基于混合NSGA2算法的生产调度优化*

赵政鑫，范 波，霍 华，孙力帆

(河南科技大学信息工程学院，洛阳 471023)

0 引言

优化过程的目的是为了找到最优值或最优解，优化问题通常为寻找最大值或最小值，根据目标的个数划分为单目标优化或者多目标优化，具有多个目标的优化问题称为多目标优化。多目标优化模型可作为资源开发和管理计划有效性的最佳评估工具，智能算法是求解多目标优化问题的主要手段。常见的智能算法有遗传算法、粒子群算法、蚁群算法、模拟退火算法、人工蜂群算法、灰狼算法等[1-6]。

调度问题的研究有利于资源的合理分配，因此有着十分重要的意义，众多学者为解决各式各样的问题进行了大量的研究，并使用智能算法寻找最佳生产调度计划。荆巍巍等[7]为解决组件制造过程中的生产调度问题，以最小化总完工时间、生产成本和最大化设备负荷为目标的柔性车间生产调度模型，使用非支配排序遗传算法对多目标模型进行求解；ZHANG等[8]针对服装生产中纺织染色工序调度问题，建立了以延迟成本和污染物排放水平为目标的优化模型，并使用粒子群优化算法对多目标数学模型进行求解；PAKPAHAN等[9]为得到自动化环境下作业车间的生产调度计划，建立了最小化零件总加工时间和延迟惩罚的多目标优化模型，并使用蚁群算法对其进行求解，得到生产调度的最佳时间表。

多目标调度优化问题的求解，需要根据所选方法具有的特点进行改进，平衡算法整体的收敛速度和搜索能力等特点。遗传算法作为常用的多目标优化问题的求解手段，具有优秀的全局搜索能力，但其他特点并不突出，需要改善遗传算法的收敛速度和局部搜索能力，以提高计算效率。

1 多目标优化

1.1 多目标优化问题描述

多目标优化是多准则决策的一个领域，涉及多个目标函数同时优化的数学问题[10]。通常，多目标优化问题的数学模型由目标函数和约束条件两部分组成，为统一求取各目标的最小值，可以将最大值问题的目标函数进行求倒数或取反，从而将最大值问题转变成最小值问题进行求解，约束条件又可细分为不等式约束和等式约束。因此，多目标优化问题可以描述为：

minF(x)={f1(x),f2(x),…,fm(x)}s.t.gp(x)≤0,j=1,2,…,Ps.t.hq(x)=0,k=1,2,…,Q

式中，F(x)是目标函数；x是决策变量；gp(x)≤0是不等式约束；P是不等式约束个数；hq(x)=0是等式约束；Q是等式约束个数；现在需要在满足约束条件的情况下求解这些目标函数的最小值，得到多目标问题的解决方案。

1.2 多目标调度优化问题的数学模型

现有n个待加工产品，生产加工需要经历的工序数为m；处理第j道工序可用的并行机器的数量Mj；在第j道工序上分给机器k处理的任务总数Nj,k；产品i的工序j在机器k上的开工时间和结束时间分别为Si,j,k和Fi,j,k，ti,j,k表示产品i的第j道工序在机器k上的加工时间；hjk表示工序j在机器k上处理的第h个作业任务；Ci,j,k表示产品i的第j道工序在机器k上的加工成本；xi,j,k为决策变量，当产品i的工序j使用机器k进行加工时其数值为1，其他情况下决策变量的数值为0。

本文针对生产调度问题建立总加工时间和总生产成本的多目标数学模型，总加工时间的目标函数为：

T=max{Fi,m,k} (i=1,2,…,Nm,k;k=1,2,…,Mm)

(1)

总生产成本的目标函数可以表示为：

(2)

调度问题的常见约束条件如下：

S(h+1)jk,j+1,r=max{F(h+1)jk,j,k,Fhjk,j+1,r}

(h=1,2,…,Njk-1;j=1,2…,m-1;k=1,2,…,Mj;r=1,2,…,Mj+1)

(3)

式(3)表示在机器r上处理第(h+1)jk个产品中的第j+1道工序的作业任务，即同一产品(h+1)jk上一道工序j的完成时间和同一台加工机器r上一产品hjk的完成时间中的最大者就是第(h+1)jk个产品的最早可开工时间。

Fi,j,k=Si,j,k+ti,j,k

(i=1,…,n;j=1,…,m;k=1,…,Mj)

(4)

式(4)表示产品的结束时间和该产品在机器上的加工时间和开工时间有关。

(i=1,2,…,n;j=1,2,…,m)

(5)

式(5)表示加工作业任务一旦开始就不可以中断或者转移。

(6)

式(6)表示对于每道工序，分配给并行机器的作业数量必须和订单的总数量一致。

Si,j,k≥0,ti,j,k≥0,Fi,j,k≥0,Ci,j,k≥0

(7)

式(7)表示非负约束。

2 改进的混合算法

多目标进化算法[11](MOEA)是一种随机优化技术，其全局搜索能力优秀，最终的输出结果精确，与数学计算得到的实际最优解相差无几，因此经常作为多目标优化问题的求解手段。与其他优化算法类似，多目标进化算法用于寻找特定问题的最优Pareto解，最具有进化特点的遗传算法就是通过种群迭代的进化思想来求解多目标优化问题。基于Pareto方法的遗传算法与简单的遗传算法的主要区别在于：基于Pareto方法的遗传算法使用支配关系，并根据个体之间的支配关系对种群进行分层，使用支配地位来判断解的好坏[12]。

在使用基于Pareto方法的遗传算法来解决多目标优化问题时，其中最可靠和最常用的是带精英策略的非支配排序的遗传算法[13](NSGA2)，该算法是非支配排序的遗传算法[14](NSGA)的第二个版本。相较于第一个版本，NSGA2提出了快速非支配的排序方法，降低了算法的计算复杂度；采用了拥挤度作为保持种群多样性的指标，也是评价同等级个体好坏的标准；引入精英策略，通过将父子种群合并，并选取排序靠前的个体作为新种群用于下一代的种群进化。

2.1 NSGA2算法

NSGA2算法的主要包含以下内容：

(1)非支配排序。在NSGA2算法当中，根据支配关系将所有个体依次划分到不同等级的前沿之中，个体的前沿等级反应了个体的好坏程度，若相比较的两个个体前沿等级不相同，等级数字越低，表明个体所处前沿越靠前，该个体在选择环节的优先度越高。

在计算每个个体所处前沿等级时，首先寻找当前种群中的所有非支配个体，组成非支配解集F1，将该集合中所有个体均标记为Pareto等级1，然后删除这些个体，消除Pareto等级1对其余个体的支配。然后将剩余种群中的非支配个体提取出来组成解集F2，并为这些个体标记为Pareto等级2，如此循环往复，直到所有个体都有独立的等级标记，完成对种群的分级。

(2)拥挤距离的计算。同等级的个体需要以拥挤距离为指标来进一步衡量个体的好坏，当每个个体的支配等级划分完成之后，需要进行拥挤距离的计算，在同前沿等级的情况下，拥挤距离越大的个体，其在种群进行非支配排序时的序列越靠前，拥挤距离的计算公式如下：

(8)

(3)个体好坏评判依据。当两个个体的前沿等级不相等时，优先选择前沿等级更小的个体；当两个个体的前沿等级相同时，再比较拥挤距离，优先选取拥挤距离较大的个体。

(4)精英保留策略。在NSGA2算法中，采用的是精英保留策略为新一代种群筛选优秀的个体。这个策略是将父子种群进行合并，共同构建一个总数是种群规模二倍的新种群，然后对合并后的新种群进行前沿等级和拥挤距离的计算，得到所有个体好坏的排序，根据比较环节决优的规则，依次为下一代代种群中填入优秀个体，直到下一代种群的规模恢复至合并前种群的规模大小。

(5)NSGA2算法基本过程。NSGA2算法是基于Pareto方法求解多目标优化问题，使用支配关系来衡量个体好坏，但其迭代进化过程与传统遗传算法大致相同，主要步骤如下：初始化参数，创建初始种群；对种群进行快速非支配排序，并选取优秀的个体进入交配池；进行交叉、变异等遗传操作产生子代种群；父子种群合并，并采用精英选择策略，选出的个体作为下一次迭代过程的父代种群；迭代循环，直至满足终止条件，将Pareto等级为1的解作为最终结果输出。

2.2 混合算法改进初始种群

混合算法是求解多目标优化问题的有效方向，整合智能算法来解决优化问题是当前研究的一大热点[15]。混合算法的目标是根据智能算法各自的特点，发挥算法对应的优点，改进混合算法整体的性能。

NSGA2算法和粒子群算法都是基于种群的方法，前者具有全局搜索能力强但搜索速度慢的特点，后者的特点为计算速度快却容易过早收敛，两者结合可以互补特点，因此本文将NSGA2算法和粒子群算法进行混合。这两种智能算法均是基于种群迭代的方式进行寻优，符合算法混合需要遵循的原则，且可以在保留各自算法自身优点的同时，互相弥补各自的不足，得到一个整体寻优效果更好的混合算法。

粒子群算法的核心内容为粒子的迭代公式，式(9)、式(10)分别是每次迭代对粒子的速度和位置进行更新：

(9)

(10)

对NSGA2算法而言，初始种群的好坏影响智能算法寻优收敛的效率。若选取优秀的个体参与交叉环节，可以将优秀的基因片段分享给其他个体并遗传给下一代，通过在寻优过程中进行有效的信息交换，从而提高算法整体的计算效率，增加种群搜索到最优解的概率，加快对多目标优化问题的求解速度。相反，若随机初始化产生的初始种群整体欠佳，交叉算子难以发挥将优良个体的基因片段遗传给后代的作用，交叉效果就会大打折扣，从而增加遗传算法寻找到最优解所消耗的时间。

如图1所示，本文通过将粒子群算法和NSGA2算法相混合，首先在第一阶段中利用粒子群算法寻优速度快、搜索效率高的特点对多目标问题进行初步寻优，获得进化到一定程度上的种群。然后混合算法进入第二阶段，将粒子群算法的输出结果作为NSGA2算法中的部分初始种群，从而提高NSGA2算法初始种群的整体质量，以此达到优化NSGA2算法初始种群的目的。为增加第二阶段初始种群的丰富度，将经过粒子群算法初步优化后的个体与第二阶段随机初始化产生的个体相混合，扩大NSGA2算法的种群规模，然后进行后续的迭代优化。将两种基于群体的智能算法进行混合，不仅避免由第一阶段粒子群算法寻优得到的个体陷入局部最优的情况，在一定程度上改善了粒子群算法容易过早收敛的缺点，增强了其全局搜索能力，还优化了第二阶段中NSGA2的初始种群，从而提高了其进化效率、改善了优秀基因片段的流通，有利于找寻全局最优解。

图1 混合算法改进初始种群

2.3 局部搜索

局部搜索是通过在某些个体的附近区域进行搜索，以期望产生更好的个体，并将其作为未来的父代参与种群进化过程当中。

本文在经过交叉和变异操作环节之后增加局部搜索环节，根据个体的支配等级和拥挤距离信息，得到非支配前沿中的每个目标的边界点和除了边界点之外拥挤距离最大的稀疏点。如图2所示，包含拥挤距离为无穷大的边界点，一共寻找拥挤距离排名前三的个体作为局部搜索的区域中心，围绕这些个体对附近的解空间进行局部搜索。通过采用多个策略变更染色体的基因序列从而生成局部解，将局部搜索得到的所有个体并入本次迭代的种群当中，一起进行快速非支配排序，共同进行选择操作。

图2 局部搜索的中心

本文的局部搜索策略有以下特点：由于进行局部搜索的区域中心是直接根据快速非支配排序的结果得到的，不需要重新计算新的指标，在一定程度上减小了计算。选择少量的个体作为局部搜索的中心，而不是对每个个体都进行局部搜索的操作，在一定程度上避免了无效的搜索，降低了设计的复杂度。采用多个策略生成局部解，增加了局部解的多样性，有利于寻找到更优的个体。

采用多策略相结合方式进行局部搜索得到的局部解组成的群体，其丰富度更高，有利于提升局部搜索的效率。本文选用逆转基因片段、交换基因位和基因位前置的三种方式对选出的个体进行局部搜索，多策略相结合的局部搜索提升了丰富度和多样性，并且这些局部搜索策略的优点是不会生产非法解。逆转基因片段是随机选取两个基因节点，将节点间的遗传信息倒序排列。交换基因位是随机选取两个基因位，交换两者所携带的遗传信息。基因位前置是随机选取一个或多个基因位将其插入某个或某些基因位之前。这三种策略均是随机挑选变更的位置，即便同一条染色体使用相同的策略，依旧有很大概率得到不同的染色体排序方式。

2.4 混合算法步骤及流程图

改进的混合算法具体流程如图3所示。

图3 混合算法流程图

3 仿真分析

本文基于铜合金板带生产调度信息进行分析，采用文中所提到粒子群和NSGA2相结合的混合算法对铜板带调度问题的多目标数学模型进行求解，得到最佳的调度方案。在符合铜板带实际生产加工流程下，优化调度任务的总加工时间和总生产成本，为企业节约时间、减小成本，提高生产效率，从而增强企业的竞争力。

依据铜板带工艺的工序流程、机器分配以及生产约束，对各订单在各道工序上的操作顺序进行安排。以10个铜板带全流程生产加工的订单任务为例，将铜板带生产加工的全流程简化合并为4个环节，共有12台机器对其进行处理，熔铸、热轧、冷轧、热处理这四道工序并行机器数量分别为3台、2台、2台和4台，不同工序其加工工艺的数据信息不同。加工时间中包含了运输时间，生产成本不包含铜合金的原料成本，铜板带订单的调度信息如表1所示，各订单在各环节加工时间的单位是分钟，加工成本的单位是万元。

表1 铜板带调度信息

10个订单在各道工序上的机器分配决定了具体的调度信息，本次铜板带生产调度实例通过MATLAB R2020a平台的数字仿真实现。所采用的混合算法主要参数信息如下，粒子群算法的种群规模为40，迭代次数为50，惯性权重为1；NSGA2算法的种群规模为100，迭代次数为300，交叉概率和变异概率分别为0.9和0.1。铜板带生产调度问题的生产加工甘特图如图4所示，横坐标表示铜板带生产加工的时间(单位是min)，纵坐标表示铜板带生产加工所使用的机器编号(机器1-3属于熔铸环节，机器4-6属于热轧环节，机器7-8属于冷轧环节，机器9-12属于热处理环节)，甘特图中作业任务的格式为[订单号，工序号]，从图中可以清楚得知作业任务的分配。

图4 铜板带生产加工甘特图

铜板带调度问题的Pareto前沿如图5所示，改进混合算法的各个目标值更佳，具有更好的Pareto前沿分布，表明其寻优性能优于原始算法。

图5 铜板带调度问题的Pareto前沿

从实验结果可以看出，铜板带生产调度问题中非支配解的调度方案在总加工时间和总生产成本上的分布，两个目标相互联系、相互冲突，每个非支配解的调度方案都有各自的优点，不论是总加工时间短或者总生产成本低。多目标优化算法可以在一次运行中为铜板带调度问题提供多种备选解决方案，由于每个备选解决方案都有各自优势，无法得到一个时间和成本均是最优的方案，企业可以根据订单任务的具体需求在非支配解集中选择合适的调度方案，根据所选方案解析出相对应的生产加工甘特图，从而将各个订单任务分配到相应的机器上进行作业。

4 结束语

文中针对生产调度多目标优化问题，以总加工时间和总生产成本为目标建立数学模型，以铜板带全流程工艺生产流程为例，采用改进混合算法对生产调度优化问题进行求解，选取其中一个调度方案并绘制甘特图。实例结果表明，所提方法可以得到更好的Pareto前沿，在各个目标值上的最佳值均优于原始方法，证明了对初始种群和局部搜索进行改进的有效性，提高了生产调度多目标问题的求解效率。根据算法求取的调度方案更具合理性，有利于缩短时间、减少成本，可以改善企业的生产效率。