变邻域保优遗传算法求解柔性车间调度问题

吴树景，游有鹏，罗福源

南京航空航天大学 机电学院，南京210016

1 引言

柔性作业车间调度问题（Flexible Job Shop Scheduling Problem，FJSP）是当前智能制造及工业自动化领域研究的热点问题，在离散制造业、流程工业中应用广泛。FJSP 是典型的NP-hard 问题，工艺约束较多，每个工件的每道工序都可在可选择的有限台机器上加工，计算复杂性高。目前求解FJSP常用的智能优化算法包括遗传算法、蚁群算法、粒子群算法、模拟退火算法、禁忌搜索算法等。

遗传算法（Genetic Algorithm，GA）是一种模拟自然进化机制的全局优化算法[1]，优化过程不受限制性条件的约束，全局搜索能力很强，但存在稳定性差、爬山能力弱、易陷入局部最优等缺点。周頔[2]融合了遗传策略和蚁群策略，有效提升了择优能力和求解精度。宋存利[3]采用贪婪策略对GA 算子进行改进，增强了局部寻优能力。

变邻域搜索（Variable Neighborhood Search，VNS）算法是一种高效的局部优化算法[4]，它旨在通过不同邻域的递进式排查，在反复迭代中使当前的局部最优解向最优解进一步靠拢，局部搜索能力很强。VNS算法在深入搜索的过程中采用多个而非单个邻域结构，因此可获得比固定邻域局部搜索算法更强的寻优能力和搜索效率[5]。崔琪等[6]提出了改进混合变邻域搜索的遗传算法，设计了“两点交换”“反转逆序”“打乱互换”等五种邻域结构，提升了解集质量。王丹敬等[7]设计了自适应变邻域搜索算法，利用“2-insertion”等邻域快速获得高质量的近优解。

目前大部分优化算法的盲目性和随机性较强，与FJSP的特点联系弱，稳定性差。由上述文献分析可知，GA 与VNS 算法构成极好互补，二者融合可有效增强FJSP 求解性能。而国内此方面的研究较为匮乏，主要体现有：遗传算子跳坑能力不足，自适应性弱；缺乏优良个体保护机制；很多邻域本质为枚举，当问题规模变大时待试探的可行解集规模也会呈指数上升，寻优效率极大降低。故遗传算子优化及邻域设计方面仍有很大提升空间。

本文结合GA 全局搜索能力强和VNS 算法局部优化效果好的特点，将GA与VNS算法相结合以平衡寻优的广度与深度。同时，对GA 算子进行改进，并引入保优记忆库策略对精英个体进行保护。其次，针对FJSP的特点设计了三种基于关键工序进行调整的邻域结构，给出了改进的关键工序寻找法则和甘特图向编码映射的工序调整方案。最后，通过算法测试与数值实验，采用基准算例与其他现有算法进行横向测评，证明所提算法的可行性与有效性。

2 FJSP数学模型

n 个工件(J1,J2,…,Jn)要在m 台机器(M1,M2,…,Mm)上加工；每个工件包含一道至多道工序；每道工序可在多台不同机器上加工；不同机器加工各道工序的时间不同。由此，FJSP问题本质上由两个子问题组成：机器选择和工序排序。

本文选取“最大完工时间Cmax最小”作为优化目标，如式（1）所示：

式中，Cj为第j 个工件最后一道工序的完成时间，Cmax为全部工件中最大的完工时间即最大完工时间（makespan）。优化目标的约束条件如下：

其中：

式中，cik和cjk分别为工件i 和j 在机器k 上的完成时间，cih为工件i 在机器h 上的完成时间，tik和tjk分别为工件i 和j 在机器k 上的加工时间；M 是一个足够大的正数；aihk为决定工序先后顺序的决策变量，xijk为工序分配机器的决策变量。

式（2）表示顺序约束条件，保证每个工件的加工顺序满足预先的要求。

式（3）表示资源约束条件，即机器加工各工件的先后顺序，限定每台机器一次只能加工一个工件。

3 变邻域保优遗传算法

本文综合遗传算法的全局搜索优势与变邻域搜索算法的局部搜索优势，加入改进的保优记忆库策略，提出了基于操作编码的变邻域保优遗传算法。

3.1 整体流程框架

整体算法流程框架如图1所示。

图1 整体算法流程框架图

算法具体步骤如下：

步骤1 使用GLR机器选择法[8]对种群进行初始化，生成质量优秀的初始解集。

步骤2 判断当前迭代次数N 是否已达最大迭代次数MAXGEN 。若是，则输出最优解或近似最优解；否则，继续执行步骤3。

步骤3 执行遍及赌轮选择操作，生成子代种群。

步骤4 根据交叉概率Pc选取进行交叉的个体，再根据交叉方式选择概率Pv采用以下两种方式中的一种执行交叉操作：子代种群中个体两两进行交叉，子代种群和外部保优记忆库中各选一枚个体进行交叉。

步骤5 根据变异概率Pm选取进行变异的个体，执行变异操作。

步骤6 对全部个体执行变邻域搜索，用优良解替代劣解。

步骤7 执行精英保留策略，选取当前代新种群中的较优个体更新保优记忆库，对精英个体进行保护。

步骤8 每隔Nd迭代次数对种群进行一次扰动，以随机选择的方式生成扰动比例Pd乘以种群规模数量的新个体，并替换当前代种群中同数目的较差个体，以此增强种群的活跃性和丰富度，防止陷入局部最优解。

3.2 染色体编码与解码

本文采用MSOS染色体编码方案[9]，如图2所示，编码由两部分组成：机器选择部分（Machines Selection，MS）和工序排序部分（Operations Sequencing，OS）。机器选择部分各基因位依次按照工件及工件工序的顺序排列，基因位的值表示该工序选择的加工机器在可选机器集中的序号；工序排序部分各基因位值为工件号，某一位置上工件号已出现的次数代表属于该工件的工序号。

图2 FJSP染色体编码示例图

解码时采用文献[8]给出的前沿贪心方式解码成活动调度，目的是尽量将工序安排至对应机器的最早可行加工时刻，将整体调度的最大完工时间缩至最短。

3.3 遗传算法

3.3.1 种群初始化

本文采用GLR机器选择初始化的方式[8]，包含全局选择（Global Selection，GS）、局部选择（Local Selection，LS）和随机选择（Random Selection，RS）。GS旨在从全局的角度保证所有加工机器负载均衡；LS 旨在从各工件独立的角度保证所有加工机器负载均衡，以提高机器的利用率；RS 旨在使初始种群尽量地分布于整个解空间，提高种群多样性。三者按各自比例均匀作用于初始种群中的个体，可显著提高初始种群中的染色体在MS部分的质量。

3.3.2 选择算子

本文对传统的轮盘赌选择算子进行了优化，改进为遍及赌轮选择算子，如图3所示。给定参数GGAP为子代和父代种群大小差异的代沟比例，为赌盘均匀设置数目等同于子代所需个体数的多个取样指针，旋转一次即可根据适应度值筛选得出整个子代种群，在保证选择结果分布均匀的前提下有效提升选择效率。

图3 遍及赌轮选择

3.3.3 交叉算子

本文在选择交叉操作执行的个体时，根据式（7）所示的交叉方式选择概率Pv,N 为当前迭代次数，MAXGEN 为总迭代次数，P 为随机生成概率。分别选用两种交叉方式：P ＞Pv时，子代种群中个体两两进行交叉；P ＜Pv时，子代种群和外部保优记忆库中各选一枚个体进行交叉。

Pv随N 变化的曲线如图4 所示，可看出：前期Pv较大，多采用第二种交叉方式，以此快速寻找到较优解，提升收敛速度；后期Pv较小，多采用第一种交叉方式，以此增加新个体产生的机会，避免陷入早熟的陷阱。

图4 交叉方式选择概率Pv 图形

详细交叉策略如下：

机器选择（MS）部分采用均匀交叉操作，如图5 所示，交换两父代染色体n 个随机位置点处的基因片段。

工序排序（OS）部分采用改进的POX 交叉方法[10]，如图6 所示，划分工件集为两个非空集合，其中一集合中工件工序的基因在两父代染色体中保持不变，顺序交换两父代染色体另一集合中的基因。

图5 均匀交叉

图6 改进POX交叉

3.3.4 变异算子

机器选择（MS）部分采用随机分配可选机器的操作[11]，如图7所示，随机选择n 个基因位（n 不大于MS部分编码长度的1/4），用其对应可选加工机器替换。

图7 MS部分变异

工序排序（OS）部分采用插入变异的方式执行变异操作，如图8 所示，在工序编码中随机选取一个基因并将其插入至OS部分的一个随机位置上。

图8 OS部分变异

3.3.5 保优记忆库策略

传统遗传算法中交叉算子的作用个体全部来自于子代种群，此机制有两个明显的缺点：一是每轮迭代产生的优秀个体因得不到及时保护而易在下一轮迭代中被破坏；二是算法易过早收敛于局部最优解而导致早熟。本文针对该弊端提出一种改良的保优记忆库机制，将搜索过程中的精英个体加入库中进行保护，留待供下一轮迭代进行交叉操作。

为使保优记忆库中的精英个体尽可能分布均匀且种类丰富，引入“海明距离”的概念：两个染色体编码中相异的基因位的个数称作海明距离，简称H 。

将精英个体更新至保优记忆库的算法流程如图9所示，其中Ht为待插入个体的海明距离，Hn为保优库中第n 个个体的海明距离。

3.4 变邻域搜索算法

图9 保优记忆库更新流程图

本文以关键工序为调整对象，机器空闲时间为突破点缩减最大完工时间的思想构建邻域，在赵诗奎[12]、王磊[13]等学者的研究基础上进一步改进：优化了关键工序的提取效率，拓展了空闲时间的搜索范围，提出了甘特图向编码映射的工序调整方案，融合了单工序与双工序的调整策略。由此提出三种邻域结构：同机器工序调整邻域、变机器工序调整邻域和双工序调整邻域。

3.4.1 变邻域搜索流程

变邻域搜索流程如图10所示，先进行单工序调整，随机选择“同机器工序调整”和“变机器工序调整”中的一个邻域先执行，再执行另一个；然后执行双工序调整。根据邻域搜索操作执行后个体的目标函数值进行取舍：若执行后的个体目标函数值优于原个体直接替换，差于原个体不替换，相等则以50%概率进行替换。

图10 变邻域搜索流程

3.4.2 关键工序提取改进方案

析取图中从起点到终点的最长路径为关键路径，对应于甘特图中工序间无时间间隔的最长路径，组成关键路径的工序为关键工序，其直接决定调度方案的最大完工时间。因此在邻域中对关键工序而非任意工序进行调整可减少搜索的盲目性，极大提高找到更优解的概率。由于每个个体进行变邻域搜索前都需对关键工序进行提取，故高效的提取方案对于整体算法快速求解尤为重要。

反向查找[13]是较为常用的关键路径提取方案，如图11所示，其原理是：从最后完工的某一工序开始向前执行地毯式试探，同时遇到其工件前续工序和机器前续工序时取其工件前续工序，直到完整拼凑出紧密连接的最长路径。此方法在规模较小的算例下效率较好，但随着问题规模增大，可试探的路径数量呈指数增加，搜寻效率和稳定性均会急剧下降。

图11 关键路径反向查找法

图12 关键工序锁定特性

如图12 所示，在工序安排顺序和最大完工时间不变的前提下，受到属于同一工件/机器的前/后工序的最早/晚开工/完工时间约束，关键工序会被锁定，而非关键工序可在一定区间内自由移动。根据这一特性，本文提出一种较大规模算例下搜索速度和质量均较好的关键工序提取方案，相关符号变量说明如下：sE(h)为工序Oh的最早开工时间，sL(h)为工序Oh的最晚开工时间，cE(h)为工序Oh的最早完工时间，cL(h)为工序Oh的最晚完工时间；PJ(h)为工序Oh属于同一工件的前道工序，SJ(h)为工序Oh属于同一工件的后道工序，PM(h)为工序Oh属于同一机器的前道工序，SM(h)为工序Oh属于同一机器的后道工序；p(h)为工序Oh在当前机器的加工时间。提取过程如下：

（1）采用文献[8]给出的前沿贪心方式将染色体解码成调度甘特图，工序Oh在图上的开始加工时间记为该道工序的sE(h)。

（2）按式（8）计算得出工序Oh的cL(h),SJ(h)或SM(h)不存在则用∞代替，cL(h)不可超过整体调度的最大完工时间。从后向前对各工序进行迭代计算，迭代过程中对已计算的变量进行记录，防止重复计算以提高效率。

（3）以式（9）为基准进行判断，若满足则判定该道工序为关键工序。

3.4.3 同机器工序调整邻域

同机器工序调整邻域通过遍历调度方案中的每个关键工序，尝试将关键工序Oh调整至属于其同一加工机器的其他工序间的空闲时间以最大限度地压缩最大完工时间。先按图13所示方法找出全部可缩减最大完工时间的调整方案，再按图14 所示方法调整染色体编码，最终保留调整后进化程度最大的调整方案。

图13 同机器工序调整邻域结构示意图

图14 甘特图向编码映射的工序调整方案

邻域结构示意图如图13所示。横向双箭头表示从0到Cmax区间内所有可供试探的空闲时间间隔。以“尝试将Oh移动至工序b 和c 间的空闲时间间隔”为例说明调整方式：对Oh的最大可调时间段[cE[PJ(h)],sL[SJ(h)]]与工序b 和c 之间的最大可能空闲时间段[cE(b),sL(c)]求交集，交集不为空时得到可利用区间t ，其左边界tL为max{cE[PJ(h)],cE(b)},右边界tR为min{sL[SJ(h)],sL(c)},若tR-tL＞0 则代表该移动可减少最大完工时间。

染色体编码的调整方式如图14 所示，同机器调整只需对编码的OS部分操作：将Oh对应的基因插入至工序c 对应的基因之前，在前沿贪心式主动调度的影响下，此番调整后甘特图上Oh也将以最紧凑的方式插入至工序c 之前。

3.4.4 变机器工序调整邻域

变机器工序调整邻域与同机器工序调整邻域的不同之处在于：前者尝试利用的是Oh当前加工机器之外的其他可选机器上工序间的空闲时间。甘特图搜寻方案和染色体编码调整方式分别如图15和图16所示。

图15 变机器工序调整邻域结构示意图

图16 甘特图向编码映射的工序调整方案

邻域结构示意图如图15所示，遍历Oh当前加工机器之外的其他可选机器上0 到Cmax区间内的空闲时间间隔进行试探，以“尝试将Oh移动至另一台加工机器上工序a 和b 间的空闲时间间隔”为例说明调整方式：对Oh的最大可调时间段[cE[PJ(h)],sL[SJ(h)]]与工序a 和b 之间的最大可能空闲时间段[cE(a),sL(b)]求交集，交集不为空时得到可利用区间t，其左边界tL为max{cE[PJ(h)],cE(a)},右边界tR为min{sL[SJ(h)],sL(b)} ，若tR-tL＞p(h)则代表该移动将Oh从原加工机器队列中抽出的同时，既不影响加入的机器队列中其他工序的原本状态，也不会产生新的关键路径，故可能减少最大完工时间。

染色体编码的调整方式如图16 所示，由于是变机器调整，先将编码的MS 部分Oh对应基因改为调整后的可选机器编号。再对编码的OS部分操作：若Oh基因在工序b 基因之后，将Oh基因插入至工序b 基因之前；否则无需调整OS部分编码。

3.4.5 双工序调整邻域

双工序调整邻域旨在对关键块（即关键路径上属于同一加工机器的相邻工序）内工序进行移动，且仅调整OS 部分。邻域结构示意图如图17 所示。该邻域基于Van Laarhoven 等[14]提出的邻域改进而来，删减了多处无效移动以缩小邻域规模，提升局部搜索效率的同时保证邻域结构的多样性。

图17 双工序调整邻域结构示意图

移动过程如下：

（1）若首块包含两道及以上工序，交换块尾相连的两道工序；若尾块包含两道及以上工序，交换块首相连的两道工序。

（2）除首块和尾块外的关键块，交换块首和倒数第二道工序，交换块尾和第二道工序。

4 算法测试与数值实验

4.1 参数设置

上述变邻域保优遗传算法采用Visual Studio 下C#语言编程，程序在处理器为Intel Core i7 四核CPU、主频为2.60 GHz、内存为8 GB、操作系统为64位Windows10的个人计算机上运行。

算法具体参数设置如下：

整体：种群规模Size=100，最大迭代次数MAXGEN=200，扰动间隔代数Nd=20，扰动比例Pd=30%；种群初始化：GS、LS、RS 的比例分别为0.6，0.3，0.1；选择算子：代沟比例GGAP=0.9；交叉和变异算子：交叉概率Pc=0.8，变异概率Pm=0.05；保优记忆库：库最大容量KMAX=10。

4.2 实验用例

（1）Kacem 8×8、10×10、15×10三个实例[15]。

（2）Brandimarte十组实例（BRdata）[16]。

4.3 变邻域搜索策略对比实验

为证明本文所设计的三个邻域拓展搜索深度的能力，使用Brandimarte十组实例（BRdata）中的MK01进行实验，分别采用添加变邻域搜索策略的遗传算法和去除变邻域搜索策略的遗传算法进行求解，重复50次，分别记录这两种算法求得解集中的最优个体目标函数值。

实验结果如图18所示，50次实验中，融合了变邻域搜索策略的遗传算法得到的最优个体Cmax主要集中在最优解40 上；而去除变邻域搜索策略的遗传算法得到的最优个体Cmax大部分集中在次优解42 和41 上。经对比可证明，在求解稳定性和搜索深度上，融合了变邻域搜索策略的遗传算法明显优于去除了变邻域搜索策略的遗传算法，当问题规模增大、解空间拓扑结构复杂时，本文设计的变邻域搜索算法可在遗传算法全局优化的基础上快速稳定地深入寻找到更优解。

图18 算例MK01（10×6）50次求解结果

表1 各种算法对Kacem算例求解结果对比分析

表2 各种算法对Brandimarte算例求解结果对比分析

4.4 标准算例测试实验

为客观检验变邻域保优遗传算法求解FJSP问题的整体性能，进行基准算例测试，每个算例求解20 次，记录最优值和平均值。

首先，对Kacem三个中小型实例进行测试，并与董蓉的GA+ACO[17]、Nouiri的MAPSO1[18]、Ziaee的Heuristic[19]、Rhamati 的BBO[20]、Gao 的TABC[21]、Wang 的IACO[22]进行对比，结果如表1所示，其中Cmax为最优解，Aver 为平均值。对比显示，在搜索深度上，本文算法所求得的最优值均已达到参考文献中的最好解，其余算法中仅GA+ACO、TABC和IACO算法可与本文算法持平；在搜索稳定性上，本文算法所求得的平均值优于GA+ACO算法。由此验证了本文算法应对中小型FJSP问题时深入且稳定的优势。

然后，对Brandimarte十个大中型实例进行测试，并与Ho 的LEGA[23]、刘 琼 的IGA[24]、Ziaee 的Heuristic[19]、Rhamati的BBO[20]、Gao的TABC[21]、Shao的hDPSO算法[25]进行对比，结果如表2和表3所示。对比显示，在求解深度上，除MK10 算例外，本文算法的求解结果均取得了所列算法的最好解；在整体求解质量上，本文算法的优于解与差于解数目和TABC算法持平，而与其他五种算法相比优于解数目明显多于差于解数目。在搜索稳定性上，本文算法所求得的平均值均优于LEGA和IGA算法，且对于MK09大型算例的求解均值有明显改善。由此验证了本文算法应对大中型FJSP 问题时，在保证搜索深度的前提下，进一步提升了寻优的稳定性和全面性。

表3 Brandimarte算例优于解和差于解数目对比分析

择取MK09实例进行完整记录，Cmax平均值和最优值收敛曲线如图19所示。可见，在扰动策略的作用下，平均值收敛曲线每迭代20 次会产生一次跃变，而最优值收敛曲线由次优解跳向更优解的行为也发生在跃变点附近，证明新元素的补充可适当增强种群的活跃度，配合变邻域搜索的局部优化能力可提高算法的跳坑能力。同时，在本文所设计保优记忆库策略作用下，平均值收敛曲线的跃变会快速回归平稳，且不会影响种群解的最优值。图20为该算例求得的最优调度甘特图。

图19 算例MK09（20×10）收敛曲线

5 结束语

本文针对最小化最大完工时间的单目标FJSP，提出融合了遗传算法与变邻域搜索的混合算法，合理平衡了搜索过程的广度与深度，通过对Brandimarte 等算例的测试验证了该算法的可行性与有效性。设计了一种保优记忆库策略，在有效保护精英个体的基础上进一步提升精英群体的丰富度。提出了高效稳定的关键工序搜寻方法，改进并设计了三种基于关键工序调整的邻域结构，并验证了其深化局部搜索能力、拓展寻优深度的良好效果。未来的研究中，将考虑与其他智能优化算法进行融合，并对多目标FJSP 和动态调度问题进行深入探索，使求解作业车间调度问题的算法更加高效和完善，且具有更强的适应性。此外还考虑将本调度算法应用于制造车间的MES 系统中，以应对实际加工过程中的任务订单调度需求。

图20 算例MK09（20×10）最优调度甘特图