◎1.2.3　Job-shop调度

制造系统的车间调度（Job-shop调度）问题是根据生产计划要求，对一项可以分解的工作，在尽量满足约束条件的前提下，通过下达生产指令，对生产任务进行排序，并通过分配资源，以获取产品成本、效率或者制造时间等的最优化，即车间调度就是要解决如何优化配置资源来较好地完成生产任务的问题。车间调度问题主要涉及三方面因素，即约束条件、优化性能指标和调度方案。其中，约束条件主要有产品的投产期、交货期、生产能力、原材料可用性、加工设备、加工顺序、批量大小和工艺路线等。这些约束条件属于确定性因素，而在车间调度过程中，设备故障、原材料供应变化、插单、生产任务变化调整、不同调度方案产生不同的作业切换时间等非正常情况具有随机性和不可预见性，调度过程中应作为不确定性因素考虑。

车间调度的目标就是在满足一系列约束条件下，优化生产系统的生产效率，提高系统生产能力，优化系统性能指标。常用的性能指标主要有最短生产周期、最小化总完工时间、最小化最大总提早/拖延时间、最小化最大作业切换时间和最大化设备利用率等。调度方案就是实现生产调度性能指标的最终解，比如一组排序。车间调度问题还会受到企业生产环境的影响，由于调度问题的优化目标、优化策略及优化模型可能存在不同，因此很难用一个生产环境的调度方案去解决另外一个生产环境的生产调度问题，并且生产环境的动态性、产品的多样性导致了生产调度的复杂性，需要将人、机、运筹学方法和信息技术结合起来解决车间调度问题。

车间调度问题一般可以描述为：设有n种工件{J1,J2,…,Jn}需要在m台机器{M1,M2,…,Mm}上加工，每种工件有一道或者多道工序Oij{O11,O12,…,O1i; O21,O22,…,O2j;…;On1,On2,…,Onq}，Oij表示第i种工件的第j道工序。每道工序可以在一台或者多台机器上加工，每台机器在某一时刻只能加工某种工件的某道工序，而且工件的某道工序在同一时刻只能在一台机器上加工，并且工件上道工序加工完成后才能转到下道工序加工。同一台机器上切换加工任务时产生作业切换时间，该时间的长短与紧前紧后加工任务的加工特征有关。

车间调度问题采用α、β、γ三参数法表示。α表示加工环境，β表示加工约束，γ表示优化目标。α、β、γ描述见表1.2。

车间调度问题描述如图1.2所示。

车间调度问题的研究经过多年的发展，从简单到复杂。学者研究的调度问题大多数都是对实际生产环境中复杂的、动态调度问题的一种抽象和简化。不同的生产环境下调度方法和优化目标有一定的差异。车间调度问题的分类方法较多，主要的分类方法包括下列几种。

（1）根据加工系统的复杂度进行划分，可以分为单机调度（Single Machine Scheduling，SMS）、多台并行机调度（Multiple Parallel Machine Scheduling，MPM）、作业车间调度（Job-shop Scheduling，JSS）和流水车间调度（Flow-shop Scheduling，FSS）。

单机调度问题是车间调度中最简单的形式，所有的加工任务都在单台机器上进行，要求每个加工任务都要在这台机器上加工一次，因此存在加工任务的优化排序问题。

多台并行机调度问题比单机调度问题要复杂，每个加工任务可以在任意一台机器上加工一次，优化任务包括两部分，首先是加工机器的选择问题，其次是加工机器上的任务排序问题，因此优化问题更为突出。

作业车间调度问题是较多实际生产调度问题的简化模型，是目前生产调度研究较多的一种典型调度问题，具有重要的理论意义和实际应用价值。允许同一加工任务可以在多台机器上加工，一个加工任务可以有多种加工路线，车间机床设备的布局比较灵活，工件的加工路径也比较灵活，各加工任务的工序和数量可以不同，这些都增加了调度的复杂性。

流水车间调度问题是指所有的加工任务都在同样的机器上加工，所有的加工任务的工序和加工顺序相同，即每个加工任务的加工路线相同，机床布局为流水线型。

（2）根据加工环境的特点，可以分为确定性调度问题和随机性调度问题。

（3）根据生产产出的产品是连续的产品流、离散的批量、离散的数量三种情况，分为连续生产过程、间隙生产过程和离散生产过程。离散生产过程加工任务通常是分批制造的，同一批产品为原材料相同、加工工序相同的一组产品，一定数量的工件作为一个工件组，在各工序需要加工机器间传输，机械加工是典型的离散生产过程。

（4）根据作业的加工特征分为静态调度（Static Scheduling）和动态调度（Dynamic Scheduling）。静态调度是指所有加工工件同时到达，处于等待加工的状态，通过一次调度，各加工任务的排序和机器分配被确定，并且后续加工中不再改变。动态调度是指加工任务依次达到，各种加工任务不断进入加工系统，加工完成后依次离开，需要考虑生产环境中不断出现的动态扰动因素，如频繁的作业切换和不确定的作业切换时间、临时插单、设备故障等。因此，动态调度需要不断地调整。

在1954年，Johnson研究了两台机床的流水车间调度问题后，人们开始研究车间调度问题。经过60多年的发展，车间调度问题的研究方法经历了从简单到复杂、从单一到多元的过程。车间调度问题的研究方法主要有以下几种。

（1）运筹学的方法。

车间调度问题可通过运筹学的方法转化为数学规划模型，采用分支定界法（Branch and Bound）、拉格朗日松弛法（Lagrangian Relaxation）和动态规划算法（Dynamic Program ming）等精确算法寻找调度最优解。分支定界法属于枚举方法，对于求解问题的所有可行解进行枚举，需要确定目标值的上下界，边搜索边减掉搜索树的某些支，对于那些不满足最优解条件的解可直接忽略，提高搜索效率。对于求解较大规模调度问题，运行时间较长，存在整数约束的限制。拉格朗日松弛法是解决复杂车间调度问题的一种重要方法，它克服了整数约束的限制，删除了整数约束并加入代价，主要思想是松弛原问题中较难的约束，将其吸收到目标函数中，再将原问题转化为比较简单的独立对偶问题，来获得原问题的最优解或次优解。动态规划算法以最优化原理和无后效性为基础，将复杂问题分解为简单的子问题，并进行求解，再根据各子问题间的关系，将子问题的解合并到原问题的解中。

（2）基于规则的调度方法。

传统的调度方法使用了调度规则（Dispatching Rules，DR），由于调度规则具有简单、易于实现、计算复杂度较低等优点，受到学者广泛研究。PanwaIkar和IskaDder将调度规则分为简单规则、复合规则和启发式规则。常用的调度规则主要包括以下几种。

① 先到先服务（First Come First Served，FCFS）准则。按工件到达车间的先后顺序安排加工。

② 最短加工时间（Shortest Process Time，SPT）优先准则。加工时间最短的工件优先安排，然后是次短的，以此排列，一直到加工时间最长的那个工件。

③ 最早工期（Earliest Due Date，EDD）优先准则。即按照工期从小到大进行排序，工期短的工件安排在前面加工，工期长的工件安排在后面加工。

④ 最长加工时间（Longest Processing Time，LPT）准则。优先选择加工时间最长的工件。

⑤ 转换瓶颈规则（Shifting Bottleneck Procedure，SBP）。该规则是求解Job-shop调度问题非常有效的启发式规则。它将机器逐一进行调度，每次调度时，都把当前机器假设为未调度机器中的瓶颈机器，每次调度完一台机器后，都要对已经调度好的机器进行局部优化。其中，瓶颈机器的识别及局部优化操作都是源于求解单机调度问题的方法，属于原生产调度问题的一个松弛问题。

⑥ Palmer规则是根据工件在各台机器上的加工时间，按照斜度顺序排列的启发式规则。按照各台机器的顺序，加工时间逐步增加的工件优先权数大，反之，加工时间逐步减少的工件优先权数小。

（3）智能优化算法。

车间调度的智能算法主要包括遗传算法、模拟退火算法、蚁群算法等。遗传算法具有很好的收敛性，以及快速随机搜索能力和潜在的并行性，并且具有可扩展性，容易与其他算法结合。然而遗传算法参数的选择直接影响解的质量，该算法对初始种群具有一定的依赖性，应该结合一些启发算法进行改进。模拟退火算法能够避免搜索陷入局部最优，寻找到全局最优解，但模拟退火算法对整个搜索空间的状况了解不多，不能快速进入最优解的搜索区域进行搜索，因此，模拟退火算法的运算效率不高。蚁群算法具有较强的寻优能力，不容易陷入局部最优，该算法利用了正反馈机制，可以加快进化过程。但蚁群算法也存在一些缺点，比如需要较长的搜索时间，容易出现停滞现象。

随着C2M生产模式的转变，越来越多的学者在研究车间调度问题时考虑了作业切换时间。在塑料工业中，不同类型和颜色的产品加工顺序依赖作业切换时间，而应用线性函数方法解决排序依赖作业切换时间的车间调度问题，或可以应用遗传算法解决排序依赖作业切换时间的车间调度问题，目标是最小化总完工时间。由此可知，遗传算法是基于自然遗传进化模型的并行优化搜索方法，完善了局部搜索算法。