基于多阶段工作转移矩阵的串行耦合设计任务分配策略

田启华 梅月媛 刘 勇 杜义贤

1.三峡大学机械与动力学院，宜昌,4430022.三峡大学计算机与信息学院，宜昌,443002

基于多阶段工作转移矩阵的串行耦合设计任务分配策略

田启华1梅月媛1刘 勇2杜义贤1

1.三峡大学机械与动力学院，宜昌,4430022.三峡大学计算机与信息学院，宜昌,443002

针对串行耦合设计任务的团队分配因涉及任务的返工而导致分配策略相当复杂这一问题，引入多阶段工作转移矩阵，将任务间的耦合关系以返工量的形式量化，并根据团队分配衍生矩阵建立串行耦合设计任务分配的数学模型，简化了串行耦合设计任务的分配过程。利用遗传算法求解该模型，获得了不同设计需求下产品开发任务的最佳任务分配方案。以某电动汽车开发项目为例，验证了该模型的可行性和有效性。

串行耦合设计；多阶段工作转移矩阵；任务分配；设计团队；遗传算法

Key works: serial coupling design; multistage work transformation matrix(MWTM); task assignment; design team; genetic algorithm

0 引言

关于设计任务分配的问题，学术界进行了许多研究。如，BASSET[1]采用数学规划法与启发式算法，解决了开发团队的时间与能力最优利用问题；包北方等[2]针对设计任务分配较少考虑任务适合度与任务协调效率的问题，建立了产品定制协同开发任务分配多目标优化模型；武照云[3]针对非耦合集产品开发过程中的任务-团队分配策略，提出了基于时序逻辑关系的动态分配蚁群优化算法；王志亮[4]提出了名义信息进化度与有效信息进化度的概念，用以解决耦合设计任务的分配问题。以上这些研究中，有的仅针对非耦合集设计任务建立分配数学模型，并不适合解决涉及返工与迭代的复杂产品开发的任务分配问题；有的虽然是针对耦合任务分配问题，但仅以完成时间长短来衡量设计任务分配效果的好坏，评价指标过于单一。

传统耦合设计任务分配方法大多是利用马尔可夫链(Markov chain)对串行设计任务的执行周期进行建模分析，并通过返工概率描述任务之间的交互关系[4-5]。按照传统方法思想，设计任务耦合迭代的时间只占整个设计周期的一小部分，总时间的长短更多取决于初始执行周期的大小。因此，为了缩短产品研发时间，只需将任务分配给执行该设计任务花费时间最少的设计团队即可。此外，对于任务数很多的大容量串行耦合设计任务集，马尔可夫链的应用会随着任务数的增多而变得更加复杂。

因此，为综合考虑设计团队各项指标对设计活动的影响，并简化计算模型，本文以工作转移矩阵(work transformation matrix,WTM)来描述耦合设计过程中的反复和迭代，并以该矩阵元素值来定量反映设计任务之间的耦合程度，提出了一种基于多阶段WTM的串行耦合设计任务分配策略。

1 基于多阶段WTM的串行耦合设计任务分配模型的构建

1.1 任务分配模型相关矩阵的定义

设计任务耦合程度的大小体现了设计任务依赖关系的强弱。依赖关系越强意味着设计任务在执行过程中需要作越多的假设，导致设计任务存在较大程度的返工，依赖越弱则表示设计任务存在较小程度的返工[6-7]，因此，设计任务耦合关系可以通过设计任务的返工关系来反映，用WTM来定量描述耦合程度。

WTM作为设计结构矩阵(design structure matrix,DSM)的一种扩展，可以用来分析设计过程中的循环和迭代，并通过耦合任务间的返工定量描述来估计循环迭代过程中的时间和成本[8-9]，用W表示。W可以分解成任务返工量矩阵R和任务周期矩阵Z两个单独的数值矩阵[10]，即W=R+Z。以T1、T2两个设计任务为例，假设每次任务T1完成后，T2有60%的工作需要重做；而当T2完成之后，T1有30%的工作需要重做；T1独立完成一次返工工作需要花6个单位时间，而T2独立完成一次返工工作则需要花5个单位时间。对应的R、Z分别为

其中，Z矩阵中对角元素的取值取决于项目开发前对设计任务的分配。

串行耦合集设计任务的分配问题描述如下：产品开发过程中包含n个任务，任务间存在返工，现在需要分配给m个设计团队完成。设计团队作为完成设计任务的主体，其任务完成效果指标是决定任务分配的重要依据。这些指标可通过参考该团队对之前类似工作的完成情况得到，并用以下矩阵进行描述[4]：

(1)执行周期矩阵Pm×n。当任务在进行分配前，任务周期矩阵Z是不确定的，需依据任务的分配情况从P中取值，矩阵元素pij表示开发团队i完成任务j时的执行周期。

(2)团队成本矩阵C1×m。它是一个行矩阵，c1i表示开发团队i在单位时间内消耗的成本。

(3)质量指标数矩阵Qm×n。相比时间和成本，质量是一个标量，因此需要进行量化，本文用质量指标数[11]表征设计质量，qij表示开发团队i完成任务j最终能够达到的设计质量水平，qij越小，表示质量水平越低；反之，质量水平越高；0

耦合设计任务是单个任务的交互集合，任务本身的性质也会对最终的分配结果造成影响，针对任务的性质引入如下矩阵：

(2)初始工作量矩阵Un×1。Un×1是一个列矩阵，ui1表示任务i的初始工作量。

(3)任务分配矩阵Am×n。设计任务分配最终结果是得到设计团队与任务的对应关系。为了避免团队之间信息沟通交流额外花费时间，这里规定每个任务只交由一个设计团队完成，而一个设计团队可以完成多项任务，可用任务分配矩阵Am×n描述，A是一个[0 1]布尔矩阵，当aij=1时，表示设计团队i被分配给任务j；aij=0，表示设计团队i与任务j无关。如有3项设计任务T1、T2、T3交给2个设计团队m1、m2完成，现将任务T1、T3分配给设计团队m1，将T2分配给设计团队m2，则对应的A为

(4)任务分配衍生矩阵Dm×n。Dm×n是A的衍生矩阵，当执行任务j时，将am×n中j≤n列元素保持不变，其他所有元素变为0，即得到Dm×n。上例中，若当前执行任务为T2，则对应的Dm×n为

1.2 任务分配优化模型的构建

WTM模型要求所有的耦合任务并行执行，而在实际中有可能出现其中一些任务由于资源约束或设计要求的改变等原因需要延迟，并在稍后的过程中才能执行。为此，SMITH等[12]进一步提出了多阶段WTM设计过程，具体做法是将n个耦合设计任务划分到r(r≤n)个阶段中。在第一个阶段中，一个有限任务集的所有任务并行执行；接下来的每个阶段所执行的任务均包含两个部分，即该阶段的任务集和前一阶段任务集的返工。通过上述描述，当r=n时，每个阶段只需执行一个任务，下一个阶段的任务包括当前任务和前一个任务的返工。此时任务的执行过程与串行迭代经典模型——马尔可夫链模型(图1)描述一致。因此，当r=n时，用多阶段的WTM设计迭代模型解决串行耦合集设计任务的团队分配问题是可行的。

图1 具有3个任务的马尔可夫链模型Fig.1 Markov chain model with three tasks

根据多阶段WTM推断出第一阶段任务执行所需时间：

T1=‖Z[I-K1RK1]-1K1U‖1

其中，I为n×n维的单位矩阵;K1为第一阶段的任务分布矩阵，是一个n×n矩阵，其中的元素定义如下：

第二阶段任务执行所需时间：

T2=‖Z[I-K2RK2]-1(K2-K1)U‖1

其中，K2为第二阶段的任务分布矩阵，其中的元素定义如下：

进而可以推断出第i阶段任务执行所需时间为

Ti=‖Z[I-KiRKi]-1(Ki-Ki-1)U‖1

其中，Ki为第i阶段的任务分布矩阵，其中的元素定义如下：

上述各阶段Ti表达式中，Z=diag((Pm1,Dm1),(Pm2,Dm2),…,(Pmj,Dmj),…,(Pmn,Dmn))，其中，Pmj、Dmj分别表示Pm×n、Dm×n的第j列元素，(Pmj,Dmj)表示Pm×j与Dm×j的内积。

则各阶段所有任务的执行时间T为

(1)

根据D、C以及每个阶段的设计时间Ti，可以计算出整个产品开发过程中所需的设计成本：

(2)

根据Q、V、A，可以得到最终产品的设计质量指标数Q，用来评价整个产品的设计质量，其中

Q=V× [(Qm1,Am1) (Qm2,Am2) …
(Qmj,Amj) … (Qmn,Amn)]T

(3)

式中，(Qmj,Amj)为Qm×n与Am×n第j列元素的内积。

本文涉及的关于时间、成本、质量的优化属于多目标优化问题，三者均是评价分配方案优劣的重要指标。从实际效果上来讲，当然要求时间(T)越短越好，成本(C)越低越好，质量(Q)越高越好。然而，要使多个指标同时达到最优一般是不可能的，比如说成本和质量，想要获得更高的质量往往意味着投入更多的成本。本文采用多目标优化方法中的ε-目标法[13]对模型进行优化。ε-目标法是选择众多优化目标中的一个为主要优化目标，再根据需求对其他优化目标进行评估，得到一个可接受范围，作为优化模型的约束条件来求解多目标优化问题。依据式(1)～式(3)可以分别建立如下三个优化数学模型。

(1)以时间为优化目标，成本和质量为约束条件建立任务分配数学模型

(4)

(2)以成本为优化目标，时间和质量为约束条件建立任务分配数学模型

(5)

(3)以质量为优化目标，时间和成本为约束条件建立任务分配数学模型

(6)

式(4)～式(6)中，T、C、Q分别为时间、成本、质量的设计变量，T1、T2、C1、C2、Q1、Q2分别表示根据不同的设计需求确定的设计时间、设计成本、设计质量的范围。

2 基于遗传算法的任务分配模型的求解

在建立串行耦合集设计任务分配的数学模型之后，关键问题就是如何对这一模型进行有效的求解。对于任务数为n、设计团队数为m的设计任务分配问题，分配方案共有mn种，随着m、n的增大，分配方案的数量呈指数级增长。由于复杂产品的设计任务分配过程中n、m的取值一般很大，更加扩大了最佳分配方案的搜索空间，若采用普通启发式算法进行搜索，结果往往需要等待很长时间。考虑到遗传算法作为模拟生物环境中遗传和进化过程而形成的一种自适应全局优化概率搜索算法，无论在搜索空间还是在搜索效率上都有很大改进，并且在一些离散优化问题，如工程调度问题、旅行商问题(TSP)的求解过程中得到了有效的应用[14]，因此本文采用遗传算法解决串行耦合集设计任务的分配问题。具体操作步骤如图2所示。

图2 任务分配模型遗传算法的实现过程Fig.2 Implementation process of task assignment model based on genetic algorithm

首先，根据设计需求选择相应的优化模型，然后对解决问题的模型准备一批表示起始搜索点的初始任务分配方案G，每个分配方案代表一个编码的染色体，染色体的长度表示耦合集的任务数，每个编码位表示设计团队的编号，利用选择、交叉、变异3种方式对这个初始群体G进行遗传操作，实现分配方案的优化，得到新一代群体G+1，接下来遗传算法会依据适应度函数、任务分配目标与约束条件对新一代种群进行评价，并判断终止条件[15]，若不满足终止条件，则重复以上过程进行迭代计算，若满足，则输出最佳的任务分配方案。

然后，应用MATLAB软件将建立的3个基于多阶段WTM任务分配数学模型(式(4)～式(6))分别转化成遗传算法的主程序，并根据串行耦合集设计任务分配的特点，参考旅行商问题(TSP)对应的遗传算法代码，编写初始化、选择、交叉、变异、适应度评价等对应的MATLAB程序，用以实现最佳分配方案的寻优。

3 应用分析

在耦合设计任务中，某些任务的开展需依赖其他任务提供的信息，因此设计项目要按照严格的序列执行，即串行执行。电动汽车的开发是典型的串行开发项目。本文以某电动汽车开发项目为例，验证了基于多阶段WTM的串行耦合集设计任务分配模型对获得最佳团队分配策略的可行性和有效性。

3.1 问题描述

对该电动汽车的设计开发过程进行分析，可以将该过程简化为8个设计任务[16]，包括：结构大小与动力学特性计算(T1)、马达规格选择(T2)、整体重量计算(T3)、存储能量需求设计(T4)、电池大小与重量设计(T5)、速度与加速度比率设计(T6)、速度与加速度规格设计(T7)和结构与支撑设计(T8)，可以将电动汽车的开发过程简化处理后得到一个8×8的串行耦合设计任务系统，整个项目按照T1—T2—T3—T4—T5—T6—T7—T8的顺序执行。

根据对该电动汽车的设计分析，确定任务的返工量矩阵(R)、质量权重矩阵(V)如下：

V=[0.15 0.10 0.10 0.15 0.15 0.10 0.15 0.10]

矩阵R中元素值量化了该电动汽车设计过程中各个设计任务之间耦合关系的强弱。其中，元素值为非0表示任务之间存在耦合关系，其值越大表明设计任务之间耦合关系越强；元素值为0则表示设计任务之间没有耦合关系。

根据实际情况，将上述8个设计任务分配给6个设计团队(m1、m2、m3、m4、m5、m6)。每个团队对每个任务的完成效果不同，表示设计团队各项指标的矩阵P、C、U、Q如下：

C=[252225212324]

3.2 问题求解

按照本文串行耦合设计任务的分配思想：执行周期长短、设计成本高低和设计质量好坏等因素均可以描述电动汽车开发任务分配方案的好坏，因此需要综合考虑。限于篇幅，本文选取设计成本为评价指标进行说明。此时的任务分配问题可以描述为：怎样将任务分配给设计团队才能满足设计时间和设计质量的要求，同时使整个设计项目的总成本最低。根据以往完成类似工作的经验，任务分配后完成时间必须在20～35天内，设计质量指标数要达到0.95以上，即将设计时间限定在[20,35]区间内，设计质量指标限定在[0.95,1)区间内。按照优化目标和约束条件，选取式(5)模型按照图2所示的流程进行求解，将设计任务个数8设置为染色体的长度，设计团队编码用1～6的正整数表示，适应度函数取个体的设计成本。选择算子选用的是随机遍历抽样运算，交叉运算使用单点交叉算子，变异运算使用均匀变异的算法，根据任务分配方案可行解的大小将种群的数量设置为200，终止代数、交叉概率、变异概率分别设置为20、0.7、0.06[15]。

运行式(5)模型对应的MATLAB遗传算法程序，得到最优个体函数值曲线如图3所示。图4表示满足相同设计需求下最差个体函数值曲线。

图3 各代最优个体设计成本Fig.3 The best individual design costs of generations

最优个体对应的团队分配矩阵A为

图4 各代最差个体设计成本Fig.4 The worst individual design costs of generations

3.3 结果分析

对本文建立的模型进行求解，从图3可以看出，随着迭代次数的增加，项目的开发成本逐渐降低，最优个体出现在第12代，之后的代数成本保持不变，说明采用遗传算法寻优是有效的。从所得到的矩阵A可以看出最后得到的任务分配方案为：任务T1、T6分配给团队m5，任务T2、T3和T8分配给设计团队m4，任务T4、T5、T7分别分配给团队m1、m2、m3，而团队m6将不参与此次设计任务，对应的设计成本为632.41万元。而从图4中可以得到相同设计需求下设计成本的最大值为855.15万元。比较两种方案对应的效果，最小设计成本相比于最大设计成本减小了34.7%。本文通过分别选择式(4)、式(6)模型对项目的设计时间和设计质量进行方案寻优，也得到类似的结论。

4 结语

本文通过引入多阶段WTM建立任务分配模型，并通过构建任务分配衍生矩阵，得到了串行耦合集设计任务分配的有效数学模型。该方法不仅简化了串行耦合集设计任务的分配计算过程，还考虑了设计团队的多项指标对串行耦合设计任务分配效果的影响。实例应用分析结果表明该任务分配策略是可行且有效的。在实际产品开发中，项目管理者应用该方法，可以对串行耦合产品设计的最终完成效果进行预先分析，因而提高了对产品开发结果的可预见性，为进行设计任务分配提供了更为科学的理论依据。

[1] BASSET T. Assigning Projects to Optimize the Utilization of Employees Time and Expertise[J]. Computers Chemical Engineering, 2000,24:1013-1021.

[2] 包北方, 杨育, 李雷霆,等. 产品定制协同开发任务分配多目标优化[J].计算机集成制造系统, 2014, 20(4):739-746. BAO Beifang, YANG Yu, Li Leiting, et al. Multi-objective Optimization for Task Allocation of Product Customization Collaborative Development[J]. Computer Integrated Manufacturing Systems,2014,20(4):739-746.

[3] 武照云. 复杂产品开发过程规划理论与方法研究[D].合肥:合肥工业大学,2009. WU Zhaoyun. Research on Theory and Method of Complex Product Development Process Planning[D]. Hefei: Hefei University of Technology, 2009.

[4] 王志亮. 复杂产品敏捷化开发中若干关键决策技术的研究[D].南京:南京理工大学,2004. WANG Zhiliang. Research on Decision-making Techniques for Agile Development of Complex Product[D]. Nanjing: Nanjing University of Science Technology, 2009.

[5] 汪鸣琦,刘传胜.工程迭代设计的过程管理研究[J]. 武汉科技大学学报,2011,34(3):210-214. WANG Mingqi , Liu Chuansheng. Process Management in Engineering Iteration Design[J]. Journal of Wuhan University of Science and Technology ,2011,34(3):210-214.

[6] 汪鸣琦,陈荣秋,崔南方. 工程迭代设计中产品族开发过程的研究与建模[J]. 计算机集成制造系统, 2007,13(12):2373-2381. WANG Mingqi, CHEN Rongqiu, CUI Nanfang. Modeling of Product Family Development Process in Engineering Iteration Design[J]. Computer Integrated Manufacturing Systems, 2007,13(12):2373-2381.

[7] 王志亮,张友良. 复杂耦合系统设计过程动态规划[J]. 计算机工程与应用,2005(13):117-120. WANG Zhiliang, ZHANG Youliang. A Dynamic Decision Model for the Complex Coupled System’s Design Process[J].Computer Engineering and Applications,2005(13):117-120.

[8] SMITH R P, STEVEN D. Eppinger Identifying Controlling Features of Engineering Design Iteration[J]. Management Science: Journal of the Institute of Management Sciences, 1997,43(3): 276-293.

[9] 陈希,王宁生.虚拟企业环境下的复杂产品并行开发框架模型研究[J].控制与决策,2003,18(6):716-719. CHEN Xi, WANG Ningsheng. Study on the Framework of Complex Product Concurrent Development in a Virtual Enterprise[J]. Control and Decision , 2003,18(6):716-719.

[10] 陈庭贵. 基于设计结构矩阵的产品开发过程优化研究[D].武汉：华中科技大学,2009. CHEN Tinggui. An Optimization Approach to Product Development Process Based on Design Structure Matrix[D]. Wuhan: Huazhong University of Science and Technology,2009.

[11] 杜微,莫蓉,李山,等. 基于产品关键特性的质量链管理模型研究[J]. 中国机械工程,2013,24(11):1516-1520. DU Wei, MO Rong, LI Shan, et al. Quality Chain Management Model Based on Product Key Characteristics[J]. China Mechanical Engineering, 2013,24(11):1516-1520.

[12] SMITH R P, EPPINGER S D. Deciding between Sequential and Concurrent Tasks in Engineering Design[J].Concurrent Engineering Research and Applications,1998,3:15-25.

[13] 张瑞军,邱继伟,王晓伟,等.基于多目标非耦合优化策略的可靠性稳健优化设计[J].中国机械工程,2014,25(2):246-250. ZHANG Ruijun, QIU Jiwei, WANG Xiaowei,et al. Reliability-based Robust Optimization Design Based on Strategy of Multi-objective Optimization Uncoupling or Decoupling[J]. China Mechanical Engineering, 2014,25(2):246-250.

[14] 董宁. 求解约束优化和多目标优化问题的进化算法研究[D].西安:西安电子科技大学,2015. DONG Ning. Study on Evolutionary Algorithms for Constrained Optimization and Multiobjective Optimization Problems[D]. Xi’an: Xi’an University of Electronic Science and Technology,2015.

[15] 史峰,王辉,郁磊,等. MATLAB智能算法30个案例分析[M].北京: 北京航空航天大学出版社, 2011：45-46. SHI Feng, WANG Hui, YU Lei, et al. Thirty Case Analysis about Intelligent Algorithm in MATLAB[M]. Beijing: Beihang University Press, 2011:45-46.

[16] 曾小华, 宫维钧. ADVISOR 2002电动汽车仿真与再开发应用[M].北京: 机械工业出版社, 2014:62-63. ZENG Xiaohua, GONG Weijun. ADVISOR 2002 Electric Vehicle Simulation and Application Development[M]. Beijing: China Machine Press, 2014:62-63.

(编辑 王艳丽)

Task Assignment Strategy for Serial Coupling Product Design Based on MWTM

TIAN Qihua1MEI Yueyuan1LIU Yong2DU Yixian1

1.College of Mechanical and Power Engineering, China Three Gorges University, Yichang,Hubei,443002 2.College of Computer and Information Technology, China Three Gorges University, Yichang,Hubei,443002

The task assignment strategy for serial coupling product design, which involved the rework of tasks, was very complex. To solve the problem, the MWTM was introduced to quantify the coupling relations among the tasks in rework amounts. Based on the task assignment derivative matrix, a model of the task assignment for serial coupling product design was built. This model was solved by genetic algorithm and so the optimal task assignment strategy of product design might be obtained for different design requirements. Taking the development of an electric car as an example, validity and feasibility of this model were proved.

2016-04-27

国家自然科学基金资助项目(51475265)

TH122;TP391

10.3969/j.issn.1004-132X.2017.05.013

田启华，男，1962年生。三峡大学机械与动力学院教授、博士。主要研究方向为机械设计及理论、CAD/CAM/CAE等。发表论文70余篇。梅月媛，女，1991年生。三峡大学机械与动力工程学院硕士研究生。刘 勇，男，1975年生。三峡大学计算机与信息学院教授、博士。杜义贤，男，1978年生。三峡大学机械与动力学院副教授、博士。