基于混合变邻域遗传算法的柔性车间调度研究

刘明豪，蔡劲草，王 雷，顾 瀚，张茂杉，谭铁龙

基于混合变邻域遗传算法的柔性车间调度研究

刘明豪1，*蔡劲草1，王 雷1，顾 瀚1，张茂杉2，谭铁龙3

（1.安徽工程大学机械工程学院，安徽，芜湖 241000；2.芜湖杭翼集成设备有限公司，安徽，芜湖 241000；3.芜湖柯埔智能装备有限公司，安徽，芜湖 241000）

针对柔性作业车间调度的问题，以最大完工时间为目标建立数学模型，提出一种混合变邻域遗传算法。采用三种初始化方法保证初始解的质量，用遗传算法进行初步搜索，将搜索的结果通过迭代贪婪策略进一步搜索，以提高解的质量，再对关键路径进行邻域搜索，设计“跨机器工序搜索邻域”、“同机器工序搜索邻域”、“次优工序搜索邻域”三种邻域结构，加强局部搜索能力。引入迭代贪婪策略和改进的邻域结构可显著提高算法的稳定性与迭代速度。通过对国际通用的柔性作业车间调度基准算例进行测试，实验结果表明所提改进算法能够有效求解柔性作业车间调度问题。

柔性作业车间调度；混合变邻域；遗传算法

高效的生产调度优化技术对于提高制造系统生产率和设备资源利用率，缩短产品制造周期具有十分重要的意义[1]。随着自动化技术的发展与进步，柔性制造系统等带有一定柔性的生产系统逐渐出现，柔性作业车间调度问题（Flexible job shop scheduling problem，FJSP）逐渐成为研究的焦点问题。FJSP是传统作业车间调度问题（Job shop scheduling problem，JSP）的延伸，它研究转向可在多台机器上加工的工序，更加符合生产实际，同时其解空间的规模进一步扩大，也是更为复杂的NP-hard问题，其研究具有重要的理论意义和应用价值。

本研究针对遗传算法不稳定和局部搜索能力弱的特点，通过将变邻域探索算法融入到遗传算法中，使用三种策略获得初始解，加入迭代贪婪后，进一步增强了局部搜索能力，通过设计了三种邻域结构结合以强化搜索的广度、深度和稳定性，最后通过基准算例验证了其有效性。

1 柔性车间调度问题

柔性作业车间调度加工约束条件如下：

1)所有机器和作业在时刻0都是可用的。

2)不同作业的操作之间没有优先级限制。

3)每项作业不能由两台机器同时进行，每台机器只能同时进行一项操作。

4)机器之间的转换时间假设可以忽略不计。

5)任何机器在同一时刻仅能加工一个工件。

2 混合变邻域遗传算法

在FJSP问题研究中，针对遗传算法搜索不够全面，容易陷入局部最优解的问题，本研究提出一种混合变邻域搜索的遗传算法。

2.1 染色体编码设计

FJSP问题由两部分组成：确定各工件工序的加工顺序和确定每个工件的各工序所用的加工机器。因此，对FJSP问题采用两段式编码：一是面向工序部分的编码，用来确定工件的加工顺序，二是面向机器部分的编码，用来确定各工件的工序的加工机器。

1)面向工序部分的编码

2)面向机器部分的编码

2.2 初始解的构造

初始解在遗传算法中有重要的作用，优秀的初始解往往能加快收敛速度、改善求解结果，反之则可能拖慢求解速度，甚至无法获得最优解。

为了使保证初始种群的多样性，工序部分的编码采用随机初始化，而机器部分的编码采用全局选择、局部选择以及随机选择三种策略产生。其中，全局选择是通过对当前工序所有可能的加工机器进行比较，选择能够使总体加工时间最短的机器，局部搜索则是在当前工序所有的加工机器中，挑选所需加工时间最短的机器，随机选择将从所有可用的加工机器中随机选取。

2.3 选择操作

FJSP问题中，通过对当前染色体的选择可以将父辈中的优良基因以更大概率保留下来，从而加快搜索的速度，提高解的质量。本研究采用锦标赛选择和精英保留策略两种选择方法。其中锦标赛选择是从父代种群中随机选取两个个体，比较其适应度值，将适应度较大的个体放入子代种群，直到子代种群中染色体数量等于父代种群中的数量。同时，为了使优良基因更大程度地保留，采用精英保留策略，取适应度前10%的个体直接进入下一代。

2.4 交叉操作

交叉操作是通过选取父代种群中的染色体进行两两交叉，从而改变基因群，有可能获得更优秀的子代染色体。对于遗传算法来说，新个体、新性能的主要来源为交叉操作，因此交叉质量的好坏决定了遗传算法的全局搜索能力。本研究针对工序编码和机器编码分别采用不同的交叉方式。

1)工序编码部分交叉

采用POX（Precedence Operation Crossover）交叉和JBX（Job Based Crossover）交叉两种交叉方式随机使用，其中，POX交叉过程如图1所示，在父代染色体1中随机取个基因（0＜＜），在父代染色体2中取相同的基因，将1，2中的基因按照原本顺序交换插入到对方基因位置处，生成子代1，2。

图1 POX交叉

JBX的交叉过程如图2所示，将所有基因划分成两部分1，2，其中父代1将1中的全部基因按照顺序取出，父代2将2中的全部基因按顺序取出，然后将父代1中取出的1基因按顺序插入2相同基因的位置处，父代2中取出的2基因按顺序插入1基因处，生成子代1，2。

图2 JBX交叉

2)机器编码部分交叉

该部分采用两点交叉，如图3所示，取两个父代1，2，然后随机取两个位置，将1，2两位置间的基因按顺序交叉，获得子代染色体1，2。

图3 两点交叉

2.5 变异操作

交叉操作仅对已有基因进行操作，一旦陷入局部最优很难跳出，因此采用变异操作，通过对当前基因进行某种随机性改变，跳出局部解，从而维持遗传算法种群的多样性，防止出现早熟收敛现象。

1)工序编码部分变异

工序部分采用互换变异（Swapping Mutation）和邻域全排列变异（Neighborhood Mutation）两种变异算子随机进行，其中互换变异的流程如下图所示，随机取一个父代染色体，生成两个变异点，然后将两个变异点的基因互换。

邻域全排列变异步骤如图4所示，随机取出三个点位的基因，然后进行全排列，从全排列的结果中随机取出一个，插入原来的基因位置。

图4 邻域全排列变异

机器编码串采用单点变异策略，在机器编码串中，随机选取一个位置，在该位置工序所对应的可选机器集中选择一个与当前加工机器不同的机器来替换当前机器。工序编码串采用互换变异方式，在工序顺序链中，随机选择两个不同位置，将其基因值互换。

2)机器编码部分变异

机器部分采用随机变异，取个基因，为染色体基因数量的一半，然后在可选机器中随机选出新的基因，插入原来的位置。

2.6 迭代贪婪

在车间调度中，最后完工的工序会决定最大完工时间，因此如果能使该工序前几道工序的加工时间变短，则能减少max。迭代贪婪算法通过对原有可行解的破坏以及后续的重构，从而获得新的可行解。如图5所示，迭代贪婪通过寻找染色体最后完工工序的工件2，将工件2所属整个工序从工序编码串OS中破坏，然后再依照加工时间最短为原则，重构工件使用的加工机器，获得新的机器编码串MS，在依照加工顺序插入工序编码串OS中，同时与原染色体最大完工时间比较，如果更优则选择，否则保留。

图5 迭代贪婪

2.7 变邻域搜索算法

2.7.1 关键路径选取

关键路径是指从0时刻开始，不间断加工直至最迟完工的工序的一条路径，在甘特图中是由开始结束时间相同的工件工序组成的最长的一条路径，关键路径决定了max的大小。若果能减少关键路径上的加工时间则一定能减少max，因此针对关键路径进行搜索可以提高效率搜索效率[9]。

2.7.2 扰动

图6 TOS算子

图7 THOS算子

2.7.3 基本局部搜索

1）跨机器工序搜索邻域

跨机器工序搜索邻域是通过遍历整个生产的全部关键工序，尝试将关键工序插入到除加工该关键工序机器以外的机器中，达到尽可能压缩完工时间的目的[19]。

图8 跨机器工序搜索邻域

2)同机器工序搜索邻域

图9 同机器工序搜索邻域

3)次优工序搜索邻域

局部的最优往往未必是整体的最优，有时次优的局部解组合能获得全局的最优。次优工序搜索邻域通过遍历关键路径上的工序，寻找关键工序是否有最优解，如果有，则选择最优解，如果当前已经是最优解，则一定概率选择次优解。

图10 次优工序搜索邻域

2.8 算法流程

通过将不同优势的算法结合，可以解决某一种算法的不足和缺陷。通过结合遗传算法与本法改进的变邻域搜索算法，设计出针对FJSP的混合优化算法，同时对选择、交叉、变异三种遗传操作产生的群体中的个体解码之后，再利用迭代贪婪策略对前10%的种群进行优化，然后再进行变邻域搜索，获得新的可行解，直到满足终止条件，输出最优解。混合算法流程图如图11所示。

图11 混合算法流程图

3 实验仿真与分析

为了检验基于两级邻域搜索混合算法求解FJSP问题的性能，利用Python语言编程，对FJSP问题基准算例进行测试，使用win10系统，计算机中央处理器的主频为2.30 GHz，内存为8.0 GB。算法参数设置如下：种群规模PopSize为100，交叉概率为0.9，变异概率为0.1，最大代数为50代。

本研究采用Brandimarte十组实例（BRdata）中的MK03和MK08进行实验，分别采用混合变邻域遗传算法和遗传算法进行求解，重复20次，分别记录这两种算法求得解集中的最优个体目标函数值，进行比较。得到MK03的max为204 s，如图12所示。MK08的max为523 s，如图13所示。

如图14所示，由于采用了全局选择，局部选择和随机选择的初始解构造，使得算法初始解为235 s，优于遗传算法初始解242 s。同时，本研究算法在21代达到最优，遗传算法在34代达到最优，迭代贪婪的加入增强了算法的收敛速度，新的邻域结构使得搜索更加全面，同时使得结果更加稳定。

图12 MK03基准案例的调度甘特图

图13 MK08基准案例的调度甘特图

最优个体/Cmax迭代次数/N

如表1所示，对MK03用遗传算法和本研究算法分别运行20次，遗传算法的解平均值为210.3 s，本研究算法的平均值为204.7 s。而达到最优的代数，遗传算法为63.3代，本研究算法为21.7代。可以看出本研究算法明显更快，且平均值优于遗传算法得到的结果。

表1 遗传算法与混合算法20次试验结果对比

表2 不同算法对Brandimarte算例MK01-MK10求解结果对比（单位：s）

如表2所示，对Brandimarte算例中的MK01-MK10问题，利用GA、文献[21]中的启发式算法、文献[22]中的禁忌粒子群混合算法和本法混合变邻域遗传算法进行求解可以看出，本法混合变邻域遗传算法相对于另外两种算法求得的最优解更接近理论最优，其中MK01、MK02、MK03、MK07、MK08均得到理论最优解。

4 结论

针对遗传算法局部搜索能力不足，搜索速度慢的缺陷，引入变邻域搜索算法。通过加入迭代贪婪策略，破坏原可行解并重构而获得更优的可行解。设计三种邻域结构，“跨机器工序搜索邻域”针对全局搜索更优加工机器，“同机器工序搜索邻域”则搜索能否在不变机器的情况下改变加工先后顺序搜索更优加工机器，“次优工序搜索邻域”则尝试次优加工机器能否实现全局最优。通过国际通用算例MK03、MK08进行仿真，结果证明本研究算法的可行性和有效性。

[1] 赵诗奎.求解柔性作业车间调度问题的两级邻域搜索混合算法[J].机械工程学报, 2015, 51(14): 175-184.

[2] 王静云,王雷,李佳路.改进遗传算法求解带不相关并行机的HFSP[J].井冈山大学学报:自然科学版,2021,42(4):81-86.

[3] Zhao B, Gao J, Chen K, et al. Two-generation Pareto ant colony algorithm for multi-objective job shop scheduling problem with alternative process plans and unrelated parallel machines [J]. Journal of Intelligent Manufacturing, 2018, 29(1):93-108.

[4] Shivasankaran N, Kumar P S, Raja K V. Hybrid sorting immune simulated annealing algorithm for flexible job shop scheduling[J]. International Journal of Computational Intelligence Systems, 2015, 8(3):455-466.

[5] 任剑翔,梁雨佳,魏佳蓓,等.基于双向奔袭策略的改进狼群算法研究[J/OL].控制工程.https://doi.org/10.14107/j. cnki.kzgc.20220059,2022-05-25.

[6] 陈魁,毕利.改进粒子群算法在考虑运输时间下的FJSP研究[J].系统仿真学报,2021,33(4):845-853.

[7] 李佳路,王雷,王静云.改进遗传蜂群算法求解分布式柔性作业车间调度问题[J].井冈山大学学报:自然科学版,2021, 42(6):74-81.

[8] Chen R H, Yang B, Li S, et al. A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem[J]. Computers & Industrial Engineering, 2020, 149:1-12.

[9] 李佳磊,顾幸生.双种群混合遗传算法求解具有预防性维护的分布式柔性作业车间调度问题[J].控制与决策, 2023,38(2)475-482.

[10] 刘巍巍,马雪丽,刘晓冰.面向柔性作业车间调度问题的改进变邻域搜索算法[J].计算机应用与软件,2015, 32(4):234-238.

[11] 桂林,李新宇,高亮.作业车间调度问题的新型邻域结构[J].华中科技大学学报:自然科学版,2021,49(7):103-106,119.

[12] 米恬怡,唐秋华,成丽新,等.融合强化学习与变邻域搜索的柔性作业车间调度研究[J/OL].工业工程与管理. https://kns.cnki.net/kcms/detail/31.1738.T.20220721.1141.002.html, 2022-07-22.

[13] 黄学文,陈绍芬,周阗玉,等.求解柔性作业车间调度问题的一种新邻域结构[J].系统工程理论与实践,2021, 41(9):2367-2378.

[14] 薛玲玲.作业车间调度的块结构邻域搜索遗传算法[J].计算机集成制造系统,2021,27(10):2848-2857.

[15] 王家海,李营力,刘铮玮,等.柔性作业车间调度的精确邻域结构混合进化算法[J].同济大学学报:自然科学版, 2021,49(3):440-448.

[16] 张桐瑞,吴定会.混合竞争群优化算法求解柔性车间调度问题[J].控制工程,2021,28(9):1820-1828.

[17] 董海,王瀚鹏.基于种群迭代贪婪算法无等待流水车间调度[J].控制工程,2023,30(5):944-953.

[18] 秦浩翔,韩玉艳,陈庆达,等.求解阻塞混合流水车间调度的双层变异迭代贪婪算法[J].控制与决策,2022, 37 (9):2323-2332.

[19] 吴树景,游有鹏,罗福源.变邻域保优遗传算法求解柔性车间调度问题[J].计算机工程与应用,2020,56(22):236-243.

[20] 崔琪,吴秀丽,余建军.变邻域改进遗传算法求解混合流水车间调度问题[J].计算机集成制造系统,2017, 23(9): 1917-1927.

[21] Ziaee M. A heuristic algorithm for solving flexible job shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology,2014,71(1-4):519-528.

[22] Henchiri A, Ennigrou M. Particle swarm optimization combined with tabu search in a multi-agent model for flexible job shop problem[C]. Proceedings of the 4th International Conference on Advances in Swarm Intelligence, Harbin China: Springer, 2013:385-394．

RESEARCH ON FLEXIBLE JOB SHOP SCHEDULING PROBLEM BASED ON HYBRID VARIABLE NEIGHBORHOOD GENETIC ALGORITHM

LIU Ming-hao1,*CAI Jing-cao1, WANG Lei1, GU Han1, ZHANG Mao-shan2, TAN Tie-long3

（1. School of Mechanical Engineering, Anhui Polytechnic University, Wuhu, Anhui 241000, China; 2. Wuhu Hangyi Integrated Equipment Co., Ltd, Wuhu, Anhui 241000, China; 3. Wuhu Kepu Intelligent Equipment Co., Ltd, Wuhu, Anhui 241000, China）

Aiming at flexible job-shop scheduling problem, a hybrid variable neighborhood genetic algorithm was proposed to establish a mathematical model with the goal of maximum completion time. In this paper, three initialization methods were used to ensure the quality of the initial solution. The genetic algorithm was used for preliminary search, and the search results were optimized by iterative greedy strategy to improve the quality of the solution. Three kinds of neighborhood structures, "cross-machine process search neighborhood", "same-machine process search neighborhood" and "suboptimal process search neighborhood", were designed to strengthen the local search ability. Through the test of the international general flexible job shop scheduling benchmark example, the experimental results showed that the proposed algorithm could effectively solve the flexible job shop scheduling problem. The introduction of iterative greedy strategy and improved neighborhood structure could significantly improve the stability and iteration speed of the algorithm.

flexible job shop scheduling; mixed variable neighborhood; genetic algorithm

1674-8085（2023）05-0099-08

TH189

A

10.3969/j.issn.1674-8085.2023.05.015

2022-11-17；

2023-3-15

安徽省高校自然科学重点科研项目(2022AH050978,2023AH052915)；安徽省高校优秀拔尖人才培育项目(gxbjZD2022023)；安徽工程大学-鸠江区产业协同创新专项基金项目(2022cyxtb6)；芜湖市科技计划项目(2022jc26)

*蔡劲草(1993-)，安徽蒙城人，讲师，博士，主要从事智能车间调度及智能优化算法研究(E-mail:caijingcao@foxmail.com)