基于遗传算法的多工序多机器调度优化研究

摘  要： 随着人民生活质量的提高，消费者对定制化生产提出了更高的要求，此外，在新的经济环境下，降本增效对于提升制造企业的发展能力具有重要的意义，基于此，本文提出了基于遗传算法的多工序多机器调度优化研究。首先，设计了基于完工时间最小化的多工序多机器加工约束的生产调度优化模型;其次，采用遗传算法设计了求解上述生产调度优化模型的算法;最后，通过案例验证了本文构建的优化模型及设计的优化算法，并绘制了以最小化完工时间为优化目标的生产调度甘特图。研究结果表明，本文构建的模型及设计的算法具有一定的实用性，可指导企业制定较优的生产调度方案。

关键词： 制造企业;生产调度;遗传算法;完工时间

中图分类号： TP39    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2019.06.027

本文著录格式：周福来. 基于遗传算法的多工序多机器调度优化研究[J]. 软件，2019，40（6）：123126

【Abstract】： With the improvement of people's living quality， consumers put forward higher requirements for customized production. In addition， in the new economic environment， reducing costs and increasing efficiency is of great significance to enhance the development ability of manufacturing enterprises. Based on this， this paper proposes a multi-process and multi-machine Scheduling Optimization Research Based on genetic algorithm. Firstly， a production scheduling optimization model with multi-process and multi-machine constraints based on minimum completion time is designed; secondly， the genetic algorithm is used to design the algorithm for solving the above production scheduling optimization model; finally， the optimization model and the optimization algorithm designed in this paper are verified by a case study， and the production scheduling Gantt with the objective of minimizing completion time is drawn. Graph. The results show that the model and algorithm constructed in this paper have certain practicability and can guide enterprises to formulate better production scheduling schemes.

【Key words】： Manufacturing enterprises： Production scheduling; Genetic algorithm; Completion time

0  引言

制造業在国民经济的发展过程中起着重要的作用，特别是在经济进入新常态下，我国的经济发展速度也进入了全新的发展阶段，为提升我国经济发展质量，国家政府先后制定了一系列的利好政策。对于生产制造企业而言，如何降低生产制造成本对于适应新的经济发展宏观环境具有重要的积极作用，然而，在生产制造过程中，对企业或行业提高生产效率和效益是至关重要的[1-2]，由于生产调度计划安排不当会给企业造成不必要的浪费，此外还容易出现因不能及时交付客户产品而引发的市场竞争力有所下降等问题，因此，再此背景下研究生产调度优化问题具有重要的现实意义。

针对生产制造过程中的调度问题，近年来国内外相关研究学者展开了大量的研究工作，并取得了一系列的研究成果。李占丞研究了以包含订货、采购、库存以及拖期惩罚成本的期望总成本最小化为目标[3-4]，Jurgen Branke.对各种调度问题进行广泛的分类，并回顾这些问题类的重要理论发展，将现有的理论与生产调度实践进行对比研究[5-6]，Xiao， Lei结合一系列系统的群预防性维护和生产调度，建立了联合优化模型，提出了一种联合优化模型[7-8]，在生产调度系统（PSS）与集成制造环境中的其他单元（决策者和软件系统）合作的背景下，研究了重新调度问题[9-10]，Carpentier S在考虑地质不确定性的情况下，提出了一种随机整数规划模型，以优化地下采矿作业的长期调度为研究目标展开了研究[11]，闫雪丽基于状态设备网络和特定事件点概念，建立非线性的连续时间间歇生产调度模型[12]，颜静针对多品种小批量生产为求快速响应订单生产所造成的生产中“半成品库存高、成品订单准时交货率低”的问题，建立了以准时交货为目标的前推后拉式综合生产调度系统[13]，谢思聪在对比分析预制构件生产与一般制造业区别的基础上提出预制构件厂生产参数的量化途径[14]，Joly M讨论了在一家致力于开发和实施先进炼油厂生产调度（RPS）技术（即Petrobras的RPS系统）的能源公司中全面实施的一项开创性但大胆的企业级项目所获得的关键经验[15]。

虽然国内外相关研究学者针对生产调度问题近年来展开的深入的研究，也取得了一系列的研究成果，但是，在算法层次研究方面依旧存在着不足，诸如现有研究算法较难满足不同零部件不同工序可以在不同设备上进行加工的并行生产调度问题，而该问题的解决对于提升生产制造企业响应客户个性化的需求具有重要的意义，因此，本文从计算机编程的角度，以现代生产制造企业的生产调度为研究对象，研究了基于遗传算法的多工序多机器约束的生产调度优化问题。

1  问题描述及模型建立

2  算法设计

由于遗传算法在求解生产调度问题时具有求解速度快的优势，因此，本文采用编程技术进行编码，利用遗传算法进行求解上述优化问题，其中，编码设计、适应度函数、进化选择及交叉操作描述如下。

2.1  编码设计

本文采用整数的编码形式对染色体个体进行编码，其中每一条由整数组合而成的染色体表示求解生产制造过程中调度问题对应的一个可行解。其中在采用整数编码的染色体上边，前半段表示零部件以此经过生产线时所对应的加工顺序，后半段则表示不同的零部件的加工工序所对应的生产设备，即某一零部件的某到工序对应在该设备上完成加工。假设某一个体的编码形式为[2 3 4 5 6 7 8 1 2 3 4 5 6 7]，则该染色体有包括了两个信息，第一个信息为零部件的加工工序，即以此加工零部件2、零部件3、零部件4、零部件5……直到加工零部件8;第二个信息为所加工零部件对应设备，即这些零部件依次在设备1、设备2、设备3……设备7上边完成加工。

2.2  适应度函數值设计

由于本文求解的目标函数是如何合理地安排加工工序，使得总的生产加工完工时间最小化，因此，本文将目标函数值即完工时间作为适应度函数值，对种群进化及进行选择，其中适应度函数如公式（2）所示。

2.3  进化选择设计

2.4  交叉操作设计

在使用遗传算法求解生产调度优化问题时，其核心是模拟生物界的自然种群进化规律，实现种群的优胜劣汰进化，因此，进化操作在整个求解最优调度方案中起着关键性的作用，本文设计两点随机交叉法来实现整个种群的进化操作，其中，个体交叉操作过程示意图如图1所示。

在交叉操作过程中，首先，在一对染色体上随机选择两点作为交叉点;其次将这两条染色体对应的交叉点位置的基因片段进行交叉，例如图1中第一条染色体的交叉点为2，3，第二条染色体的交叉点为3，1，则经过交叉操作之后，第一条染色体的基因将变成为3，1，与此同时，第二条染色体对应的基因将变为2，3。然后，对多余的工序以及对应工序的加工机器进行调整，最终产生新的个体，即表示新的可行解产生。

3  案例分析

生产调度属于生产制造过程中的关键性技术问题，一个好的生产调度方案可以为企业有效降低加工成本，在本部分，本文将选择一个案例来说明本文设计的优化求解模型及算法在求解生产调度问题时具有一定的可行性与优势。现有10台机器负责加工6个零部件，每个零部件需要经过6道加工工序才能完成整个加工过程，某些零部件的不同加工工序可以选择在不同的机器上进行加工。其中，不同零部件加工工序可选的机器信息如表1所示。

不同零部件的不同工序在不同机器上加工的时间不同，其中，每一个零部件对应的不同工序在不同机器上的加工时间表如表2所示。

本文采用编程技术编写的遗传算法代码在Matlab软件上对生产调度优化问题进行求解，设置初始种群数为40，最大迭代次数为50次。通过Matlab软件求解出了满足加工时间最小化的生产调度方案，其中，最优结果对应下的生产调度方案甘特图如图2所示。

图2中，x轴表示加工时间，y轴表示加工机器。根据上图可以清晰地看出不同零部件对应的不同工序的生产计划调度安排，此外还可以看出不同加工机器对应的完工时间。在采用Matlab算法求解生产制造过程中的生产调度问题时，得到的进化迭代图如图3所示。

根据图3可以看出在求解生产调度优化问题过程中解的变化过程以及种群均值的变化过程，从图3中可以看出，本文设计的算法能够快速地在短时间内寻找出以完工时间为优化目标生产调度方案，且最早的完工时间为53，这说明了本文采用编程技术设计的优化算法能够较好地解决生产调度优化问题。

4  结论

本文以制造企业中制定生产调度的问题为对象展开了研究，构建了以最小化完工时间为最优的生产调度优化模型，基于遗传算法设计了求解该生产调度优化模型的算法，并选择案例对本文构建的模型及设计的算法进行了验证，结果表明本文构建的生产调度优化模型及设计的优化模型求解算法具有一定的实用性。

参考文献

[1] 徐俊刚， 戴国忠， 王宏安. 生产调度理论和方法研究综述[J]. 计算机研究与发展， 2004， 41（2）： 257-267.

[2] 卢宏， 孙鹏. 钢铁企业基于无线传感网的氧气实时优化调度[J]. 软件， 2018， 39（5）： 129-133.

[3] 李占丞， 刘晓冰， 薄洪光. 面向生产调度的订货量分配问题研究[J]. 工业工程与管理， 2016（2）.

[4] 杨继伟. 视频云源站的资源调度系统设计与实现[J].软件， 2018， 39（5）： 170-181.

[5] Jurgen Branke， Member， IEEE， et al. Automated Design of Production Scheduling Heuristics： A Review[J]. IEEE Transactions on Evolutionary Computation， 2015， 20（1）.

[6] 张春燕. 基于改进遗传进化算法的复杂作业流程调度[J].软件， 2017， 38（12）： 98-103.

[7] Xiao， Lei， Song， et al. Joint optimization of production scheduling and machine group preventive maintenance[J]. Reliability Engineering & System Safety， 2016， 146： 68-78.

[8] 李伟， 邓红涛， 陈红莉， 韩峰. 面向饲料产品的物流车辆调度系统设计[J]. 软件， 2016， 37（08）： 51-53.

[9] Kalinowski K， Grabowik C， Kempa W， et al. The role of the production scheduling system in rescheduling[J]. IOP Conference Series： Materials Science and Engineering， 2015， 95： 012140-.

[10] 彭超. 基于B/S模式下的煤礦生产调度系统开发设计与实现[J]. 软件， 2011， 32（04）： 23-25.

[11] Carpentier S， Gamache M， Dimitrakopoulos R. Underground long-term mine production scheduling with integrated geological risk management[J]. Mining Technology， 2016， 125（2）： 93-102.

[12] 闫雪丽， 韩豫鑫， 顾幸生. 基于状态设备网络的改进间歇生产调度模型[J]. 化工学报， 2018.

[13] 颜静， 朱伏平， 杨婉琳. 基于准时交货的多品种小批量生产调度系统研究[J]. 机械， 2017（4）.

[14] 谢思聪， 陈小波. 基于多层编码遗传算法的两阶段装配式建筑预制构件生产调度优化[J]. 工程管理学报， 2018.

[15] Joly M， Miyake M Y. Lessons learned from developing and implementing refinery production scheduling technologies[J]. Frontiers of Engineering Management， 2017， 4（3）.