基于遗传算法的流动车间作业调度

刘明，索良泽

（贵州大学电气工程学院，贵州 贵阳 550025）

0 引言

一直以来，调度问题都是一个极其重要的课题。在各种工业活动中，制订一个高效的调度计划是不可或缺的组成部分。这就要求计划制订者要做出满足任务要求的调度安排，并根据任务确定最晚完工时间。此问题最具挑战性的地方在于如何找到理想的调度计划，既满足任务要求又是问题的最优解[1-3]。在数学上，通常将此类问题归结为组合优化问题，同时也属于NP完全问题，其特点是还没有找到一种算法可以在多项式时间内求出其最优解。由于启发式算法对解决此类问题有着很明显的优点，如算法简单易于设计，计算效率高等，所以一直以来人们使用启发式算法来对调度问题进行求解。在本文中，研究调度问题中的一种典型问题，车间调度问题[4-8]。

车间作业调度问题是生产管理中必须要面临的问题。调度计划的好坏对生产成本和生产时间有直接的影响。通过科学的调度方法，车间内的资源可以得到更合理高效的利用，同时还能以最快的速度将要加工的零件送入车间，加工完成的零件运到下一车间[9]。车间调度涉及到每一批加工的零件在时间、空间及设备等各种资源上的协调和分配，这属于运筹学中的动态调度问题。

我们常常需要考虑实际的约束条件，根据现有的资源去完成各种加工任务，给出不同工件在相关机器上的加工时间和顺序，使得相关的性能指标达到最优，这不仅能有效的提高企业的作业效率，还能为企业带来巨大的经济效益。车间作业调度问题解决的关键在于算法，因此，研究出精确而高效的调度算法不仅是该领域重要的课题，还是实际生产中的迫切需求。本文应用遗传算法对车间调度问题进行求解，目的在于熟悉遗传算法，并能将其应用于实际问题中[10]。

1 车间作业调度问题模型

车间作业调度是一类有顺序约束的资源配置问题，也属于组合优化类问题。随着工业水平的快速发展，车间作业调度的研究越来越重要。在生产工程中若能优化流程，提高加工效率，缩短产品的加工时间，无疑对于工业生产来说是获取更大利润的一个措施。虽然研究车间作业调度能带来巨大的利益，而且这方面的研究也有了近50年的历史，但是由于车间作业调度问题种类繁多，所含约束非常多，并且大多是非线性约束，所以在实际应用中还未有一整套完整的理论和方法[11-13]。

一般来说，为了理论研究，车间作业调度问题都会做一些简化假设，以便于建立数学模型。经典的车间作业调度问题可以简单描述为：有一个待加工的工件集合和一个用来加工工件设备的集合，每一个工件有多道工序，而每一道工序需要特定的加工设备，工件需要在某一段时间内在该设备上进行加工。调度问题就是将工件在某一段时间内放在某台机器上进行加工。在理论上研究车间调度问题时，常常基于以下简化假设：

1）同时刻，一个工件只能在一台设备上加工；

2）每台设备在同一时刻只能加工一个工件；

3）一个工件的不同工序需要在不同设备上加工。也就是说，一个工件的一道工序只在一台设备上完成，一台设备只加工一个工件的一道工序；

4）只有同一个工件的工序有前后顺序约束，工件之间不影响加工顺序；

5）在加工过程中，不考虑两道工序之间的转运时间，即上一道工序完成立即就开始下一道工序；

6）每一道工序作为一个完整体，不可分割，即是说工序开始之后，除了加工结束，否则不能将工件拿开；

7）工件的集合，机器的集合，加工的顺序和每一道工序需要的时间都是已知的。一些在过程中花费的时间统统算入加工时间内，保持两道工序间是连续进行加工的。

以上假设基本解析了车间作业调度问题的约束条件。这些约束可以总结为两个方面，一个是加工的顺序约束，另一个方面为加工的资源约束。也即工件的加工要按照一定的先后顺序依次进行加工，另外，机器数量有限，在一个时间段只能加工一个工件，而其余工件就可能发生排队等待的情况。那么，车间作业调度问题就可以看做是资源约束和顺序约束下的组合优化问题，问题的核心就是如何在这两个约束条件下将工件的工序分配到加工机器上使得某个指标性能达到最优，例如使整个加工任务总时间最小[14-16]。

2 算法简述

遗传算法又被称为GA（Genetic Algorithms），它是在20世纪60年代初由美国Michigan大学的Holland教授提出的，根据自然界的遗传机制和生物进化论而成的一种并行随机搜索最优化方法[17]。由于遗传算法搜索的高效性，又适用于解决搜索空间巨大的复杂组合优化问题，并在生产调度中已有广泛成功的应用先例，所以本文采用遗传算法来对车间调度问题进行求解。

遗传算法搜索过程中的基本操作为：复制、交叉、变异。正是由于这几种操作的存在才使得遗传算法具有不断向目标搜索前进的能力，而这些操作又都是具有概率性的，所以在搜索进程中具有很大的灵活性和高速度性，随着搜索进程的发展越来越多的优良个体会产生，逐渐逼近问题的最优解[18-20]。

遗传算法的5个要素是编码、适应度函数、初始种群、遗传算子和参数设置。本文按照遗传算法在流动车间作业调度问题应用上的设计步骤对问题进行求解。具体步骤如下：

（1）编码

本文采用M行N列的二维数组对问题进行编码，M是工件数量，N是加工所需工序数量。数组中第i行第j列的元素代表第i个工件在第j个工序上加工的设备编号。这种编码是根据工件在对应工序上加工设备编号的排列组合生成的，十分直观、便于计算。如表1所示：

表1 工件信息表Table 1 Workpiece information sheet

（2）适应度函数

对于M个工件，N个工序，第 j道工序有Ki台机器（1≤j≤N）的问题来说。设第i个工件在第j个工序上加工的时间为

那么对于第一个工序，按机器编号顺序来依次确定各工件的加工时间。都选择1号机器的工件之间进行排序，发生等待。依次按此规则进行到Ki号机器。依上例就是先进行1号工件的加工然后2号工件等待，而3号工件没有约束和1号工件一起开始加工，3和5号工件也有同样约束。以此规则便能定下5个工件在第一个加工工序上的先后顺序和确定加工时间。即1号工件在t11时刻结束第一个工序的加工而2号工件在 t11+t21时刻结束，以此类推。

对于第二个工序到第N个工序，则需考虑两个约束。一是工件要在前一个工序结束后才能开始，二是工件要在机器上的前一个工件加工完成后才能进行加工。在没有违反这些约束的条件下工件的加工先后顺序对结果没有影响，所以按照编号顺序来确定工件加工的先后顺序（编号小的先进行加工）。最终，整个加工任务的结束时间就为最后一个工序结束时5个工件中加工时间的最大值。到此自适应函数建立完毕，并将此作为遗传个体优良好坏的评价标准。计算出每个个体的适应度函数，选择函数值较小的作为优良个体，淘汰不良个体，以优良个体作为父代继续遗传下去。

（3）对种群进行初始化

遗传算法的执行效率和运行结果受种群大小的影响，种群太大会增加计算的复杂度，延长收敛时间，太小则不能提供足够的采样点。因此，我们通常将种群的个体设置为20～100之间。本次实验采用的种群规模为100，种群个体皆为随机产生，即上述表格中的机器编号都是随机产生的。

（4）遗传算子

一般而言，遗传算子包括变异算子、交叉和选择。此次实验中的选择方式为先进行交叉产生新的个体，即将新产生的个体和原来的个体组成一个200个个体的种群然后进行两两随机配对竞争，将适应度函数值大的个体淘汰，留下较小的那个又形成100个个体的种群。

交叉，将初始种群中的个体随机进行两两配对交叉，随机选择交叉点进行单点交叉。行交叉是将一个个体在交叉点以上的行与另一个个体在交叉点以上的行进行交换，从而产生新的个体。列交叉是将个体在交叉点以前的列与另一个个体交叉点以前的列进行交换产生新的个体；变异，选取变异概率为0.1，随机选择一个变异点，将其改变为一个不违反规则的随机数。

（5）参数设置

即确定好初始种群大小，交叉概率，变异概率，终止迭代次数等参数。本例中采用的初始种群大小为100，交叉概率为1，变异概率为0.1，终止迭代次数为100。

3 算例分析

在本例中求解5个工件经过4个工序的车间调度问题。为简单起见，以平均加工时间作为每个工件在相应工序上的加工时间。如下表：

表2 车间加工信息表Table 2 Workshop Processing Information table

图1 调度结果图Fig. 1 Scheduling results graph

矩形块中的数字代表工件选择的机器编号，矩形长度代表时间，宽度表示工件编号。从该甘特图中（图1）可以看出此方案即是调度的最优方案，实现了加工时间最小的目标。

从图2中可以看出每经过一代个体的遗传变异，种群中平均适应度函数值的总体趋势是在变小的，经过约35代的遗传基本稳定在最优解68处，也即说明经过上述遗传算法处理过后的群体的适应度是在不断增强的。

图2 各代种群平均适应度函数值Fig. 2 Average fitness function value of each generation population

4 结论

通过算例可知，针对此类车间调度问题，本文设计的遗传算法可以很好的求解得到调度结果。本文提出了一种直接的编码方式，便捷易处理。文中所述的适应度函数相较于其他遗传算法具有直观、便于计算等优点。文中设计的遗传算子采用全随机的方式，可以最大限度的扩充搜索空间。有两种选择复制的方式可供随机挑选，保证了新种群中个体的多样性同样扩大了搜索空间。两两随机配对竞争的策略使得种群具有保留最优个体的能力，保证了基因的优良性。

[1] 张长水, 阎平凡. 解Job-Shop调度问题的神经网络方法[J]. 自动化学报, 1995, 21(6): 706-712.ZHANG Chang-shui, YAN Ping-fan. Neural Network Method for Solving Job-shop Scheduling Problem [J]. Acta Automatica Sinica, 1995,21(6): 706-712.

[2] 黄彦曌, 王科社, 黄喜淦, 等. 基于遗传算法的滚珠丝杠副控制器设计与仿真[J]. 新型工业化, 2017, 7(11): 5-10.HUANG Yan-zhao, WANG Ke-she, HUANG Xi-gan, et al. Ball Screw Pair Controller Design & Simulation Based on Genetic Algorithm[J].The Journal of New Industrialization, 2017, 7 (11): 5-10.

[3] 王书锋, 邹益仁. 车间作业调度(JSSP)技术问题简明综述[J]. 系统工程理论与实践, 2003, 23(1): 49-55.WANG Shu-feng, ZOU Yi-ren. Techniques for the Job Shop Scheduling Problem: a Survey[J]. Systems Engineering-Theory & Practice,2003, 23(1): 49-55.

[4] 王永辰, 肖伸平, 刘先亮. 基于改进自适应遗传算法的配电网重构[J]. 新型工业化, 2015, 5(8): 6-10.WANG Yong-chen, XIAO Shen-ping, LIU Xian-liang. Distribution System Reconfiguration Based on Improved Genetic Algorithm[J]. The Journal of New Industrialization, 2015, 5(8): 6-10.

[5] 沈斌, 周莹君, 王家海. 基于自适应遗传算法的流水车间作业调度[J]. 计算机工程, 2010, 36(14): 201-203.SHEN Bin, ZHOU Ying-jun, WANG Jia-hai. Flow Job Shop Scheduling Based on Self-adaptive Genetic Algorithm[J]. Computer Engineering,2010, 36(14): 201-203.

[6] 曲媛, 杨晓伟. 关于流水车间调度问题的综述[J]. 经营管理, 2007(8): 24-25.QU Yuan, YANG Xiao-wei. A summary of flow shop scheduling problem[J]. Sci-Tech & Development of Enterprise, 2007(8): 24-25.

[7] SIM S T, YEO K T, LEE W H. An expert neural network system for dynamic job shop scheduling[J]. Engineering Library, 1994, 32(8): 1759-1773.

[8] Ding Y R, Cai Y J, Sun P D. The Use of Combined Neural Networks and Genetic Algorithms for Prediction of River Water Quality[J]. Journal of Applied Research and Technology, 2014, 12(3): 493-499.

[9] KHAN A, BAIG A R. Multi-Objective Feature Subset Selection using Non-dominated Sorting Genetic Algorithm[J]. Journal of Applied Research and Technology, 2015, 13(1): 145-159.

[10] Kumar M, Guria C. The elitist non-dominated sorting genetic algorithm with inheritance (i-NSGA-II) and its jumping gene adaptations for multi-objective optimization[J]. Information Sciences, 2017(s382-383): 15-37.

[11] 刘民, 吴澄, 蒋新松. 用遗传算法解决并行多机调度问题[J]. 系统工程理论与实践, 1998, 18(1): 14-17.LIU Min, WU Cheng, JIANG Xin-song. Genetic Algorithm Method for Identical Parallel Machine Scheduling Problem[J]. Systems Engineering-Theory & Practice, 1998, 18(1): 14-17.

[12] 郑文秀, 房瑞东, 王璞, 等. 基于混合遗传算法的线路板AOI运动控制系统设计[J]. 新型工业化, 2017, 7(2): 60-66.ZHENG Xiu-wen, FANG Rui-dong, WANG Pu, et al. Hybrid Genetic Algorithm for the AOI Motion Control System of PCB[J]. The Journal of New Industrialization, 2017,7(2): 60-66.

[13] 葛继科, 邱玉辉, 吴春明, 等. 遗传算法研究综述[J]. 计算机应用研究, 2008, 25(10): 2911-2916.GE Ji-ke, QIU Yu-hui, WU Chun-ming, et al. Summary of genetic algorithm sresearch[J]. Application Research of Computers, 2008,25(10): 2911-2916.

[14] 边霞, 米良. 遗传算法理论及其应用研究进展[J]. 计算机应用研究, 2010, 27(7): 2425-2429.BIAN Xia, MI Liang. Development on genetic algorithm theory and its applications[J]. Application Research of Computers, 2010, 27(7):2425-2429.

[15] 孔玲爽, 潘晓楠, 肖伸平, 等. 基于改进拟态物理学算法的配电网故障区段定位[J]. 新型工业化, 2015, 5(5): 9-14.KONG Ling-shuang, PAN Xiao-nan, XIAO Shen-ping, et al. Fault Location in Distribution Network Based on Improved APO[J]. The Journal of New Industrialization, 2015, 5(5): 9-14.

[16] 马永杰,云文霞. 遗传算法研究进展[J]. 计算机应用研究, 2012, 29(4): 1201-1206.MA Yong-jie, YUN Wen-xia. Research progress of genetic algorithm[J]. Application Research of Computers, 2012, 29(4): 1201-1206.

[17] 常俊林, 张春慨, 邵惠鹤. 求解一类并行多机调度问题的混合启发式算法[J]. 计算机仿真, 2004, 21(3): 121-123.CHANG Jun-lin, ZHANG Chun-kai, SHAO Hui-he. A hybrid heuristic algorithm for solving a class of parallel multi-machine scheduling problems[J]. Computer Simulation, 2004, 21(3): 121-123.

[18] 徐加利, 管章玉. 协作无线网络中基于遗传算法的联合中继选择与认知频谱接入机制[J]. 新型工业化, 2014, 4(5): 41-47.XU Jia-li, GUANG Zhang-yu. Joint relay selection and cognitive spectrum access based on Genetic Algorithm in cooperative wireless networks[J]. The Journal of New Industrialization, 2014, 4(5): 41-47.

[19] 于莹莹, 陈燕, 李桃迎. 改进的遗传算法求解旅行商问题[J]. 控制与决策, 2014, 29(8): 1483-1488.YU Ying-ying, CHEN Yan, LI Tao-ying. Improved genetic algorithm for solving TSP[J]. Control and Decision, 2014, 29(8): 1483-1488.

[20] 韩铖, 张彦军. 基于遗传算法的四旋翼飞行器最优控制[J]. 电光与控制, 2018, 25(1): 28-33.HAN Cheng, ZHANG Yan-jun. Optimal Control for Quad-rotor Aircrafts Based on Genetic Algorithm[J]. Electronics Optics ＆ Control,2018, 25(1): 28-33.