基于NSGA-Ⅱ的产品开发任务调度多目标优化

田启华 明文豪 文小勇 杜义贤 周祥曼

1.三峡大学机械与动力学院，宜昌，443002 2.湖北江山重工有限责任公司民品事业部，襄阳，441100

0 引言

产品开发是一个求解实现产品功能、满足各种技术和经济指标，从可能存在的所有方案中确定综合最优方案的过程。随着市场竞争的日益激烈和科学技术的发展，人们对产品开发的要求越来越高，产品开发变得日益复杂。设计任务间的耦合性使设计过程出现反复和迭代，延长开发时间，增加开发成本。耦合设计任务的开发时间和开发成本与任务调度有直接关系，子任务的执行顺序会引起后续子任务不同的返工量，故需合理安排每个子任务开始执行的时间。任务调度研究的问题是确定项目的子任务、安排任务进度、编制完成任务所需的资源预算等，目的在于保证产品开发能够在合理的工期内，以尽可能低的成本和尽可能高的质量完成[1]。

近年来，围绕产品开发任务调度问题的研究逐渐受到重视，并取得了一些研究成果。CHEN等[2]将量化搜索算法用于解决多个虚拟企业协同下的设计任务调度问题；武照云等[3]采用加权系数法和极差变换法建立了产品开发任务分配多目标优化的目标函数，采用基于时序逻辑关系的动态分配蚁群算法进行优化计算；蒋增强等[4]提出了基于多目标优化的产品协同开发任务调度理论，根据企业对产品开发的时间、成本及质量重视程度，确定三者各自的权重，以三者的加权指数和为多目标优化函数，得出最优的任务调度方案。加权系数法虽然可以在很大程度上降低求解问题的难度，但只能得到一个Pareto解，而且实际应用中的权重系数确定完全依赖于专家，主观依赖性较强。陈庭贵等[5-6]将产品开发的成本和时间单独考虑，获得了最优成本和最优时间的任务分布方案，但没有考虑成本与时间共同优化的矛盾性和竞争性。田启华等[7]采用约束法，将产品开发的成本作为一个主要的优化目标，给产品的质量和开发时间设定一个上下界(当作约束条件)，对问题进行了优化求解。这种处理可以降低求解问题的难度，但本质上相当于单目标优化，且主要优化目标取决于决策者的喜好。田启华等[8]、杨利宏等[9]将传统的遗传算法引入到产品开发任务分配的优化，以时间为优化目标，但没有考虑任务分配对开发成本的影响，优化的目标函数不够完善。

遗传算法作为一种有别于传统的搜索算法，在求解组合优化领域的非确定性多项式(non-deterministic polynomial，NP)问题上显示出强大的搜索优势[9]。非支配排序遗传算法[10](non-dominated sorting genetic algorithm，NSGA)根据个体之间的支配和非支配关系分层实现，采用它求解得到的非劣最优解分布均匀，但其计算复杂度高，无精英策略，并且对共享参数的依赖性较大，而改进的非支配排序遗传算法(non-dominated sorting genetic algorithm-Ⅱ，NSGA-Ⅱ)[11-12]采用快速非支配排序方法，引入拥挤距离保证Pareto解集的均匀性和多样性，降低了算法的时间复杂性，且带有精英策略，在进化过程中不会造成最优解的丢失，NSGA-Ⅱ算法比NSGA算法更加优越。多目标遗传算法在许多工程优化设计问题中都有运用[13]，但在产品开发任务调度方面应用较少。鉴于此，本文基于NSGA-Ⅱ对产品开发任务调度问题中的时间和成本进行多目标优化，根据执行时间和成本对个体进行非支配排序和拥挤距离的计算，以保证Pareto最优解集的均匀性和多样性，从而最终得到最优的任务调度方案。

1 产品开发任务调度的多目标优化模型建立

1.1 问题描述

产品开发任务的调度对开发的时间和成本有很大影响，因此需要对任务进行合理调度。一般来说，产品开发任务调度是一个混合迭代过程。一个有P个任务、n(n>2)个阶段的混合迭代模型的工作过程描述如下[6]：将P个任务分成n个工作小组；首先，第一阶段执行第一个小组的任务；然后，第二阶段执行第二个小组的任务和第一小组任务的返工，此时只有第二个小组的任务有初始工作；第三阶段执行第三个小组的任务和第一、二小组任务的返工；以此类推，经过n个阶段，直到第n个小组的任务全部执行完毕，并完成前面n-1个小组的返工。完成当前阶段的小组任务后，前面小组的返工都会在当前阶段完成。第一阶段任务执行所需时间T1和成本E1分别为

(1)

E1=‖W(I-K1AM1K1)(I-K1AK1)-1K1u0‖1

(2)

(3)

第二阶段任务执行所需时间T2和成本E2：

(4)

E2=‖W(I-K2AM2K2)(I-K2AK2)-1(K2-K1)u0‖1

(5)

(6)

依此类推，第n阶段任务执行所需时间和成本：

(7)

En=

‖W(I-KnAMnKn)(I-KnAKn)-1(Kn-Kn-1)u0‖1

(8)

(9)

P个任务执行完毕所需总时间T和总成本E分别为

(10)

(11)

从以上的模型可以看出，任务之间的耦合关系和每个任务的执行周期确定后，影响产品开发过程的总时间T和总成本E的因素只有任务的调度方案。

1.2 以时间和成本为优化目标的数学模型的建立

在任务工期确定和不考虑资源约束的条件下，产品开发任务调度问题多目标优化的目标为总开发时间T最短、总开发成本E最低，约束条件如下：

(12)

式中，P为总的任务数；qi为小组i中任务的个数，P>qi≥1且qi∈Z；n为组数。

2 基于NSGA-Ⅱ的产品开发任务调度的多目标优化求解

2.1 Pareto进化算法求解步骤

基于NSGA-Ⅱ算法的产品开发任务调度问题多目标优化的一般步骤如下：首先，生成大量的不同任务调度方案，计算出它们所需的执行时间和成本，淘汰其中时间和成本均较大的方案；其次，根据不同的执行时间和成本，对保留下来的任务分布方案进行非支配排序和拥挤距离计算；再次，根据个体的序值和拥挤距离选出父本，进行交叉变异运算，得出新的任务分布方案，并计算出时间和成本；最后，将新生成的任务分布方案与之前保留的任务分布方案进行非支配排序和拥挤距离计算，以保证Pareto解的多样性和均匀性。以此类推，直至达到最大的遗传代数，输出Pareto最优前沿。

根据产品开发任务调度多目标优化问题的特点，NSGA-Ⅱ算法的具体实施方法如图1所示。

图1 基于NSGA-Ⅱ算法的流程图Fig.1 Flow chart based on NSGA-Ⅱ algorithm

2.1.1染色体的编码

产品开发任务调度混合迭代模型中，任务划分的阶段数和任务的分布情况是影响时间和成本的重要因素，所以在选择染色体的编码方式时，个体的阶段数和任务的分布情况是要突出表现的特征。本文采用整数编码的方法，以问题解{x1,x2,…,xN}的编码形式表示染色体(或称个体)，各编码位是整数，xN对应任务N，xN的值表示任务N所在的阶段。假设当前任务划分的阶段数为n，用1到n之间的一个正整数来表示任务所在的阶段，染色体中每个编码位取值为1、2、...、n中的一个，不同的数字代表该任务处在不同阶段，且染色体的编码位上共有n个不同的取值，染色体的长度由耦合集中任务的个数N决定(n≤N)。染色体{1,1,3,2,2,1,3,4,2,1,3}表示由11个任务的耦合集所构成的四阶段混合迭代模型的一种任务调度情况，其中，从左至右的第1、2、6、10个位置的数值为1，这表示任务1、2、6、10属于第1阶段，以此类推，任务4、5、9属于第2阶段，任务3、7、11属于第3阶段，任务8属于第4阶段。染色体编码方式确定以后，不同的任务分配有唯一的染色体与之对应，每一个染色体都对应着一个产品开发任务调度方案。

2.1.2交叉和变异操作

运用二元锦标赛选择的方法，从种群中选出适应性较高的个体加入交配池，为后续的交叉和变异做准备。根据以上的染色体编码方式，设计与之对应的交叉变异操作。以2个个体的交叉为例，首先，从经过选择操作得到的新种群中随机选择2个父本P1和P2，假设这2个父本的染色体有m个基因位，将交叉操作分两步进行：①在染色体上随机产生2个交叉的位置r1和r2(r1、r2∈{1，2，…，m})；②将P1和P2上两个交叉位置r1、r2间的基因互换，生成2个子个体O1和O2。多阶段模型中，每个任务所在的阶段必须确定，且每个阶段至少分配到一个任务，这些要求在染色体上的表现如下：对于一个染色体(染色体最大编码数为n)，从1到n的每个数字都要出现在染色体中，即任务的阶段数保持连续。对染色体交叉操作的过程中，可能出现某些阶段的基因缺失。多阶段模型出现某阶段基因缺失，将导致迭代无法进行或出现错误。针对这个问题采用以下的方法予以修正：在子个体中用遗失的基因替换非交叉区的重复基因。例如，父本P1={1,3,1,3,1,2}、P2={1,2,2,1,1,3}交叉的位置点r1=4，r2=6，则生成子个体O1={1,3,1,1,1,3}、O2={1,2,2,3,1,2 }，由于子个体O1缺少阶段数2，故O1修正为{2,3,1,1,1,3}，而O2不用修正。

多阶段迭代模型可以在个体的染色体上随机选择2个基因的位置，然后互换这2个位置上的基因作为变异操作。具体过程是选择一个父本P3，在P3的染色体上随机产生2个不同位置点r3和r4，互换两位置上的基因，生成子个体O3。

2.2 Pareto最优解的选取

为了便于产品开发决策者从众多任务方案中确定产品开发的最优执行方案，本文基于模糊优选法[14]，对NSGA-Ⅱ求得的多目标优化问题的Pareto最优解集进行优化，确定最优折中解。建立Pareto集优选的过程如下。

首先，计算出Pareto集合中个体i的第j个目标函数值所占比重δij：

(13)

式中，fjmax、fjmin分别为目标函数值集合中的第j个目标函数值的最大值和最小值；fij为个体i的第j个目标函数的取值。

其次，对Pareto集中的每一个个体进行标准化，得到个体i的满意度：

(14)

式中，Ω为Pareto集中的个体数。

最后，取标准化后满意度最大的个体的满意度δimax作为Pareto集中的最优解，其中，δmax=maxδi。

3 仿真测试与实例应用分析

3.1 算法仿真测试

为了说明该算法的优越性，本文采用典型多目标测试函数中的2个测试函数ZDT1和ZDT2进行仿真[15]。

参数设置如下：种群数量p=100，遗传迭代步数g=150，交叉概率pc=0.9，变异概率为0.1。

(1)ZDT1具有凸的Pareto最优前沿：

使用NSGA-Ⅱ计算ZDT1，仿真结果如图2所示。

图2 使用NSGA-Ⅱ求解ZDT1Fig.2 Solving the ZDT1 with NSGA-Ⅱ

(2)ZDT2具有非凸的Pareto最优前沿：

minf1(x)=x1

minf2(x)=g(x)*[1-(f1(x)/g(x))2]

使用NSGA-Ⅱ计算ZDT2，仿真结果如图3所示。

图3 使用NSGA-Ⅱ求解ZDT2图Fig.3 Solving the ZDT2 with NSGA-Ⅱ

分别对比图2和图4、图3和图5可知，使用NSGA-Ⅱ得到的结果大致与ZDT1、ZDT2的理想Pareto前沿重合，且得到了分布均匀的最优解集。因此，可以得出本算法对于求解两目标优化效率高、性能好的结论。

图4 ZDT1理想Pareto前沿Fig.4 Ideal Pareto front of ZDT1

图5 ZDT1理想Pareto前沿图Fig.5 Ideal Pareto Front of ZDT2

3.2 实例描述

以某汽车引擎罩部件的设计开发过程为例说明上述模型在实际生产中的应用，并验证该方法的有效性。文献[16]使用设计结构矩阵对该开发过程进行建模，在划分、割裂运算后，找出众多子任务中的耦合集(包括由20个和14个子任务组成的大耦合块、由3个任务组成的小耦合块)，本文选择由20个子任务组成的耦合块进行分析。

由该20个任务间的耦合信息可得任务返工量矩阵A和任务执行周期矩阵W；根据任务间的依赖强度确定任务的返工量，例如当任务D设计完成后，在随后的迭代阶段，任务J的26%(对应矩阵A中第四列数据0.26)需要额外的返工；矩阵A空白位置的元素取值均为0。

任务执行周期矩阵W为

W=diag(15，60，40，40，15，2，1，5，30，1，1，5，5，10，20，5，2，2，15，5)

A B C D E F G H I J K L M N O P Q R S T

3.3 任务调度方案优化

按照本文给出的多阶段混合迭代模型，以执行时间最短、成本最低为目标，以任务的分布方案为设计变量，在满足阶段划分的约束条件的前提下，对汽车引擎罩开发任务调度的多目标优化问题进行求解，得到该问题的Pareto前沿(最优解)。按照前面提出的整数编码的规则，由耦合集的任务个数20，确定染色体的长度为20，假设耦合集中的任务被划分成n个阶段，染色体上的每个编码位用1～n的自然数表示。该自然数表示任务通过随机组合的方式得到的初始种群，交叉和变异运算按照本文给出的方法操作。为了确定算法的具体参数并说明不同参数对优化结果的影响，利用MATLAB进行了多次试算，确定了相关参数的大致范围。将任务的阶段数确定为13，采用控制变量法，每次改变种群数量、遗传迭代步数和交叉概率三者中的一个，可得初始种群数量对优化结果的影响，见图6。图中，d*p表示天*人。对比可知，初始种群较大时，获得的Pareto解多，且分布相对均匀；遗传迭代步数对优化结果的影响见图7，对比可知，迭代步数较小时，Pareto最优解相对比较集中，容易造成最优解的丢失；染色体交叉概率分别设置为0.5、0.7和0.9，求解结果见图8，对比可知，染色体交叉概率对优化结果影响很小，在0.5～0.9范围内均可。分析图6、图7可知，当种群数量、遗传迭代步数足够大时，可得到稳定且分布均匀的Pareto最优前沿，但种群规模太大时，结果难以收敛且浪费资源，遗传迭代步数太小，算法不易收敛；步数太大，算法已经熟练或种群过于早熟，继续进化没有意义，因此这两个参数可以根据具体问题进行调整。

图6 种群数量对优化结果的影响(g=100,pc=0.9)Fig.6 Influences of population size on theoptimized result(g=100,pc=0.9)

图7 遗传迭代步数对优化结果的影响(p=1 000,pc=0.9)Fig.7 Influences of Genetic iteration steps on the optimized result(p=1 000,pc=0.9)

NSGA-Ⅱ的参数经过反复试算，设置如下：初始种群P0中个体的数目p=1 000，遗传迭代步数g=100，染色体交叉概率为0.9，染色体变异概率为0.1。图9所示为利用MATLAB进行多目标优化仿真的结果，由于事先不能确定任务划分为多少阶段，时间和成本才会出现综合最优，所以把1～20阶段每次运行MATLAB得到的优化结果保存下来，并对时间T(单位：天，用d表示)和成本E两个优化目标进行非支配排序，获得的Pareto前沿结果。

图8 染色体交叉概率对优化结果的影响(p=1 000,g=100)Fig.8 Influences of chromosome crossover probability on the optimized result(p=1 000,g=100)

图9 多目标优化的Pareto前沿Fig.9 Pareto front of multi-objective optimization

由图9以看出， NSGA-Ⅱ计算出的Pareto解分布均匀，大体上可以看出Pareto解的开发周期和成本成反比的关系。这说明了产品的开发时间、开发成本这两个目标的矛盾性。图9中的所有点构成了Pareto最优集合，可以看出，AB段内，时间的变很小化就会引起成本的很大变化；CD段内，成本的很小变化就会引起时间的很大变化，它们都不是很好的选择。因此决策者可以根据实际情况从BC段集合内进行权衡，获得时间和成本都能接受的产品开发任务调度方案。

为了说明本文算法的优越性，采用常规的多目标遗传算法进行比较，选择相同的初始参数，先分别求出时间和成本的最小值、最大值，使用MATLAB仿真求得Tmin=97.10 d，Tmax=297.84 d，Emin=315.44 d*p，Emax=473.10 d*p，量纲一化后的综合目标函数为

(15)

其中，w1、w2分别为时间T和成本E的权重系数且w1+w2=1。调整w1、w2的结果如表1所示，表1中的方案下方的数字代表对应任务所在的执行阶段，从左至右，对应任务A到T(共20个任务)所在的阶段，如第一个数字3表示任务A在第3阶段执行。

表1 多目标遗传算法优化的任务调度方案

使用常规的多目标遗传算法求解该问题时，结果依赖于评价函数的选择，每次只能得到一种任务调度方案，无非支配排序和精英保留制，进化过程可能会造成最优解的丢失，可供选择的方案较少；采用NSGA-Ⅱ算法，一次运行就能得到多种方案，有精英保留制，不会造成最优解的丢失，该算法的收敛性和鲁棒性好，产品开发决策者可以根据实际情况或偏好目标选择最优的任务调度方案。

现根据2.2节提出的模糊集合优选的方法进行产品开发过程任务调度多目标优化的Pareto选优，得到最优的任务调度方案见表2，表2分别给出了时间最短、成本最低、时间和成本综合最优的任务分布方案，以及所有解的平均时间T和平均成本E。由表2可以看出，最优任务分布方案的时间和成本比Pareto解的平均时间149.47 d，成本358.09 d*p都小，说明了该算法的有效性。

表2 时间最短、成本最低、最优任务调度方案阶段号

由表2知，时间和成本综合最优的任务分布方案是将20个任务分成了6个阶段，分别是：第1阶段执行的任务是内外观的确定(R)；第2阶段执行的任务是进行概念设计(F)、系统尺寸估计(J)、成本估计(K)、工艺评估(T)；第3阶段执行的任务是CAD建模(G)；第4阶段执行的任务是确定传动系统布置(A)、确定主截面(D)、检验功能性质(H)、检查外部面板的接触面(N)、设计铰链(O)；第5阶段执行的任务是初始装配方案设计(L)；第6阶段执行的任务是确定比例与受力性能(B)、确定连接点的受力性能(C)、产生结构要求(E)、CAD模型进行初始设计(I)、估计销的载重(M)、初步估计加工和装配成本(P)、成本分析(Q)、市场定位及分析(S)。最优方案如图10所示，图中，对角线元素为对应任务的执行周期，非对角线元素为对应任务的返工量，任务从左到右依次执行，相同阶段的任务用同一种颜色表示，可以清楚看到每个阶段增加的新任务，以及新任务和之前执行的任务的返工情况。

图10 优方案的任务分布图Fig.10 Task distribution of the optimal solution

4 结语

本文在产品开发任务调度混合迭代模型的基础上，构建出产品开发任务调度的多目标优化数学模型，引入NSGA-Ⅱ，以产品的开发时间和产品的开发成本为目标函数，对产品开发任务调度问题进行了多目标优化求解，得到多目标优化的Pareto前沿(最优解)。在此基础上，结合模糊优选法对多目标优化得到的Pareto解集进行选优，确定了产品开发任务调度的最优执行方案。