资源约束下产品开发任务调度的多目标优化

2022-03-11田启华黄佳康明文豪杜义贤周祥曼付君健

计算机集成制造系统 2022年2期

田启华,黄佳康,明文豪,杜义贤,周祥曼+,付君健

(1.三峡大学机械与动力学院，湖北宜昌 443002； 2.湖北亿纬动力有限公司方形三元技术中心，湖北荆门 448000)

0 引言

产品开发的任务调度由于受到来自企业内部技术人员、设备工具和资金等资源约束，原来可以执行的任务发生延迟执行或不能执行，例如技术人员调动、设备工具损坏、资金链中断等，都会使产品开发任务调度受到约束。针对资源约束下的任务调度问题，国内外学者开展了一些研究，并取得了相应的成果。KARA等[1]提出一种多项目调度启发式算法，用于解决资源约束下的多项目调度问题；秦旋等[2]构建了以生产完工时间和惩罚成本为目标的生产调度数学模型，设计了一种新颖的多目标混合共生生物搜索算法(Multi-Objective Hybrid Symbiotic Organisms Search Algorithm，MOHSOSA)对模型进行求解，以合理安排构件的生产顺序和资源配置，达到降低成本、提高生产效率的目的；安晓亭等[3]提出一种带局部搜索的改进蚁群优化算法，用于求解多目标资源受限项目调度问题；徐赐军等[4]提出运用弹性资源特性进行动态调度决策的方法，以解决产品开发中的多个活动冲突问题，其主要根据活动间的时序约束和资源约束特点，分别建立了用以解决时序冲突、资源冲突的模型，并证明了弹性资源约束动态调度决策方法的有效性和可行性；CHEN等[5]在EXCEL仿真计算的基础上，建立了多维模型(MD模型)，用于评估项目的优先级并进行计算，当多个项目的积极效应达到最大，人员能力满足任务要求时，获得了最佳人力资源配置；徐赐军等[6]根据不同的资源约束和强耦合的设计活动特点，提出一种资源约束的产品开发过程集成模型；GAO等[7]对于资源受限的项目调度问题，提出一种改进的关键路径调度算法；肖人彬等[8]提出一种资源均衡策略的耦合集求解方法，以解决产品开发中资源约束下的资源分配问题，从而提高了资源的利用率，缩短了产品开发任务调度的迭代时间；项前等[9]提出一种改进的动态差分进化参数控制方法和双向优化问题调度算法，以解决资源受限的项目调度问题；王静等[10]建立了一种求解资源受限项目调度模型的差分进化人工蜂群算法，获得了约束资源的分布以及资源和项目时间的优化方案；TAHOONEH等[11]采用人工蜂群算法解决随机资源约束项目调度问题，仿真结果表明该算法能更有效地解决随机资源约束项目调度问题；LIN等[12]构建了多资源约束下多项目任务调度最短延迟时间的数学模型，根据资源调度任务和项目内部时序关系，结合启发式算法，解决了多资源约束下的多项目任务调度问题。上述文献从不同方面对资源约束下的任务调度问题进行了研究，有些针对非耦合设计任务调度建立的优化模型，任务数量较少且任务间的关系较简单，不适用于存在大量迭代和返工情况的耦合设计任务调度优化，如文献[1-6]；有些优化目标单一，或采用其他方法将多目标优化问题转化为一个综合的目标，评价指标较单一，如文献[7-12]；文献[13]虽然建立了以产品开发时间和开发成本为目标的任务调度多目标优化模型，并采用带精英策略的快速非支配排序遗传算法(fast elitist Non-dominated Sorting Genetic Algorithm，NSGA-Ⅱ)求解，确定了任务调度方案的Pareto最优解集，然后采用模糊优选法得到最优的任务调度方案，但是未考虑任务调度中存在的资源约束问题。另外，目前对耦合设计任务调度中客观存在的学习与遗忘效应问题的研究较少。

资源约束下的产品开发任务调度，要求在满足资源约束的条件下合理调度各项任务，最大化利用资源，对开发时间、开发成本等多个目标进行优化。产品开发中执行每项任务都会占用相应的资源(如设备、人力和资金等)，而且资源一般都是有限的，在执行一个或多个任务的同时启动其他任务时，由于当前执行的任务占用了一定资源，可能出现某种或某些资源不足的情况，该任务只能等当前任务执行完毕，所需资源释放后才能开始执行，即任务在执行过程中会受到相关资源约束的影响，导致任务延后执行甚至不能执行。因此，需要及时调整并优化任务调度方案，以使任务在执行时满足资源约束的条件，尽可能缩短开发时间，减少开发成本[14]。

本文针对产品开发过程中存在的资源约束问题，结合多阶段耦合集求解模型，考虑任务执行过程中存在的学习遗忘效应，以开发时间和开发成本为目标，研究资源约束下的产品开发任务调度优化问题。

1 学习遗忘矩阵的构建

对于执行任务的小组人员来说，一方面，随着返工次数的增加，工作经验不断积累，小组人员的工作能力(或工作效率)逐渐提高，即减少了执行同一任务的时间；另一方面，由于工作中断和遗忘而导致经验丢失，小组人员的工作能力相比之前会有所降低，即存在学习遗忘效应[15]。为了研究学习遗忘效应在迭代过程中对执行时间和成本的影响，本文将学习曲线与遗忘曲线相结合进行研究。

假设t(1)为某一任务小组第一次执行任务所需的时间，t(p)为第p次返工执行同一任务所需的时间，结合WRIGHT[16]提出的学习效率曲线，可得

t(p)=t(1)×p-l。

(1)

式中l为学习效率指数，0≤l<1，l取值越大学习能力越强，特别是l=0时表示没有学习效应。学习效率指数可采用同类工作的经验和历史数据，通过学习效率曲线确定。由式(1)可知，随着返工次数p的增加，完成同一任务所需的时间t(p)减小，但WRIGHT[16]指出学习效率曲线存在一个下界，即执行时间不可能无限减小。

同时，遗忘效应也是客观存在的，由于经验被遗忘丢失，完成单位工作量所需的时间会增加。假设在第b次返工时，学习发生了中断(经验遗忘丢失)，t′(a)为某一任务小组第a次执行任务所需的时间，t′(b)为学习中断时第b次返工执行同一任务所需的时间，结合文献[17]，可得遗忘效应曲线

t′(b)=t′(a)×(b-a)f,b>a。

(2)

式中:f为遗忘效应指数，0≤f<1，f取值越小遗忘能力越小，特别f=0时表示没有遗忘效应。遗忘效应指数同样可采用同类工作的经验和历史数据，并通过遗忘效率曲线确定。由式(2)可知，随着返工次数b的增加，执行同一任务的时间t'(b)在增加，但遗忘效率曲线同样存在一个上界，即执行时间不可能无限增加。

对于一个有m个任务的串行耦合集，m个任务对应的每个小组第s次返工的学习效应矩阵L(s)与遗忘效应矩阵F(s)分别为:

式中s1,s2,…,sm分别为存在学习效应和遗忘效应时对应任务的返工量。

一般而言，学习和遗忘是一个概率事件，在任务执行过程中，人员的工作能力可能因学习效应而提高，也可能因外部的扰动、工作中断等遗忘效应而降低。在后续的返工迭代中，根据概率规则，每次随机生成一个0～1之间的数pd，当pd不大于某一λ值时会产生学习效应，否则会产生遗忘效应。综合考虑学习效应和遗忘效应，第s次返工中的学习遗忘矩阵为：

(3)

2 多阶段任务执行时间与成本的计算模型

将产品开发过程中的m个任务划分为n(n>2)个阶段执行，每个阶段至少执行一个任务，而且只有当上个阶段的所有任务执行完后，下个阶段的任务才能开始执行。任务执行中存在迭代返工，用工作转移矩阵WTM(可简写为W)定量表示任务的返工量，W通常包括两部分数值信息，即由两个独立的数值矩阵(任务工期矩阵Z和任务返工量矩阵R)组成[18]，工作转移矩阵W=Z+R。其中：Z为m维对角矩阵，其元素表示该项任务对应的执行时间，其值取决于产品开发前专家根据经验对每个设计任务时间的估计值；R为m维非对角矩阵，元素rij表示任务j完成后引起任务i的返工量，描述迭代过程中任务之间的耦合关系。例如一个有关3个耦合设计任务A，B，C的执行工期矩阵Z和任务返工量R分别为：

Z矩阵表示任务A，B，C独立完成一次分别需要7，6，9个单位时间。R矩阵表示任务A执行结束后，由于任务A，B，C之间存在耦合关系，导致任务B需要重做30%的工作(返工量)，任务C需要重做15%的工作；当任务B完成后，任务A需要重做25%的工作，任务C需要重做50%的工作；当任务C完成后，任务A需要重做40%的工作，任务B不用重做。

由文献[19]并结合学习和遗忘矩阵可以得出，将m个任务分为n个阶段，在执行第1阶段任务的过程中，完成时间最长的任务所需的时间T1和所有任务的开发成本D1分别为：

D1=Etc[QK1(Z(I-K1RdK1)(I-K1RK1)-1K1u0)]。

执行第2阶段任务所需的时间T2和成本D2分别为：

D2=Etc[QK2(Z(I-K2RdK2)

(I-K2RK2)-1(K2-K1)u0)]。

以此类推，执行第n阶段任务所需的时间Tn和成本Dn分别为：

(4)

Dn=Etc[QKn(Z(I-KnRdKn)
(I-KnRKn)-1(Kn-Kn-1)u0)]。

(5)

执行完m个任务所需的总时间T和总成本D分别为：

(6)

3 多目标优化模型的建立

3.1 资源利用率的定义

机械产品开发涉及的工种较多，需要多部门协作和跨学科交流，随着设计任务数量的增加，对资源的数量需求和种类需求更多，为了方便计算并进行仿真，假设：①每个任务执行时所需的资源为一个确定的值；②总的资源一定；③任务执行完后，所占用的资源立即全部释放。

当任务的阶段数确定后，每个阶段由于执行的任务不同，所需的资源数量也不一样。有的阶段并行执行的任务数量较多，资源一般能够被充分利用，甚至可能超过总的资源量，导致有些任务不能执行或延迟执行；有的阶段并行执行的任务数量较少，通常造成资源大量闲置。为了体现任务执行过程中资源的利用率，假设任务{A1，A2，…，Am}所需的资源不可分割(每个任务只有分配一定数量的资源才能执行)，定义资源分配行向量Zy=(Zy1,Zy2, …,Zyn)，资源总量为Zyzl(确定值)，即每个任务执行时需要的资源量为一定值，而且每个阶段只有当该阶段的全部任务所需的资源总和小于或等于资源总量Zyzl时，任务才能并行执行。定义资源的利用率：

第1阶段资源的利用率

Z1=‖K1×Zy1‖/Zyzl×100%；

第2阶段资源的利用率

Z2=‖(K2-K1)Zy2‖/Zyzl×100%；

以此类推，第n阶段资源的利用率

Zn=‖(Kn-Kn-1)Zyn‖/Zyzl×100%。

(7)

由于每个阶段执行的任务不同，资源利用率的差异可能相差较大，设计人员或决策者往往对总资源利用率的期望值较高，而不是某一阶段的资源利用率最高，对此提出资源平均利用率

(8)

3.2 评价函数的构造

为了获得产品开发时间和开发成本的最优调度方案，本文采用多目标理想点法[20]对求得的Pareto最优解集进行选优，该方法在期望度量下，寻求离G*最近的G作为近似值(该优化模型需先分别求出每个目标的最小值)。如图1所示，图中：“*”为目标g1和目标g2的理想点，即两个目标同时达到最小值；“+”和“△”为目标g1和目标g2的实际分布点，显然“△”代表的值比“+”代表的值都大，只需在“+”中寻找距离“*”最近的点，构造评价函数G，

(9)

3.3 多目标模型的建立

在产品开发设计过程中，一般总资源有限，设计人员或决策者会根据以往的设计经验给每个任务分配固定的资源，只要每个阶段所需的资源不超过总量，该阶段的任务即可顺利进行，因此资源约束条件为

(10)

产品开发时间T和开发成本D均为评价任务调度方案优劣的两个重要指标，一般很难有两个指标同时达到最优的任务调度方案，因此资源约束下的产品开发任务调度问题属于多目标优化问题。

由于时间和成本在单位、数量级的差别，本文通过(T-Tmin)/(Tmax-Tmin)和(D-Dmin)/(Dmax-Dmin)分别对T和D进行无量纲化处理，其中：Tmin为时间最小值，Tmax为时间最大值；Dmin为成本最小值，Dmax为成本最大值。为了体现企业决策者对时间或成本的重视和偏好程度，本文在多目标理想点法的基础上引入权重系数w。假设时间和成本的权重系数分别为w1，w2，满足w1≥0，w2≥0且w1+w2=1，其值可由企业决策者根据实际产品开发中的具体情况选择。引入式(10)的约束条件后，资源约束下产品开发任务调度多目标优化的数学模型描述如下：

s.t.

(11)

其中：目标函数的个数为2；m为总任务数，n为划分的阶段数，qi为第i阶段任务的个数，v为1～n阶段任务数之和；1

4 多目标优化模型的求解

4.1 NSGA-II的改进

有别于传统的搜索算法，遗传算法在求解组合优化领域的非确定性多项式(Non-deterministic Polynomial，NP)问题上显示出强大的搜索优势。其中非支配排序遗传算法(Non-dominated Sorting Genetic Algorithm，NSGA)[21]能够根据个体之间的支配和非支配关系分层实现优化，虽然其求解得到的非劣最优解分布均匀，但是计算复杂度高，无精英策略，而且对共享参数的依赖性较大；NSGA-II[22-23]采用快速非支配排序方法，引入拥挤距离保证Pareto解集的均匀性和多样性，降低了算法的时间复杂性，而且带有精英策略，在进化过程中不会丢失最优解，比NSGA算法更优越，已应用于许多工程优化设计问题[24]，但在产品开发任务调度方面应用较少。鉴于此，本文基于NSGA-II对产品开发任务调度问题中的时间和成本进行多目标优化，根据执行时间和成本计算个体的非支配排序和拥挤距离，以保证Pareto最优解集的均匀性和多样性。

NSGA-II虽然优点较多，但是容易陷入“早熟”(即快速收敛到局部最优解而不是全局最优解)，而且在接近最优解时收敛速度较慢。根据文献[25]，交叉概率Pc和变异概率Pm是影响算法收敛性的主要原因。一方面，Pc越大，新个体的产生速度越快，但Pc太大时遗传模式被破坏的可能性较大(适应度较高的个体结构很快就被破坏)，而当Pc太小时，新个体产生的速度太慢，甚至停滞不前；另一方面，Pm越小，产生新个体的难度越大，当其值过大时，遗传算法就变成了纯粹的随机搜索算法。不同的优化求解问题需多次反复实验确定Pc和Pm的值，这种操作既复杂，又难以获得适应每个问题的最佳数值，考虑到动态自适应技术的优越性，本文采用自适应遗传算法，根据个体的适应度值动态调整Pc和Pm，当种群适应度值比较分散时适当减小Pc和Pm，而当种群个体适应度值趋于一致时适当增加Pc和Pm。同时，对适应度值低于群体平均适应度值的个体采用较高的Pc和Pm，对适应度值高于群体平均适应度值的个体采用较小的Pc和Pm。因此，采用自适应的Pc与Pm可以提供相对某个解的最佳Pc和Pm，确保算法的收敛性和种群的多样性，具体计算如下：

(12)

(13)

式中：fmax为种群中个体最大的适应度值；favg为每代群体的平均适应度值；f′为交叉的两个个体中较大的适应度值；f为变异个体的适应度值。

利用改进的NSGA-II求解时间、成本的最大值和最小值，并进行多次计算，以减少算法的随机性，尽可能找到全局最优解。

4.2 算法的求解步骤

设开发某产品时共有m个任务，将所有任务划分为n个阶段执行(m≥n)，则任务调度方案数约为nm。复杂的产品开发涉及的m，n一般较大，若采用传统的枚举法或启发式算法，则搜索空间太大，时间消耗过大，且难得到全局最优解。遗传算法采用染色体交叉和变异操作，能够保留优良个体的特性，淘汰适应度较低的染色体，从而对问题进行优化求解。基于自适应交叉和变异概率的遗传算法优化流程如图2所示。

步骤1随机生成一定数量染色体(个体)，采用十进制编码，每个编码位表示对应任务所在的阶段数，如染色体{3,2,1,2,2,1}，表示任务3，6处于第1阶段，任务2，4，5处于第2阶段，任务1处于第3阶段。假设任务数为6，阶段数划分为3，初始种群数为100，则个体在MATLAB中生成的代码为Chrom=3ceil(rand(100,6))。每个阶段数都要出现在染色体的编码位上，淘汰没有出现所有阶段数字的染色体(或称个体)，调用相应函数，判断生成的染色体是否符合约束条件(对生成的染色体进行判断选择)。

步骤2将符合约束条件的染色体计算转换为开发时间和开发成本的综合目标评价函数G，并得出适应度。最小化问题适应度函数取目标函数的倒数1/G，适应度函数根据目标函数值的大小区分群体中个体的优劣(适应度函数是算法演化过程的驱动力，也是进行自然选择的唯一依据(保留适应度值较大的个体))。

步骤3选择适应度较大的两个个体作为父本，将其进行交叉变异操作得到新的染色体，判断是否满足约束条件，满足则执行步骤4，否则转步骤1。

步骤4计算符合约束条件新染色体的适应度大小。循环执行，直到满足终止条件，输出最优任务调度方案。

5 实例分析

5.1 问题描述

以某电动小汽车产品的开发过程[26]为例，该设计项目包括多个设计任务，简化处理后得到一个由8个设计任务组成的耦合集，如图3所示，包括：任务0-1(大小与动力特性)、任务0-2(马达规格与重量)、任务0-3(整体重量)、任务0-4(存储能量需求)、任务0-5(电池大小与重量)、任务0-6(速度与加速度比率)、任务0-7(速度与加速度规格)、任务0-8(结构与支撑设计)。图中：对角线元素为对应任务执行工期的中点值，非对角线元素为任务的返工量，空白处均为0；0～1之间的数值元素值表示任务的返工量，其值越大表示耦合关系越强，返工量越多，例如第1列第2行数字0.15，表示完成任务0-1后，任务0-2的返工量为15%(相对上一次工作量)。根据以往经验，从0-1～0-8每个任务对应的资源为5，3，3，4，2，4，3，6个单位资源，即Zy=[5,3,3,4,2,4,3,6]，总资源Zyzl=15。

由图3可得返工量矩R阵和任务工期矩阵Z:

Z=diag(8,6,4,3,3,6,3,5)。

5.2 任务调度方案优化

在不考虑学习与遗忘效应(即学习遗忘矩阵Q为单位矩阵)时，根据各阶段的任务执行时间和成本的计算模型(6)，在资源约束下对电动汽车中的耦合设计任务调度进行阶段划分，求解该耦合设计任务的调度问题。按照本文提出的整数编码方式，耦合集中的任务个数为8，则个体的编码长度为8。为了确定该耦合集的任务划分为多少阶段会出现最优任务调度方案，将任务的阶段数分别划分为2，3，4，5，6，7，8，采用MATLAB进行多次试算[25]，确定的相关参数如下：初始种群数量p=500，遗传迭代步数g=50，初始染色体交叉概率Pc=0.8，变异概率Pm=0.1。采用改进的NSGA-II寻找各阶段的最优解，用式(6)和(9)求解，分别得到各阶段的时间最小值、成本最小值及其对应的任务调度方案，如表1所示。

为了更加直观地表示时间、成本随着阶段数增加的变化趋势，采用MATLAB软件，得到表1不同阶段的最小时间优化图和最小成本优化图，分别如图4和图5所示。

表1 各阶段任务调度方案

显然，任务划分的阶段数越多，由每个阶段执行的任务数量相对越少，所需的资源也相对越少，此时资源充足，资源的利用率相对较低。若阶段数划分得太少，则开发成本较大；若阶段数划分得较多，则开发时间较长。由图4和图5可见，随着阶段数的增加，时间增加，成本下降，Pareto解的开发时间和成本大体成反比，不存在时间和成本同时最小的情况，说明同时优化时间和成本两个目标存在矛盾，即减少开发时间会增加开发成本，减少开发成本会延长开发时间，设计人员或决策者可以根据要求确定时间或成本可接受的范围，选择合适的任务调度方案。

在不考虑学习与遗忘效应的情况下，用改进的NSGA-II求解资源约束下的多目标优化模型(11)，得到所有方案的时间、成本Pareto解集，并计算平均时间为43.93 d，平均成本为87.9(d·人)，平均资源利用率为40%；再对所有方案的时间和成本进行非支配排序[13]，得到任务调度方案时间、成本的Pareto最优解集(如表2)；取权重系数w1=w2=0.5，采用改进的多目标理想点法对该解集进行选优(如图6)，计算获得最优任务调度方案对应的编码为{34211214}(企业决策者也可根据实际情况在Pareto解集中权衡选择)，即任务0-4、任务0-5、任务0-7处于第1阶段，任务0-3、任务0-6处于第2阶段，任务0-1处于第3阶段，任务0-2、任务0-8处于第4阶段，此时所需的时间T=32.93 d，成本为76.51(d·人)，利用式(8)得到该方案资源的平均利用率为50%。

表2 改进的NSGA-Ⅱ优化任务调度方案的时间、成本Pareto最优解集

针对只考虑学习效应、同时考虑学习和遗忘效应两种情况，采用以上相同的初始参数，采用改进的NSGA-Ⅱ和改进的多目标理想点法，分别得到相应任务调度方案的时间、成本Pareto最优解集和优选解。表3所示为不考虑学习和遗忘效应、只考虑学习效应、同时考虑学习和遗忘效应时的时间、成本优化结果及其比较。

表3 只考虑学习效应以及学习和遗忘效应时的时间、成本优化结果及其比较

为了比较不同学习指数l、遗忘指数f和学习概率λ对优化结果的影响，将任务的阶段数设置为8，采用控制变量法得到的结果和比较如表4所示。

表4 同时考虑学习与遗忘效应时不同l，f，

5.3 结果分析

用改进的NSGA-II求解本文建立的资源约束下的多目标优化模型，得到所有方案时间、成本的Pareto解集，再对所有方案的时间和成本进行非支配排序，得到方案时间、成本的Pareto最优解集，采用多目标理想点法对该解集进行选优，得到最优调度方案所需的时间T=32.93 d，成本为76.51 (d·人)，资源的平均利用率为50%，相比Pareto解集的平均时间43.93 d、成本87.09(d·人)和平均资源利用率40%，时间和成本分别缩短了25.04%，12.15%，资源利用率提高了25%。说明本文优化方法是有效的。

从表3可见，相对于不考虑学习和遗忘效应，只考虑学习效应或同时考虑学习和遗忘效应的产品开发时间分别减少6.2%，4.2%，成本分别降低7.2%，5.1%；相对同时考虑学习和遗忘效应，只考虑学习效应的产品开发时间减少2%，成本降低2.4%。说明只考虑学习效应或同时考虑学习和遗忘效应，均可减少产品开发时间并降低开发成本，但只考虑学习效应时产品开发时间和成本的优化效果更为显著。

由表4可知，当遗忘指数f和学习概率λ不变，学习指数l较大，或者l与λ不变，f较小，或者f和l不变，λ较大时，产品开发时间较少，开发成本较低；当λ不变，f较小，l较大，或者f不变，l和λ均较大，或者l不变，f较小，λ较大时，产品开发时间较少，开发成本较低。说明l，f，λ均对资源约束下的产品开发时间和成本有直接影响，其中l，λ较大或f较小，均可减少产品开发时间，降低开发成本。