任务执行时间不确定下产品开发的多目标优化

田启华 汪汝学 张玉蓉 周祥曼 付君健

(1.三峡大学 机械与动力学院，湖北 宜昌 443002;2.闻泰科技股份有限公司BG2服务器事业部，上海 200030)

产品设计开发过程中，任务执行时间常常受到各种外界因素的影响而变得不确定，由此将直接导致产品开发过程的总工期估算产生较大误差，进而产生不合实际的任务执行方案.

国内外学者针对任务执行工期的不确定性问题进行了大量研究.例如，Elmaghraby[1]发现用平均值替换随机变量来规避项目中各种参数的不确定性，可能会在成本估算和基于成本估算的投标中出现错误;陈卫明等[2]应用统计学的三点估计法来解决产品开发中任务执行工期的不确定性问题，建立了动态环境下基于混合迭代的耦合集求解模型;Lombardi等[3]通过利用优先级约束发布(PCP)的离线/在线混合技术，解决了存在持续时间不确定性的多任务应用程序的可预测和有效的非抢占调度问题;施骞等[4]着重分析了两种概率型调度方法的研究现状;田启华[5]等研究了动态环境下任务工期不确定性对产品开发过程的影响，利用反馈控制原理对并行耦合任务迭代过程进行动态调节;耿苏杰等[6]以任务工期和发布时间分别描述项目内部与外部环境不确定性对项目实施的影响，并采用模糊数进行参数表示，利用蚁群优化算法证实该研究所得到的预防调度方案可以保证项目顺利完工的概率高且完工时间更短;Liu等[7]针对具有初始环境信息不完全、并发执行和执行时间不确定等特点的应急任务规划问题，提出了一种具有不确定持续时间的有条件时态HTN规划的范例;Li等[8]研究了任务执行时间不确定条件下雾队列系统中实时任务的资源分配与任务卸载，利用机器学习方法对任务执行时间的上限和下限进行预测;田启华等[9]建立了工期不确定条件下区间型多目标优化数学模型，采用改进的NSGA-Ⅱ求解，得到了任务调度方案的Pareto最优解集，等等.

但目前大多数针对任务执行时间不确定性的研究，没有充分考虑不确定因素在迭代过程中的影响.因此，面对产品设计开发中的耦合问题和任务执行时间不确定性问题，提出新的解决方法以及任务调度求解模型，以实现资源的合理分配和产品开发的工期和开发成本多目标优化，是人们十分关注的.本文针对产品开发过程中存在任务执行时间不确定性问题，采用六点模糊数来描述产品开发中任务的执行时间，结合任务调度中的混合迭代模型，以开发时间和开发成本为目标，研究任务时间不确定下的优化问题.

1 基于六点模糊数的不确定条件下任务完工时间的描述

在产品开发过程中处理任务执行时间不确定问题时，项目管理者一般都是先用三点估计法[10]或区间数表示法[11]将其转换为确定性的优化问题，再进行求解.

三点估计法和区间数表示法得到的结果与实际产品开发的结果相比误差较大.因此人们引入模糊数来表示任务的完工时间.模糊数的表示方法有多种，目前在实际工程项目上运用较多的有三角模糊数、梯形模糊数和六点模糊数.六点模糊数所包含的信息较多，隶属度函数图复杂，能精确地反映不确定信息，分析结果与实际情况往往差异较小.因此，本文采用六点模糊数来表示任务完工时间的不确定.

根据文献[12]，设为一个模糊数，={(x，u(x))|x∈R}，其中u(x)为的隶属度函数.给定任意一个数a∈[0，1]能得到M~={x|u(x)≥a}，称为模糊集的a水平集.六点模糊数)是一个分阶段性模糊数表示任务估计最小完工时间表示任务估计最大完工时间.区间内为任务完工工期最有可能的取值.区间为任务完工工期可能性较大的取值，λ表示可能性系数.可以由企业指定较好的水平集来代表不确定的数据.若u(x)=1，表示指定的变量x必然属于集合.

现用变量x表示任务估计完工的时间，其完工工期的不确定性用六点模糊数表示;u(x)表示任务完工工期的各种可能性程度，其隶属度函数图和隶属度函数分别如图1和式(1)所示.

图1 六点模糊数的隶属函数图

为了判断工期长短及优化过程的作用，需要比较相应的六点模糊数的大小.通过积分法推导出六点模糊数的清晰化函数，并将清晰化函数的值定义为六点模糊数的度量指标[13]，见式(2).通过比较相应六点模糊数的度量指标来比较其大小.

在产品开发过程中，每个任务都有一个完工时间的模糊工期，并且六点模糊数所对应的6个变量可以根据企业以往产品数据及工程师的开发经验给出大概估计，集合6个可能的完工工期估计值即可构成一个模糊数来表示一个任务的执行工期.

2 混合迭代下多目标优化模型的建立

2.1 产品开发中任务调度混合迭代模型

产品开发过程中任务迭代的方式和执行关系可分为并行迭代、串行迭代和混合迭代.在并行迭代中资源有限的条件下，不能同时完成执行;而在串行迭代中，所有任务按顺序执行，产品总周期大大延长;混合迭代结合了并行迭代和串行迭代的优缺点，根据任务间依赖强度关系将任务划分为一个个任务集，即任务分布方案，然后根据任务分布方案来分阶段地执行任务，该迭代方式可减小不必要的迭代，减小总工作量和产品工期.

根据文献[14]，定义一个工作列向量u，其n个子向量分别表示n个相应任务所需要完成的工作量;ui表示第i次迭代时相关任务所需要做的工作量，假设任务的迭代方式为并行迭代，则每个任务初始都需要完全执行，因此初始工作向量u0的子向量全部为1.由此可推得每次迭代所有任务相应的工作量为:

式中:A为相应任务间的返工量矩阵.

则并行迭代条件下，设整个产品开发过程中每个任务的工作总量为列向量U，其为每次迭代相应任务的工作量求和，即:

式中:N为总的迭代次数，根据文献[15]，当N→∞时，如果矩阵A的最大特征值小于1，则:

设完成每个任务所需要消耗的时间总量为列向量G，则:

式中:W为任务工期矩阵.

根据任务分布方案，将所有任务分成多个阶段来执行，引入任务分布矩阵Ki.Ki为主对角线矩阵，其对角线上的元素为1或0，用来控制任务是否执行.首先执行第1阶段的任务，然后执行第1阶段的返工和第2阶段的初始任务，以此类推直到所有阶段的任务全部执行.将任务分布矩阵代入式(6)得混合迭代条件下各个阶段完成相应任务所需要消耗的时间总量列向量Gi:

式中:m为总的阶段数，任务分布矩阵Km的定义为:

2.2 混合迭代下多目标优化模型的建立

2.2.1 优化目标的确定

对于产品的开发工期，每个迭代阶段内任务集是并行执行的，其耗费的时间是相应迭代阶段内所用时间最长的任务所耗费的时间.用T表示产品的开发工期，并可以将计算得到的总工期T用六点模糊数表示为，则有:

对于产品开发成本，本文用整个产品设计开发过程中所需要做的总工作量来衡量产品的开发成本.而产品开发的工作总量是所有迭代阶段中每个任务的工作量总和.根据2.1节可以得到产品的开发成本C，并且可以将计算得到的总成本用六点模糊数表示为，则有:

2.2.2 评价函数构造

为了获得产品开发时间和开发成本的最优调度方案，本文采用六点模糊数来表示任务的完工时间和成本，并引入权重系数ω.假设工期和成本的权重系数分别为ω1和ω2，ω1+ω2=1，ω1≥0、ω2≥0，其值可由企业决策者根据实际产品开发中的情况来选择.优化后的工期为，成本为，由于工期与成本单位不同，因此用对工期T和成本C做无量纲化处理.用Q来表示产品开发优化后结果的可信度，则定义:

2.2.3 优化模型的建立

对企业来说，要提高自身市场竞争力，就必须缩短产品开发工期和减少开发成本，但实际上一般很难存在两个指标都同时达到最优的任务调度方案.因此产品开发任务的调度问题属于多目标优化问题.

以任务分布方案即矩阵Km(m=1，2，3，…，n)为设计变量，假设不考虑资源约束的问题，在任务执行工期不确定的条件下，基于模糊理论的混合迭代下多目标优化模型可以描述为:

式中:n为总任务数;N为总迭代次数;m为划分的阶段数;g为1～n阶段任务之和;qi为第i阶段任务的个数，1≤qi＜n且qi∈Z.

3 多目标优化模型的算法求解步骤

改进型非支配排序遗传算法(NSGA-Ⅱ)[16]采用染色体交叉和变异操作，保留优良个体的特性，淘汰适应度较低的染色体，从而可以对问题进行优化求解.基于NSGA-Ⅱ的多目标优化算法求解的流程如图2所示.其中n为迭代步数;N为累计的迭代步数.

图2 遗传算法的实现过程

Step 1:随机生成一定数量的目标染色体，并将染色体I的长度设为n，I=[λ1，λ2，…，λi].其中，i为总的任务数，λ的数值表示对应任务所在的执行阶段.例如一条染色体的编码为[2，3，1，5，3，2]，编码位上的数值最大为5，表示该过程一共分5个执行阶段，任务1和任务6在第2阶段执行.任务2和任务5在第3阶段执行.不同编码的染色体聚集形成初始种群Pn，始种群构成一组混合迭代下的任务分布方案，其需要满足两个条件:

①每条染色体的编码位上的数值需涵盖1，2，…，S的所有数，保证不存在缺失阶段造成任务分布方案失效的情况;

②每条染色体的编码位上的数值排序不能相同，以保证不存在重复的染色体即相同的任务分布方案，导致增大计算工作量.

Step 2:种群中的每条染色体都有一个适应度，而适应度值是由非支配等级和拥挤度这两部分来决定的[17].通过非支配排序和拥挤度计算后，可以定义其适应度并由此选择较好的任务分布方案，本文定义算法的适应度函数为:

Step 3:从初始种群中选择适应度大的个体，按照一定的概率将他们的部分染色体片段相互交换，即交换部分任务执行阶段数，形成新的个体.例如:随机选取的交叉位置为第2位和第7位两个交叉位置，操作方法如下:

得到新的任务执行方案A和B:

初始种群或交叉后的种群中出现任务阶段数空缺或形成单一阶段，对单阶段的个体进行剔除，并对阶段数空缺的个体进行随机变异以满足要求.例如:变异位置为第2位、第4位、第9位和第12位，操作方法如下:

经过交叉变异操作后得到新的任务分布方案，还需要判断是否满足条件.

4 实例分析

4.1 问题描述

以某四连杆门座起重机的变幅机构的开发任务[18]为例，通过利用设计结构矩阵(DSM)对其耦合任务集进行划分后，该变幅机构开发过程主要包括8个设计任务:A:象鼻梁设计;B:臂架设计;C:对中小杠杆设计;D:对重设计;E:变幅传动布置设计;F:变幅电动机设计;G:变幅减速器设计;H:螺杆传动设计.其相应耦合任务间的返工量如图3所示.

图3 变幅机构开发过程的任务返工量信息

由2.1节可知，其表示的是相应任务间因耦合关系而造成的不确定条件下各任务的返工量大小，例如表中1行2列的0.3表示的是任务A在任务B之前执行，任务B对任务A的结果不满意或不相容，任务A需要做30%的返工量;表中0表示对应两任务间没有耦合关系.则其任务返工量矩阵为:

基于第1节所描述的不确定条件下任务工期的六点模糊数表示法，根据以往开发过程的历史数据及相关人员的设计经验可初步确定各任务完工时间的六点模糊数，见表1.

表1 任务完工时间的六点模糊数

根据这些信息，以该变幅机构开发过程的任务分布执行方案为变量，并以其开发成本、开发工期为优化目标，利用NSGA-Ⅱ算法对该实例问题进行求解.

4.2 问题求解

本文以Matlab R2017b软件为平台，编写NSGA-Ⅱ算法程序.算法的初始种群大小设为500，最大迭代步数为50，交叉率为0.8，变异率为0.5，问题的处理及分析过程如下.

4.2.1 任务执行阶段数的选取

取工期和成本的权重比为1∶1，即σ=0.5.由表1可提取6组模糊工期:

由于该变幅机构一共有8个设计任务，将任务的执行阶段数依次设置为1、2、3、4、5、6、7、8，分别代入遗传算法进行运算，在相应的执行阶段数下分别取其最优任务执行方案，得到各个模糊工期和模糊成本，见表2.

表2 不同执行阶段数条件下的优化结果

不同阶段数的执行条件下，算法的收敛曲线如图4所示.从图中可以看出该算法均在50代之前收敛，具有较好的收敛特性，求解效率高.

图4 适应度收敛曲线图

为了比较各个执行阶段数条件下优化后的模糊工期和模糊成本的大小，采用第1节所述的积分值法，取λ=0.5，分别求出优化后的每组模糊工期和模糊成本的度量指标见表3.

表3 不同执行阶段数条件下优化结果的度量指标

表3中不同任务执行阶段数条件下，将其优化后的模糊工期和模糊成本度量指标进行对比，如图5所示.

图5 不同执行阶段数下优化后工期和成本的对比

由图5可知，随着任务执行阶段数的增加，优化后的总工期也一直增加，其增加的速率先减小后增大，在阶段4～5之间最小;而优化后的成本逐渐减少，其减少的速率也是先减小后增大，在阶段4～5之间最小.因此管理人员可根据对成本和工期的权重比要求的不同，选择将所有任务划分为4个阶段执行或者划分为5个阶段执行.

4.2.2 任务执行阶段数确定的条件下最优任务分布方案的选取

首先定义任务分布方案的执行阶段数为5，分别将6组模糊工期带入算法中进行求解，可得6组Pareto解集，如图6所示，其具体运算结果见表4.

图6 执行阶段数为5时模糊工期下的Pareto解集

表4 运算结果

从表4的数据结果中可以看出，各任务的模糊执行工期不同将会直接导致其Pareto解集的不同及相应任务分布方案的不同.因此，本文利用六点模糊数来描述每个任务的执行工期和成本，将6个点的模糊工期和模糊成本分别代入优化模型进行寻优.从表4的6个任务模糊工期组中各选出两组任务方案，并从运算结果中提取出两组任务执行方案一致的Pareto解，见表5.

表5 优化后的产品开发方案

表5中任务方案a为(4 4 1 2 5 3 4 5)，表示任务C在第1阶段执行，任务D在第2阶段执行，任务F在第3阶段执行，任务A、任务B和任务G在第4阶段并行执行，任务E和任务H在第5阶段并行执行;任务方案b为(4 5 1 2 4 3 4 5)，方案b与方案a的区别在于任务B和任务E的执行阶段数的不同，方案b中任务B在第5阶段才开始执行，而任务E在第4阶段就开始执行.

为了选取最优任务执行方案，利用优化结果可信度来判断，则由公式(12)可得优化后工期的可信度，见表6.

表6 优化后工期的可信度

由表6可得，对比a和b两种优化方案，方案a(4 4 1 2 5 3 4 5)的可信度更好，因此在任务执行阶段数为5的条件下，选取方案a作为产品开发的最优执行方案.

本文两组任务方案的选取在其Pareto解中靠中间，工期和成本的权重接近1∶1，而在实际的产品设计开发中，企业管理人员可以根据对优化工期和成本的着重点的不同来从表3的运算结果中选取对应的方案组，最终根据优化方案的可信度来选取最优任务执行方案.

5 结 论

本文对产品设计开发过程中任务执行时间不确定的问题进行了研究，研究表明:

1)通过引用六点模糊数，结合产品开发中任务调度混合迭代模型，能够获得基于模糊理论的混合迭代下多目标优化模型，从而减少产品的开发时间，降低开发成本.

2)通过引入NSGA-II算法和积分值法，可以有效地解决任务时间不确定下产品开发多目标优化求解问题.

3)为了最大限度减少产品的开发时间，降低开发成本，应合理调整工期和成本权重，选择合适的权重.