基于路径搜索的产品设计过程建模

胡从林，容芷君，陈奎生，但斌斌

（武汉科技大学 机械自动化学院，湖北 武汉 430081）

0 引言

随着全球制造业市场的快速发展，企业面临着越来越激烈的市场竞争。为了以最快的速度、最低的成本提供质量最优的产品来快速响应市场，研究缩短产品设计周期和优化产品设计过程的理论与方法具有十分重要的意义。目前，设计过程的优化建模 方 法 有 关 键 路 径 法 （Critical Path Method，CPM）、有向图法、设计结构矩阵（Design Structure Matrix，DSM）法、甘特图（GANTT）、计算机辅助制造定义方法（Integrated Computer aided manufacturing DEFinition method，IDEF）系列建模方法和Petri网建模方法等［1－2］，根据这些方法，可以从不同角度对设计过程进行建模。其中，CPM和甘特图对设计过程中的业务运作、项目管理可以有效地建模；IDEF3可以静态地描述整个设计过程，但不支持过程的改进和分析；DSM采用耦合、撕裂等规则对设计过程进行重组优化；Petri网和有向图都是一种面向图形的建模方法，可以对设计过程进行动态描述。设计过程由设计要素组成，设计要素包括设计活动、设计任务、设计实体零部件和设计者等，设计要素之间相互关系的表示和分析是设计过程建模方法的主要内容和目标。因此，在设计过程建模中，对设计要素进行层次划分，得出设计要素之间的相关性和耦合性，从而减少设计过程的迭代次数，是优化产品设计过程的重点。国内外学者对产品设计过程建模进行了大量研究。Mike等［3］在产品设计过程中，考虑结构和功能等多域情况，提出基于域匹配矩阵（Domain Mapping Matrices，DMM）和 DSM 的产品设计过程建模方法；Heiko Duin等［4］在协同设计的基础上，应用树图网络建立了产品设计动态模型；Tang等［5］提出基于DSM的产品设计工程变更模型，用以分析设计要素之间的依赖关系，从而降低设计要素变更对设计过程的影响；郭银章等［6］通过对决策变迁信息库中的决策信息进行分析，提出基于Petri网的产品设计过程动态模型。针对分析设计要素之间的关系往往采用DSM方法，该方法最初由美国学者Steward［7］博士于1981年提出，它是一个特定的研究产品设计过程分析规划的方法。20世纪后期，Eppinger等［8］提出了数字化的设计结构矩阵（Numeric Design Structure Matrix，NDSM），发展到现在，DSM已经成为设计过程建模的主要研究方法之一，围绕该方法也有一些相关软件与工具，如 Antares DSM，AcclaroDFSS，IntelliJIDEA 等［9］。DSM方法主要根据设计要素之间的联系强度对设计要素进行运算，如划分、撕裂、绑定和聚类等，从而实现对设计过程的结构建模与分析，但设计要素之间的联系强度主观判断会直接影响DSM的运算结果，导致产品设计过程建模的不确定性和复杂性，同时DSM方法对复杂产品设计过程建模有一定的局限，其针对大规模复杂问题的计算速度和精度还有待进一步提高。近年来，针对DSM的局限性，研究设计过程复杂性的设计过程建模方法成为新的焦点［10］。

本文应用基于路径搜索的方法对产品设计任务进行分析，用有向图描述产品设计任务之间的依赖关系，定义了有向图和关系矩阵的转化规则。通过所提算法对关系矩阵中元素的路径进行搜索，根据搜索规则对设计任务进行重组优化，建立层次过程模型。以某大型起重机吊臂设计过程为例说明了该方法的可行性。该方法基于图论和矩阵方法，避免了DSM方法中关系强度的主观判断，同时整合了DSM方法中的划分、撕裂、聚类等运算，计算过程简洁明确。

1 产品设计过程建模

产品设计过程是一个动态、复杂的过程，包含多个设计者、设计约束、设计目标、设计活动和过程变量等要素，这些设计过程要素之间的相互关系构建了设计过程的结构［11］。由于设计任务之间的相互关联，设计过程建模成为了产品设计过程的难点。在对产品设计过程进行建模时，模型的可信性既取决于模型的种类，又取决于模型的构造过程。复杂产品设计过程由大量设计任务组成，这些设计任务之间存在着错综复杂的相互作用关系，要建立设计过程的数学模型，必须首先正确地表示这些设计任务及其相互之间存在的某种关系，即建立系统的过程模型。过程模型具有以下特性［12］：

（1）过程模型是一种设计关系模型，可用有向连接图表示。

（2）过程模型是一种以定性分析为主的模型，主要用来分析系统各设计任务之间的关系。

（3）过程模型可用矩阵形式来描述，使用定性分析和定量分析相结合的方式。

（4）过程模型的描述形式正处在数学模型和逻辑分析形式之间，它可以处理宏观、微观、定性和定量的问题。

在产品设计过程中，各设计任务之间存在着复杂的依赖关系，从任务相互影响的角度来看，有三种类型：

（1）串行 一个任务要在另一个任务完成之后才可以进行，即B任务需要将A任务的输出作为其输入，任务之间存在前后依赖关系。

（2）并行 任务之间不存在相互依赖关系，即任务A和任务B是并行关系。

（3）耦合 任务之间存在双向交互关系，即A任务需要将B任务的输出作为它的输入，同时B任务也需要将A任务的输出作为它的输入。

这三种关系类型的有向图及相应的矩阵映射如图1所示。

2 基于路径搜索的建模方法

产品设计模型是一种描述设计要素关系的过程模型，要素之间的关系可以用有向图来描述［13］。有向图是反映对象之间关系的一种工具，由一系列节点和连线组成，节点表示设计要素，连线表示设计要素之间的关系。用V＝｛v1，v2，…，vn｝表示设计要素集合，E ＝ ｛e1，e2，…，em｝表示设计要素之间关系的集合，G＝〈V，E〉表示有向图。有向图和矩阵之间存在对应关系，有向图中的节点和连线分别对应矩阵中的元素和元素之间的关系。对设计过程进行建模首先需要明确设计任务之间的关系，然后将设计任务之间的关系转化为设计过程关系矩阵，最后应用数学方法，如图论、矩阵方法等进行数学计算，从而建立设计过程模型。由产品设计任务之间的关系，可以得到设计关系矩阵

式中：T ＝ ｛t1，t2，…，tn｝为设 计 任 务 集 合；R ＝｛r1，r2，…，rm｝为设计任务关系的集合；rij表示任务i和任务j之间的影响关系，i，j∈ （T1，Tn），Rij∈（r1，rm）。

在关系矩阵R（如图2）中：＊表示设计任务i对设计任务j存在影响关系；空白表示设计任务i对设计任务j没有影响；＋表示设计任务i本身的关系。

图2所示是有向图和关系矩阵的对应关系。

路径搜索是关于矩阵间元素相互关系的一种数学建模方法，即根据搜索矩阵中元素的行和列，来判断环路和层级关系。基于路径搜索的产品设计过程建模的算法步骤如下：

步骤1 根据元素之间的关系确定关系矩阵R，并明确矩阵的维数。

步骤2 在关系矩阵中进行搜索，找出行全为空的元素设置为起始任务，列全为空的元素设置为终止任务。如果没有搜索到行全为空或列全为空的元素，则转步骤5。

步骤3 把行全为空的元素移动到矩阵最上边，标出为一个任务块；把列全为空的元素所在的行移动到矩阵最后一行，标出为一个任务块。

步骤4 删除任务块中的元素，返回步骤1。

步骤5 说明元素间存在环路（耦合块），从中找到任意一个环，把环中的所有元素标志为一个任务块。环搜索规则为：选择矩阵中任意一个元素（原则上优先选择和其他元素关联比较多的元素作为搜索起点），根据元素之间的关系搜索与其有关联的任一个元素，直至再次回到起点元素，形成一个环路。如果没有找到回路，则再选择其他元素进行重复搜索，直至找到一个环路为止。

步骤6 把环中所有元素合并到一个新元素中。合并规则为：只要其他元素和环中至少一个元素存在关联，则该元素就和新元素存在关联关系。

步骤7 重构过程关联矩阵中的元素，返回步骤1。

步骤8 按照标志任务出现时间的先后，确定最终元素层级关系。

该算法的C＋＋语言编程代码设计如下：

｛

／／初始化数据

Init（）；

／／元素为0，或读取的初始数据文件错误

if（elements＿count＝＝0）

｛

cout＜＜"元素个数为0，或者文件“data.txt”打开错误"＜＜endl；

return false；

｝

／／定义找环函数Find＿Round的返回值Find＿Round＿Return frr＝init；

while（frr！＝ no＿find＿should＿terminate）

｛

／／查找空行和空列，空行往上移，先移上去的在上面；空列往后移，先移上去的在后面

Find＿And＿Delete＿Empty＿Row＿And＿Column（）；

／／临时变量：找环过程中临时存储环中的元素（元素的原始标记号）

vector〈int〉container＿find＿raw；

／／临时变量：找环过程中临时存储环中的元素（元素在新矩阵中的索引）

vector〈int〉container＿find＿current；

／／找环

frr＝ Find＿Round（container＿find＿raw ，container＿find＿current）；

／／如果找到环，就将环元素合并为一个新的元素G，同时计算新元素与矩阵中其他元素的关系

if（frr＝＝find＿round）

Merge＿Round＿Elements（container＿find＿raw ，container＿find＿current）；

｝

／／合并环

Classify＿Merge（）；

／／找未成环的元素

Find＿Signal＿Element（）；

／／计算环、起始元素、未成环元素的层级关系

Tidy＿Hierarchy（）；

／／输出结果

Print＿Result（）；

return true；

｝

3 算例

在产品设计过程建模中，产品设计任务之间往往存在着相互影响的关系，找到任务之间的耦合关系和各个任务之间的层次划分是建模的关键。下面以QTZ80H型塔式起重机吊臂为例，说明基于路径搜索的建模过程。吊臂的设计开发涉及总体、结构、传动、分析计算、液压、电器控制、标准、工艺和试制等多个环节，该设计过程包含17个设计任务：①吊臂设计输入确定；②截面形式设计；③吊臂材料选定；④变幅形式设计；⑤伸缩方式设计；⑥吊臂根部铰点位置设计；⑦各节臂臂长（节数）设计；⑧变幅液压缸铰点位置设计；⑨各节臂截面参数设计；⑩基本臂设计；⑪伸缩臂设计；⑫伸缩机构设计；⑬设计校核；⑭制造工艺性分析；⑮样机试制（实物）；⑯ 设计修改；⑰设计定型。任务之间的关系如图3所示。

由起重机吊臂设计任务之间的关系可以得到各设计任务间的关系矩阵R，矩阵中的元素表示设计任务，如图4所示。

根据路径搜索算法找出行为空的元素，第一行为空，标记为起始任务；找出列为空的元素，最后一列元素为空，标记为终止任务，如图5所示。

删除行为空的元素和列为空的元素，得到剩余元素的重构关系矩阵R1，如图6所示。

在R1中进行搜索，如果找不到行为空的元素或者列为空的元素，则说明在R1中存在环（元素之间的耦合关系）。下面进行环搜索，任意选择一个元素作为搜索起点，例如选择元素10作为搜索起点，可以搜索到元素10受到元素12、元素13、元素15、元素16的影响，转移到下个邻近元素12；元素12受元素10、元素11、元素13、元素15、元素16的影响，依次向下进行搜索，就转移到下个邻近元素13；元素13受元素9、元素10、元素11、元素12、元素15的影响，转移到元素15；元素15受到元素16影响，转移到元素16；元素16受元素10、元素11、元素12影响，回到元素10，形成一个回路G1。环路G1＝（10，12，13，15，16），如图7所示。

把元素10，12，13，15，16合并成一个新元素环G1，找出其他元素与环路G1的关系，更新矩阵R1，得到重构矩阵R2，如图8所示。

如果进行重新搜索，也不存在行为空元素或者列为空的元素，则说明R2也存在环，再根据上面环的搜索规则进行搜索得到环路G11，如图9所示。

由于环G1在环G11中，可以把两个环合并到一个环G0中，则环G0＝（9，10，11，12，13，15，16），重构关系矩阵R3，如图10所示。

在矩阵中可以搜索到列为空的元素G0，把G0设置为另一个终止任务。同理，重复以上过程，可以得出悬臂梁多个设计任务之间的耦合层级关系，如图11所示。

根据路径搜索算法步骤2，首先确定起始任务为元素1、终止任务为元素17，经过行列变换将起始任务元素和终止任务元素分别调整到矩阵的最上方和最下方。然后经过计算可以得到三个环（耦合任务），分别记为G0＝（9，10，11，12，13，15，16），G1＝（6，7），G2＝（3，2，14），在同一耦合块中元素彼此影响比较大，故同一耦合块中的元素属于一个层级。元素5和元素8在设计时互不影响、是并行关系，放在一个层级。因此，在对起重机吊臂设计过程建模时，可以把其中的17个设计任务分成7个层级关系，每一个层级里的设计任务在设计过程中的优先度相同，并且相互影响比较大，可以构成一个设计模块；层级越是在最上层的设计任务，对以下层级的任务影响越大；并行任务彼此不影响，可以同时进行设计。

该模型算法实现了计算机编程，提高了计算效率，体现了该算法的实用价值。在该算例中，元素5和元素8是并行关系，计算机自动把两个元素分在两个层次，这对产品设计过程建模结果的分析不会产生影响。计算机运算结果如图12所示。

4 结束语

本文提出一种基于路径搜索的产品设计过程建模方法，该方法可以对设计要素进行重组优化，生成设计结构的耦合层级关系，并应用某大型起重机吊臂的设计过程实例对该方法进行验证，结果表明该方法清晰、简明，与实际设计情况相符，为产品设计过程建模提供了可行有效的方法。该方法具有以下特点：①所构建的模型可以和有向图直接转化，表达直观，便于理解；②该方法以图论与矩阵方法为理论基础，具有通用性和科学性；③模型算法容易用计算机编程实现，方便过程计算，计算结果可以清晰展现设计过程；④可以通过一次建模，对所有设计要素之间的关系进行分析。本文的后续研究工作主要针对其他几种产品设计过程建模算法（可达矩阵法、邻接矩阵求幂法、撕裂算法等）进行计算机编程，同时根据计算机编程的复杂程度和算法计算速度等指标，对这几种设计过程建模算法进行比较和改进，从而得到更优的设计过程建模方法。

［1］ XIONG Guangleng.The theory and practice of concurrent engineering［M］.Bejing Tsinghua University Press，Springer Press，2001（in Chinese）.［熊光楞.并行工程的理论与实践［M］.北京：清华大学出版社，施普林格出版社，2001.］

［2］ HUANG Hongzhong，LIU Wei，LI Li.Process modeling of product collaborative design［J］.Computer Integrated Manufacturing Systems，2003，9（11）：955－959（in Chinese）.［黄 洪钟，刘 伟，李 丽.产品协同设计过程建模研究［J］.计算机集成制造系统，2003，9（11）：955－959.］

［3］ DANILOVIC M，BROWNING 段 .Managing complex product development projects with design structure matrices and domain mapping matrices［J］.International Journal of Project Management，2007，25（3）：300－314.

［4］ DUIN H，ESCHENBÄCHER J，THOBEN 段 .Modelling dynamics in collaboration：an extension to the collaborative network relationship analysis［J］.IFIP Advances in Information and Communication Technology，2011，362：287－294.

［5］ TANG Dunbing，XU Ronghua，TANG Jicheng，et al.Design structure matrix－based engineering change management for product development ［J］.International Journal of Internet Manufacturing and Services，2008，3（1）：231－245.

［6］ GUO Yinzhang，ZENG Jianchao.Dynamic modeling for mechanical product collaborative design process based on OPN and decision rule［J］.China Mechanical Engineering，2011，22（14）：1708－1714（in Chinese）.［郭银章，曾建潮.基于决策规则对象Petri网的机械产品协同设计过程动态建模［J］.中国机械工程，2011，22（14）：1708－1714.］

［7］ STEWARD 段 .The design structure system：a method for managing the design of complex system［J］.IEEE Transactions on Engineering Management，1981，28（3）：71－74.

［8］ EPPINGER 段 ，NUKALA M，WHITNEY D.Generalized models of design iteration using signal flow graphs［J］.Re－search in Engineering Design，1997，9（2）：112－123.

［9］ Technische Universität München.The Design Structure Matrix （DSM）［EB／OL］.［2011－11－16］.http：／／www.dsmweb.org／

［10］ KREIMEYER M，LINDEMANN U.Complexity metrics in engineering design：managing the structure of design processes［M］.Berlin，Germany：Springer－Verlag，2011.

［11］ MA Mingxu，WANG Cheng'en，ZHANG Jiayi，et al.Multi disciplinary design optimization for complex product review［J］.Chinese Joural of Mechanical Engineering，2008，44（6）：15－26（in Chinese）.［马明旭，王成恩，张嘉易，等.复杂产品多学科设计优化技术［J］.机械工程学报，2008，44（6）：15－26.］

［12］ RONG Zhijun，CHEN Kuisheng，YING Baosheng，et al.Structure analysis and optimization of product design proces［J］.China Mechanical Engiineering，2012，23（7）：856－859（in Chinese）.［容芷君，陈奎生，应保胜，等.产品设计过程结构分析和优化［J］.中国机械工程，2012，23（7）：856－859.］

［13］ KO 段 .An innovative matrix－based approach for designing product variety ［J］.Systematic Innovation，2010，1（2）：27－43.