车间调度问题研究现状与发展趋势

罗哲　朱光宇

摘  要：文章从车间调度问题的实际应用特性出发，综述了当前车间调度问题在国内外的研究現状，在总结分析当前研究车间调度问题的相关方法与技术的基础上，指出了当前在车间调度问题研究中存在的问题与不足，并提出了几个车间调度问题研究的发展趋势，以期为后续车间调度问题的不断深入以及更好地为生产实际服务提供可借鉴的方向。

关键词：车间调度;生产计划;调度方法

中图分类号：TP278        文献标志码：A         文章编号：2095-2945（2020）23-0123-02

Abstract： Starting from the practical application characteristics of the workshop scheduling problem， this paper summarizes the current research status of the workshop scheduling problem at home and abroad， and on the basis of summarizing and analyzing the relevant methods and technologies of the current research on the workshop scheduling problem， this paper points out the problems and deficiencies existing in the research of workshop scheduling problem， and puts forward the development trend of several workshop scheduling problems， in order to provide a reference direction for the continuous deepening of the follow-up workshop scheduling problems and for the production of actual services.

Keywords： workshop scheduling; production planning; scheduling method

1 概述

生产调度指的是企业在生产过程中，以生产为中心，通过对有效的资源进行合理指挥、控制和调节，进而达到提高经济效益目的的过程。近年来随着科学技术的发展，人们已经成功地将加工制造技术与现代管理技术、自动化技术、信息技术以及系统工程技术等学科相融合，提出了许多先进的制造模式，这些模式都是通过内外资源合理的分配、缩短加工时间以及降低成本等方法来解决诸多企业所面临着的许多共性问题。而生产调度的主要作用就是要对有限的资源进行有效合理配置和优化，使待加工的作业能够均衡地安排到每台处理机上， 在满足加工系统约束条件的前提下最大程度上满足客户和企业所需求的指标。因此，生产调度就成为了各种先进加工制造模式的核心内容和重要组成部分。

自1945年Johnson提出了流水车间调度的问题之后，许多的研究学者逐渐开始注重车间调度问题的研究，并针对解决车间调度问题的算法的有效性和复杂度展开研究。在以后的几十年里，随着对车间调度研究的逐渐深入，许多的专家学者将应用数学、运筹学、工程技术等领域中的方法应用到车间调度问题中，在此期间形成了许多解决问题的理论和方法，并解决了许多典型的调度优化问题。本文分别就国内外在车间调度问题上的研究现状，以及发展趋势进行探讨。

2 车间调度问题国外研究现状

国外对车间调度的研究开始得很早，研究成果也比较多，主要的研究方法有：

2.1 传统的调度方法

主要有1999年Rios R.Z.等人运用运筹学的方法解决一类多机器的流水车间调度问题，并结合分支定界法对其进行求解。2001年Rabadi G.等也是应用了分支定界法解决有公共交货期和独立调整时间的单机提前/拖期调度问题，从而得到了令人满意的结果。2002年chen M等人使用了混合整数规划模型对制造生产过程最小化加工时间调度问题进行优化，并得到了很好的结果。

由于单纯的运筹学方法的计算复杂度较大，只能对小规模的车间调度问题进行求解。因此，在解决大规模的车间调度问题时，将运筹学与其它算法相结合的方法来降低计算复杂程度。主要代表有： 2003年Mohanasundaram K.M等提出了基于调度优先规则来解决最大流程时间、阶段延迟和最大作业拖期的一类多层制造作业车间问题等。

2.2 智能调度方法

实际生产过程中，调度问题是一个规模较大，约束较多的问题，在这种情况下要寻找车间调度的最优解是比较困难的，因此只能通过一种方法能够在较短的时间内找到问题的近似解。20世纪80年代以来由于神经网络、遗传算法等人工智能方法的逐渐提出，很多学者和专家将这些人工智能算法应用到生产调度问题上并得到了很大的发展。主要的方法有：

（1）基于统计式全局搜索技术的智能算法，主要包括模拟退火算法、禁忌搜索算法等，代表文献有： 2004年Armentano V.A等应用禁忌搜索算法来解决双目标流水车间调度问题。2006年Mohammad S.M等用禁忌搜索算法方法来解决最大完工时间最小依赖于设置的柔性作业车间调度问题。2008年Olivier L等人提出了一种新的禁忌搜索方法来取代自由搜索的目标函数来解决生产项目调度问题。

（2）神经网络方法，它是根据生物神经网络的行为特征提出的一种并行信息处理的智能搜索算法。在车间调度中应用的代表为：2005年Akyol D.E等人提出了双层反馈神经网络，以此来解决最小化提前和拖期连接权的多机调度问题。2006年Noorul H等将神经网络的方法用来解决双目标流水车间调度问题等等。

（3）遗传算法，它是根据生物群体的物竞天择的进化理论提出的一种具有较好的并行性和鲁棒性特征的优化算法，所以遗传算法被广泛的应用在实际生产调度问题中。同时遗传算法可以与其他算法相结合，能够更好地解决车间调度问题，典型代表有：2006年chen K.J.通过订单的信息确定了以最小化机器空闲时间和提前/拖后惩罚为目标的动态车间调度，将冻结间隔的优先规则和遗传算法结合的方法解决这个问题。2008年Vicente V.等人应用混合遗传算法对资源受限的项目调度问题进行求解。2010年L. De Giovanni等采用一种改进的遗传算法来解决分布式柔性作业车间调度问题。

3 车间调度问题国内研究现状

由于我国在加工制造业技术上存在滞后，所以在生产过程中一般主要还是依靠调度人员长期积累的经验对加工作业进行分配。但随着国外对车间调度研究方法的不断传入，国内也掀起了一股研究车间调度问题的热潮。研究工作主要集中在一些重点高校的实验室，而目前这些实验室还处于开发试运行的初始阶段，主要的研究成果有：2005年徐震浩将模糊数学理论引入到免疫算法中提出了模糊免疫调度算法来解决一种不确定条件下的流水车间调度问题[1]。2006年牛刚刚等根据细胞分裂和变异的思想提出了一种免疫算法解决静态作业车间调度问题[2]。2009年张长胜提出了一种将遗传操作引入到粒子群算法中的自适应混合粒子群进化算法来解决最小化加工完工时间的流水车间调度问题[3]。2010年李俊青等人提出了一种带有Pareto档案集的混合禁忌搜索算法来解决最小化最大完成时间、总机床负荷和最大机床负荷的一种多目标柔性作业车间调度问题[4]。2011年王伟玲等提出一种将正逆序调度方法与生成调度活动的遗传算法相结合的双种群遗传算法来求解多目标作业车间调度问题[5];2015年朱光宇等利用灰熵并行关联度作为优化计算的适应度值计算策略，采用差分算法与遗传算法相结合的混合优化算法解决多目标作业车间调度问题[6];2019年宋存利等提出一种改进贪婪遗传算法求解针对最小化最大完成时间的带有不相关并行机的流水车间调度问题[7]。

4 车间调度研究存在的问题与发展趋势

国内外针对不同类型的生产调度问题展开研究已有30多年的历史，研究的内容和应用的范围也极其广泛，但多数研究的是单机单目标调度和多机单目标调度，而对多目标调度的研究还很少，而现实生活当中车间调度问题的多目标性一直普遍存在，而这种多目标性更加符合现实生产情况。企业一般在生产加工时，不仅要求减少工件的空闲时间、客户的等待时间、产品的生产周期，而且还要减少延期费用、存储费用等，所以实际的生产调度问题是一种复杂的多目标优化问题。虽然国内外的一些专家学者对多目标车间调度问题也有一些研究，但是在对多个目标的均衡问题上，如何避免主观人为因素的影响，对于具体问题能够准确合理的确定每个目标的权重比较困难，这将是后续车间调度问题研究的一个重点。

大多数的车间调度问题属于一类非常复杂的组合优化问题，且在实际生产过程当中车间调度经常会受到各种各样的因素干扰，如机器故障，需求市场的波动和客户对产品要求的变更等等。由于这些因素的影响使得我们无法精确的求出车间调度问题的最优解，只能寻找一种能够得到近似最优解的方法。而人工智能算法能在合理的时间内产生令人相對满意的调度，所以这些方法已经广泛应用于实际生产调度中。在实际车间调度中还存在另一个问题，这就是生产车间计划与生产车间调度通常是分开进行的，这可能造成车间计划在实际调度中产生不可行的情况，所以对车间调度的进一步研究还要综合考虑这个两方面，以便能够得到总体的优化。现在的加工都是在柔性制造环境下进行的，柔性车间作业调度问题也将会成为接下来研究的重点和方向。

参考文献：

[1]徐震浩，顾幸生.不确定条件下的flow shop问题的免疫调度算法[J].系统工程学报，2005，20（4）：374-380.

[2]牛刚刚，孙树栋，余建军，等.免疫进化算法求解静态job-shop调度[J].机械工程学报，2006，42（5）：87-91.

[3]张长胜，孙吉贵，欧阳丹彤，等.求解车间调度问题的自适应混合粒子群算法[J].计算机学报，2009，32（11）：2137-2146.

[4]李俊青，潘全科，王玉亭.多目标柔性车间调度的Pareto混合禁忌搜索算法[J].计算机集成制造系统，2010，16（7）：1419-1426.

[5]王伟玲，李俊芳，王晶.求解多目标作业车间调度问题的双种群遗传算法[J].计算机集成制造系统，2011，17（4）：808-815.

[6]朱光宇，杨志峰，陈旭斌.基于灰熵并行分析法的多目标作业车间调度优化[J].计算机系统应用，2015，24（4）：176-183.

[7]宋存利.求解混合流水车间调度的改进贪婪遗传算法[J].系统工程与电子技术，2019，41（5）：1079-1086.