基于分阶段迭代模型的产品设计任务分布方案优化

用Markov Chain方法对耦合设计迭代过程进行分析，得到迭代过程的时间成本与设计结构矩阵 中表示任务周期、返工概率的参数的关系，进而获得有利于缩短开发时间的任务布局方案的设计 结构矩阵调整策略.以某照相机的开发过程为例，验证了该方法的有效性.关键词：分阶段迭代模型；任务分布；设计结构矩阵；方案优化；Markov Chain中图分类号:TB472：TH122

文献标识码：A

文章编号：1672-948X(2019)06-0092-05Optimization of Product Design Task Distribution Scheme

Based on Grading Iterative ModelTian Qihua1 Yan Junzhe1 Dong Qunmei2 Zhang Yurong1 Zhou Xiangman1(1. College of Mechanical & Power Engineering, China Three Gorges University, Yichang 443002, China； 2. State Grid Dadu River Repair & Installation Co. , Ltd. , Leshan 614000, China)Abstract Aiming at the problem that the unreasonable task distribution in product development leads to the extension of product development time, the iteration process of coupled design is analyzed by applying the

design structure matrix (DSM) and the Markov chain method； the relationship between the time cost of the iterative process and the parameters representing the task cycle and rework probability in the design structure

matrix is obtained； and then DSM adjustment strategy is obtained which is helpful to shorten the development time. Taking a camera's development process for example, the validity of this method is proved.Keywords grading iterative model； task distribution； design structure matrix (DSM) ； scheme optimizing； Markov Chain完全的并行迭代模型假设所有的耦合集任务同

矩阵(work transformation matrix, WTM)运用到二

时并行执行，而在实际的产品开发过程中，部分任务 由于设计要求的改变或资源约束等原因总存在执行

阶段迭代模型中，得到了有利于减少项目开发时间成 本的任务分配方案；陈卫明等⑵通过启发式算法对二

顺序先后问题，优先完成的任务必须要等待后完成的 阶段迭代模型执行时间进行求解，但是没有给出寻求 最优的二阶段迭代模型任务分布方案的可行方法；肖 人彬等⑷针对分阶段迭代模型中的资源分配问题，运

任务，故完全并行迭代模型已经不再适用，故需要采 用分阶段迭代模型处理•针对分阶段迭代模型中任务 分布方案优化的问题，国内外学者进行了相关的研

用遗传算法得到了较优的资源分配方案；田启华等⑷ 运用动态规划法对二阶段迭代模型的任务分布方案究，并取得了相应的成果.如:Smith等⑴将工作转移收稿日期=2018-12-29基金项目：国家自然科学基金资助项目(51475265)通信作者：田启华(1962—)，男，教授，博士，博士生导师，主要从事机械设计及理论XAD/CAE/CAM等研究.E-mail： tqh@ctgu. edu. cn第41卷第6期田启华，等基于分阶段迭代模型的产品设计任务分布方案优化93进行寻优,并证明了该方法能在一定程度上弥补启发 式方法容易陷入局部最优解的不足.上述文献从不同

角度研究了分阶段迭代模型中任务分布方案优化的 问题.但是，不同算法对具体迭代模型的适用性较为

有限，甚至需要对算法进行一定的改进才能成功获取 一个较优解.鉴于以上研究的不足，引入Markov Chain理论.

假设在设计任务的迭代过程中，每次只有一个任务执 行，因此其过程转化为串行设计迭代过程，而耦合设 计任务集总的执行时间等于那些任务所花时间的总

和•针对此假设，耦合设计任务集可以描述成Markov Chain模型并用Markov Chain分析方法进行分析.

由于Markov Chain分析方法是建立在随机统计分析 基础之上，因此算法简单，求解过程清晰明了，无需借

助计算机编程就能得到结果.当耦合任务规模较小

时，采用马尔可夫链(Markov Chain)方法对串行迭代

过程进行建模分析，可以通过计算纯粹顺序情况下的

总迭代时间，来确定最优的耦合集任务执行顺序.目前Markov Chain在迭代建模中也已经得到许

多成功应用.例如：石坤等阪运用Markov Chain理 论，将量化的流程图转化为Markov概率转移图，根

据概率转移图列出概率转移矩阵，求解矩阵的平稳分 布，利用平稳分布来解出驾驶人行为的可靠性；南爱

强等⑷结合经典灰色理论，构建了一种新型的灰色 Markov Chain模型，相较传统的经典灰色理论具备 较高的预测精度.设计结构矩阵能简化并有效地描

述、分析信息流和迭代循环等信息交互关系，具有较

强的问题描述能力\"切，还能很好地适应矩阵运算，被 广泛地应用于产品开发领域的研究中.目前,DSM在

耦合集迭代的求解问题上已经得到不少应用，例如杨

沁等⑼分析了需求节点之间的矛盾，提出了一种基于 DSM的客户需求表达方法；钱艳俊等〔⑹充分利用矩

阵运算的特点，提出了基于DSM的耦合活动排程.本文在分阶段迭代模型的基础上，以缩短产品开

发过程的时间成本为目标，引入设计结构矩阵，运用

Markov Chain方法对设计任务的迭代过程进行分 析,得到不同任务分布方案下执行时间、任务周期和 返工概率的关系，提出一种基于分阶段迭代模型的产

品设计任务分布方案优化.1分阶段迭代模型的求解分阶段迭代模型是在完全并行迭代模型的基础

上发展而来的，是将部分任务延迟执行的情况加以考

虑，其求解方法是将整个耦合任务集分成若干个子

集，并将这些任务子集分配到不同的阶段中去执行. 在迭代过程中，整个耦合任务集通常包含有多个设计

任务(假设任务个数为祝)，可能的迭代方式包括一阶

迭代、二阶迭代、……、祝阶迭代.为了便于研究说明， 本文以m阶迭代为研究对象，即假定每个阶段均只

有一个任务被执行的情况.为了描述分阶段迭代模型中各任务的分布情况，

定义对角线矩阵K为任务分布矩阵，表示为：~kn00… 0 ■0上220… 0K =00叽・・・ 0(1)_000・・・ kv mm _式中，矩阵K对角线上元素和、展2取值为0或者1(其中= 当取值为0时,表示第i个任务不在当前指定的阶段被执行，

当取值为1时，表示第i个任务在当前指定的阶段被

执行.根据文献口叮，分阶段迭代模型第1阶段的执行

时间T.为：=Z(I -KlRKtr1K]uQ

(2)式中，Z是任务周期矩阵;R是返工概率矩阵；初始的 工作向量«o是全1向量，表示在第一次迭代中所有 任务都需要同时执行』为单位矩阵，矩阵K|是一个

对角矩阵，描述了任务在第1阶段迭代过程中的执行 情况，矩阵比对角线上第i行第j列元素的取值定 义如下：舄叫卩如果 i=j且第其它i个任务在1阶段 第2阶段需要的执行时间T2为：T2 =Z(I ~K2RK2r} (K2 -K^u0

(3)式中，矩阵K?为第2阶段的任务分布矩阵，描述了任

务在第2阶段迭代过程中的执行情况，矩阵对角 线上第£行第j列元素的取值定义如下：2卩 如果=lo

i=j且第i个任务在1,2个阶段其它第s阶段所需时间Ts为：T, =Z(I — K,RK,)T(K,(4)

式中，矩阵K,为第s阶段的任务分布矩阵，描述了任

务在第s阶段迭代过程中的执行情况，矩阵K,对角

线上第i行第j列元素的取值定义如下：k = 卩{ 如果i 且第i个任务在1至s个阶段 10 其它将所有阶段的执行时间求和，并对其取模，可得94三峡大学学报(自然科学版)2019年］2月到迭代过程的总时间成本值为T：T = |STm

s I (5)J = 1对于一个包含有多个任务的分阶迭代过程.通过

设计一个较优的任务分布可以减少迭代过程的时间 成本.因此，从迭代过程本身出发，通过研究DSM中 任务周期矩阵Z、返工概率矩阵R与时间成本之间的

关系，以得到有利于时间成本下降的任务布局方法.2任务分布方案的优化策略DSM是一个具有相同行列标志的矩阵，能够以 直观、形象、最优的分析形式显示迭代过程中任务之 间的耦合关系.本文采用DSM对耦合集中任务的执 行状态进行描述.例如，对于一个包含有A、B、C、D

4个任务的耦合集的四阶迭代过程，若A、B、C、D任 务分别在第1阶段、第2阶段、第3阶段、第4阶段被

执行，结合文献［12-13］中DSM的设计方法，该迭代

过程对应的设计结构矩阵如图1所示.A B C DZ1

ri2ruri4ri\\Zlrn「23HiryiZi□2『43Z4图1设计结构矩阵由图1可知，DSM主要包括对角线和非对角线

单元•其中，G、Z2、Z3、“为DSM对角线上的元素，

描述了耦合集中各任务的执行周期值；是DSM非对

角线的元素，表示在迭代过程中任务的返工概率.图 1设计结构矩阵对应的任务周期矩阵Z和返工概率 矩阵R分别为：根据公式(1)-(5)可知，迭代过程的执行时间不

仅与任务的分布矩阵K,有关，还与任务周期矩阵Z、 返工概率矩阵R直接相关，而任务周期矩阵Z、返工

概率矩阵R分别由DSM中对角线上的元素、非对角

线上的元素组成，且各阶段迭代的任务分布矩阵K, 也是由DSM中任务的执行顺序决定.为了减小问题分析难度，取DSM中任务A、B进

行分析，并简化DSM中元素的记法，即：“、Z2分别 是任务A和B的执行周期值，取值为整数，表示任务

A和B分别执行所需的时间；r,.r2分别是任务A、B的返工概率，其取值范围均为0到1,小表示每

次任务A完成后，引起任务B要重做的概率，而九 表示每次任务B完成后，引起任务A要重做的概率,对应的DSM如下：ABA厂2 =B(6)-厂i根据定义，返工概率矩阵R是由DSM非对角线

上的元素构成，任务周期矩阵Z是由DSM对角线上的元素构成，即:R = 0 Ln o;Z =Z1_ 0 Z2对该迭代过程建立Markov Chain模型，如图2 所示.任务分布优化相当于确定哪条虚箭线包括在链 的模型中.图2 2X2阶迭代的Markov Chain模型图2中虚线指向A,表示任务A在第1阶段先执 行，任务B在第2阶段被执行，记为A-B方案；若虚

线指向任务B,则为B-A方案.定义Ta和Tb分别表示在同一迭代过程中任务

A和任务B的执行时间，根据图2的迭代过程，参考 文献口4］中运用Markov Chain对串行迭代过程进行 建模的方法，可得到如下矩阵线性方程组：

lTA=r,Tti + zt (?)Itb =r2rA + z2用Ta.b和T*分别表示A-B.B-A方案的时间

成本，分别求解两种任务分布的TA.B和T»a关于周

期值“、孔和返工概率值r,、九的数学关系式.在A-B方案中，阶段1只有A任务被执行，故阶

段1的任务执行时间即为任务A单独执行所需的时

间，即Ta=2i!在阶段2中，A任务是非开始任务，只 需要保留B任务的执行时间Tb，根据公式(7),可以 得到Tb =字亘A-B方案的总时间成本为阶段1 —厂严 1和阶段2之和，即若为B-A方案，阶段1只有B任务被执行，故阶

段1的任务执行时间即为任务B单独执行所需的时

间，即TB = z2i在阶段2中，B任务是非开始任务，只 需要保留A任务的执行时间7\\，根据公式(7),得第41卷第6期田启华，等基于分阶段迭代模型的产品设计任务分布方案优化95B-A方案的6为：几二心再人方案的总时z1+z2r1导，与目前已有的引入优化算法来获取较优的任务布 局相比，是解决分阶段迭代过程方案优化的另一种途 间成本为:径•下面通过示例计算说明本文提出方法的有效性.于

«1 +乂2J B-A = «2 + -：----------------------

九1 —广严(9)通过上述分析，可知对于包含任务A和B的耦

3实例分析合集迭代过程，其可能的任务分布方案及对应的 DSM和时间成本见表1.以某型号照相机开发过程为例进行说明.该产品

表1两种方案下的DSM及时间成本T开发过程包括功能定义（任务A）、概念设计（任务

方案DSMB）、快门装置设计（任务C）、取景装置设计（任务D）、 时间T

相机体设计（任务E）、卷片装置设计（任务F）、光学

ABA-BAPr2~z2 +g r2镜头设计（任务G）、光圈设计（任务H）等8个任务， B叽其中任务C、任务D、任务E以及任务F等4个任务

构成带循环信息流的耦合集⑴切•假定照相机开发过 BAB-AB戈2G +?2厂|程中C、D、E、F分别在第1、2、3、4阶段被执行，对应

A-r21 —\"2的任务分布形式表示为（C、D、E、F）,DSM对角线上

的元素表示任务C、D、E、F各自执行的周期，非 为了便于分析任务分布方案的优化策略，先假设 对角线上元素表示各任务的返工概率，该方案下的

A-B方案的时间成本小于B-A方案,即DSM如下.6 +, ---之2---------------------- +之1厂2 +北2厂1(10)C D E F1—厂1厂2 1—厂1厂2由于 OOi VI ,0<厂2 VI，则（1 —d）〉0,将公 式（10）中不等式的两边同乘以（1一厂］厂2），整理后，可

以得到N1厂2（1—厂1 ） V^2厂1（1—厂2），即引：^丄一厂2 <孔 厂厂* 11—

1 — ^2 1 — 口（“11）、结合式（6）对应的DSM可知小、小对应为DSM

中的非对角线元素，zj、z2对应为DSM中的对角线

元素.分析式（11）可知，当任务A的执行周期21小

于任务B的执行周期匕、任务B的返工概率九小于 任务A的返工概率ri时，式（10）、式（11）恒成立，即

T A-B VTba.在迭代初始阶段，初始工作向量«o为全1列向

也就是说，对于包含A、B任务的耦合集迭代过

量，即：“。=口 1 1 1］丁，任务c、D、E、F分别被分配到 2\"1、2、3、4阶段去执行执行，根据第2节关于任务分布

程，其DSM为

'zi r时，当满足：ZjK]=0DSM对角 0,K?=1析过程，执行周期长的任务应优先安排在0线的右下方，返工概率大的值应放置在DSM对角线

0_0_的下方，这种任务布局是有利于时间成本减少的.1j

■以上分析过程，是以迭代过程中的两个任务为对

K3 =1象来分析的，将任务分布方案的优化问题，转化成具 1,Kq =11体的计算推理，进而抽象性地得出了有利于时间成本

01_的布局方法.虽然理论过程存在一定的局限性，但是， 根据第2节中公式（5）,可得照相机开发分阶段 该研究方法是从迭代过程的本身出发进行的计算推迭代过程的时间成本为：96三峡大学学报（自然科学版）2019年12月Z(/ -K.RKJ 'K.Mo +Z(I -K2RK2V} g ~K, )«„ +ZCI -k3rk3)~'(k3 -k2)«0 +(13)Z(I — K’RKQTg ~K3)u0将Z、R、K|、K2、K3、K』、“°、I分别带入公式（13）,可以得到基于任务分布方案（C、D、E、F）的时间成本为200. 361 4个时间单位.下面应用本文提出任务分布优化方法对DSM

进行重新调整.为减少照相机开发的时间成本，在对

DSM进行调整的过程中，尽可能让周期较长的任务 稍后执行，高返工概率值置于DSM对角线的下方，

分析公式（12）中DSM的数据结构，需要将返工概率 较高的0.5和0.4调整到对角线的下方，周期最长的 任务D尽可能安排在靠后阶段被执行，可将DSM第4行和第2行进行交换，再将第2列与第4列交换，调整过程如图3所亦.c D E F C D E F

CFEDC'20 0.1 02 0.3'交换第2行C'20 0.1 02 03交换第2列C'20 0.3 0.2 0.1'D0.3 35 0 0.2和第4行〜F0.1 0.1 02 18和第4列K F0.1 18 0.2 0.1E0.1 0.3 21 回E0.1 0.3 21 回E0.1 回 21 0.3F0.1 0.1 0.2 18D0.3 35 0 0.2D0.3 0.2 回 35.图3 DSM的结构调整过程图3得到的调整后的DSM的任务分布形式为表 示任务C第1阶段被执行，任务F在第2阶段被执

行，任务E在第3阶段被执行，任务D在第4阶段被执行，即调整后的DSM为：CFEDC~200. 30.20. 1F0. 1180. 20. 1E0. 10. 5210. 3(14)D0. 30. 20.435调整后的DSM的任务矩阵分别为:_1「1009K2 =000_1__1「1 _K011,Kq =11_- 1_照相机开发过程基于调整后的DSM的Z、R矩阵分别为:（13）,可得到任务分布方案（C F E D）的时间成本值 为154. 470 1.对DSM进行调整前，周期最长的任务

D在第2阶段被执行，返工概率较高的数值0. 5和 0. 4在对角线的上方；调整后的DSM中，周期最长的 任务D在最后段被执行,返工概率较高的数值0. 5和

0.4均在对角线下方，时间成本为154.470 1个时间 单位，见表2.表2基于DSM优化策略前后的任务布局及时间成本调整任务分布

执行时间前后方案DSMT/dCDEFC「200. 10. 20.调整前（C、D、E、F）D0. 3350.40. 2200. 3614E0. 10.3210.5F0. 10. 10.218_CFEDC「200. 30. 20. r调整后（C、F、E、D）F0. 1180.20.1154. 470 1E0. 10. 5210.3D0. 30. 20.435 _由表2可知，调整前照相机开发过程的时间成本 为200. 361 4个时间单位，调整后的时间成本为

154.470 1个时间单位，调整后减少了 45. 1 3个时

间单位，时间成本下降了 22. 904 2%.以上分析结果 表明，对于分阶段迭代模型任务分布优化问题，采用

本文提出的基于DSM优化方法，即周期长的任务稍 后执行，返工概率高的值放在DSM对角线的下方， 是有利于时间成本下降的任务布局.4结语本文研究的基于分阶段迭代模型的产品设计任

务分布方案优化方法，通过运用Markov Chain方法 来分析任务周期和返工概率对不同任务分布时间成

本的影响，并通过构建任务分配衍生矩阵，简化了分

阶段耦合集设计任务分配的数学模型.运用该方法对

分阶段迭代模型的任务分布进行优化，以某型号照相 机开发过程为例，验证了该分析方法是可行且有效

的，并能获取一个能有效减少产品开发过程的时间成 本的相对较优解，对实际产品开发有一定的参考意义.（下转第112页）112三峡大学学报(自然科学版)2019年12月on B/P pair and Al/N pair doping carbon nanotubes[J]. [17] Liu H, Dong H , Ji Y» Et Al. The adsorption, diffusion

Chemical Physics Letters, 2015 , 619 :1-192.and capacity of lithium on novel boron-doped graphene

口4] Liu J, Zhang Z H, Deng X Q, et al. Electronic struc­

nanoribbon： A density functional theory study[J]. Ap­tures and transport properties of armchair graphene na­

plied Surface Science♦ 2019, 466 ： 737-745.noribbons by ordered doping [J]. Organic Electronics, [18] Zheng B. One-step synthesis of nitrogen-doped graphene

2015, 18:135-142.from a sole aromatic precursor [J]. Materials Letters,

[15] Srivastava P, Dhar S, Jaiswal N K. Potential spin-po­

2019, 236:583-586.larized transport in gold-doped armchair graphene nanor-

[19] Bhattacharya B, Seriani N, Sarkar U. Raman and IR

ibbons[J]. Physics Letters A, 2015, 379(9) ：835-842.signature of pristine and BN- doped y-graphyne from [16] Jacobse P H , Kimouche A, Gebraad T, et al. Electron­

first-principleEJ]. Carbon, 2019, 141:652-662.ic components embedded in a single graphene nanorib- [责任编辑卢亚霞]bon[J]. Nature communications, 2017, 8(1)： 119.(上接第96页)参考文献：划者体系流程运行评估[J].工程管理学报，2017,31:17-22.(4)[1] Sm让h R P, Eppinger S D. Deciding between sequential

[8] 杨 青，吕佳芮，索尼亚.基于设计结构矩阵(DSM)的

and parallel tasks in engineering design]J]. Concurrent 复杂研发项目建模与优化研究进展□].系统工程理论

Engineering： Research and Application, 1998, 6 ( 1 ) •

与实践，2016, 36(4):9-1002.15-25.[9] 杨 沁，宋 飞，潘高峰，等.基于设计结构矩阵的产

[2]

陈卫明，陈庭贵，肖人彬.动态环境下基于混合迭代的 品多域需求表达合理性研究口].中国机械工程，2017,

耦合集求解方法[J]•计算机集成制造系统，2010, 16

28(12):1455-1461.(2):271-309.[10] 钱艳俊，林 军.基于设计结构矩阵的耦合活动排程

[3]

肖人彬，周 锐，陈庭贵.基于资源均衡策略的耦合任

LJ1 系统工程,2018,36(6):154-15 8.务集求解方法研究[C].南昌：上海系统科学出版社(香

[11] 田启华，梅月媛，刘 勇，等.基于多阶段工作转移矩

港)，2008.阵的串行耦合设计任务分配策略[〕]•中国机械工程，

[4] 田启华，董群梅，杜义贤，等.基于动态规划法的二阶

2017,28(5):583-588.段迭代模型任务分布方案的寻优[J].机械设计与研究，

[12] 陈庭贵，据春华.基于设计结构矩阵的任务规划新方法

2016,32(3):85-88.D0•计算机集成制造系统,2011, 17(7):1366-1373.[5] 石 坤，张永进，孙超勇.基于马尔科夫链的驾驶行为

[13] 尹保伟.应用DSM方法优化整车工程变更流程[D].北

可靠性分析[J].机械研究与应用，2017,30(6) :49-52.京：北京理工大学，2016.[6] 南爱强，王锋宪.经典灰色理论和马尔科夫链的交通量

[14] 张卫民，周伯生，罗文胡.顺序迭代开发过程建模与仿

预测模型构建[J].微型电脑应用,2018,34(7):85-87.真[J]・计算机集成制造系统,2008,14(9):1696-1703.[7] 吴 桦，苏振民，唐如建.基于设计结构矩阵的最后计[责任编辑张莉]