车间调度问题的特性决定了该问题是个十分复杂的问题，也正因为如此，多年来，对这一问题的研究吸引了来自不同领域的大量研究人员，他们提出了若干求解方法，希望能满足实际应用的需求。以下对这些方法进行简单介绍［21］。

1.运筹学方法

运筹学方法结合数学和运筹学的理论来求解调度问题。虽然该类方法大多能从理论上求得最优解，但是它仅适合简单的调度问题；当面对复杂的环境时，存在计算复杂、运算耗时等困难，从而难以在实际环境中得到广泛应用。同时，这一类方法需要对研究对象的特点进行全面的分析，对问题的依赖性很强，不利于推广。针对调度问题，主要的运筹学方法有分支定界法和数学规划方法两大类。

1）分支定界法

分支定界法是求解组合优化问题的一种通用方法，最早由Land和Diog［22］于1960年提出。大量基于分支定界法的改进方法被应用于求解各类生产调度问题，如单机调度、并行机调度、流水车间调度、作业车间调度等问题。分支定界法的主要思想是对所求问题的所有可行解进行枚举操作。在求解过程中，首先确定目标值的上界，然后以此为标准对搜索树的一些超出该上界的分支进行舍弃操作，并通过这样的循环操作缩小搜索空间。可见，分支定界法对问题的上界依赖性很强，因此对于大规模的问题难以在合理的时间里获得最优解或者较优解。针对该缺点，需要进一步研究分支定界的规则，设计出更为强大的、效率更高的排除规则。

2）数学规划方法

用等式和不等式表达调度问题的目标函数和约束等，再通过各种数学规划方法求解调度问题的方法称为数学规划方法。目前，已有多种数学规划方法被应用到调度问题中，如整数规划、混合整数规划、拉格朗日松弛法、动态规划等。其中，拉格朗日松弛（Lagrangian relaxation，LR）法是求解组合优化问题的非常经典的方法。它的主要思想是松弛原问题中较难的约束，将它吸收到目标函数中，使原问题转化为一些比较简单的独立对偶问题，再通过求解这些对偶问题来获得原问题的最优解或近似最优解。自20世纪70年代起，拉格朗日松弛法被成功用于求解生产调度这类典型的组合优化问题。

动态规划最早是由Bellman在20世纪50年代提出的［23］，它以最优化原理和无后效性为基础，将复杂问题分解为一系列较为简单的子问题，对每一个子问题进行分析求解，获得子问题的最优解，最后再利用各个子问题间的关系，将这些子问题的最优解合并得到原问题的最优解。动态规划在生产调度问题中也有着很多成功的应用。

数学规划方法或者分支定界法等精确的方法只适合求解规模较小、环境简单的调度问题，当面对复杂多变的实际调度环境时往往难以应对。

2.启发式规则

启发式规则是一类局部优化方法，通过一些规则快速建立调度问题的解；但是难以保证求得的解的可行性和最优性，也无法对解的性能进行定量的评估。目前，基于启发式规则的方法主要有三大类：基于优先分派规则（priority dispatch rules，PDR）、基于插入方法（insertion methods，IM）和基于转移瓶颈规则（shifting bottleneck procedure，SBP）。下面对前两类方法做简要的介绍。

1）基于优先分派规则

基于优先分派规则是指在工件加工时，根据设定的一些优先次序安排工件的加工顺序。该方法是最早的一类近似方法，具有易于实现、计算复杂度低等特点，可以广泛地应用到各种调度问题中。Panwalker和Skander对113种不同的规则进行了总结和分析，其中常用的规则如下。

（1）先到先服务（first come first served，FCFS）规则，指的是按照工件到达的先后顺序依次进行加工，先到的先加工。

（2）最短加工时间（shortest processing time，SPT）优先规则，指的是按照工件在所有机器上的总加工时间从短到长排序，排在前面的先加工，排在后面的后加工。

（3）最早工期（earliest due date，EDD）优先规则，指的是按照工期从短到长的顺序进行排序，并以此顺序来安排工件先后加工顺序。

（4）最长加工时间（longest processing time，LPT）优先规则，指的是按照工件在所有机器上的总加工时间从长到短排序，排在前面的先加工，排在后面的后加工。

（5）剩余总加工时间最长（most work rerunning，MWR）优先规则，指的是根据当前工件剩余的加工时间从长到短排序，排在前面的先加工，排在后面的后加工。

（6）剩余工序数最多（most operations remaining，MOR）优先规则，指的是根据当前工件剩余的工序数从多到少排序，依次安排工件加工。

一些研究表明单一的规则效果有限，通过综合多个规则共同指导工件加工顺序的方法具有更好的效果。但是这些规则设定只考虑机器或者工件当前的状态，导致解的整体性能受到一些影响。

2）基于插入方法(www.daowen.com)

与前文的基于优先分派规则相比，基于插入方法的实施过程较为复杂：在整个调度过程中需要不断地根据当前机器和工件的状态进行排序，选择最优的作为当前的子调度，直到安排所有的工件完成加工任务为止。目前主要的规则如下。

（1）NEH（Nawaz-Enscore-Ham）规则是一种求解流水车间调度问题非常有效的启发式规则。它首先计算各工件在所有机器上的加工时间和，并按照递减顺序排列；然后将最前面两个工件进行调度排列，选出较好的排列；接着将剩余的工件依次插入已经排好的工件调度序列中的所有可能位置，进行调度排序，生成新的调度排列，直到所有工件都已参与排序，生成完整的调度解。

（2）Johnson规则用来最小化包含两台机器的流水车间调度问题的最大完工时间，效果很好，它为后来用启发式规则求解包含多台机器的流水车间调度问题奠定了良好的基础，几乎所有的启发式规则都会用到它的思想。其主要步骤为：首先将工件分为A和B两组，其中A组里的工件在第二台机器上的加工时间比在第一台机器上的加工时间长，B组里的工件与之相反；然后将A组里的工件按它们在第一台机器上的加工时间从小到大排列，将B组里的工件按它们在第二台机器上的加工时间从大到小排列；最后将A组和B组工件连在一起，组成完整的工件加工序列，依次加工。

（3）CDS（Campbell-Dudek-Simth）规则是Johnson规则的一种扩展形式，用于求解包含多台机器的流水车间调度问题。具体步骤为：首先将m台机器系统地分为两组，产生m-1个两台虚拟设备问题的合；然后利用Johnson规则获得m-1个调度序列，选出其中最好的一个加工序列作为最优调度解；同理考虑包含3台机器、4台机器直到m台机器的组，获得最终的完整调度解。

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

由于作用于整个调度过程，在大多数情况下，基于插入方法求解调度问题的效果要好于基于优先分派规则，但是同样地，面对大规模问题时，它还是难以得到性能较优的解。

3.智能优化算法

在过去的几十年里，传统的运筹学方法和启发式规则得到了很大的发展，但是实际的生产调度问题十分复杂，规模也很庞大，这些传统的调度方法无法用来求解实际生产调度问题。理论调度与实际调度之间存在很大的差距，这个问题一直困扰着广大研究者。自20世纪80年代起，人工智能的思想开始被引入生产调度问题中，孕育出了大量有效的智能优化算法。前文介绍的启发式规则属于构造型算法，即从什么都没有开始，逐步增加一个工件，最后获得完整的调度解，而智能优化算法属于改进型算法，它从一个完整的调度解开始，不断改进，以获得更优的调度解。与传统的运筹学方法相比，智能优化算法不需要对具体问题进行深入分析，对问题的依赖性较弱，仅仅通过计算机的迭代运算就可以完成整个搜索优化过程，但是智能优化算法最终求得的解不一定是全局最优解，它只能保证在较短的时间内获得一个较为满意的解。目前已有的智能优化算法很多，成功应用于生产调度问题的也不少，下面介绍几种最为常见的智能优化算法。

1）遗传算法

遗传算法（genetic algorithm，GA）是建立在达尔文进化论以及孟德尔遗传学说基础上的，模拟了自然生物界遗传机制和进化理论的优化方法。它最早由美国密歇根大学的教授Holland于1975年提出［8］。GA在整个搜索迭代过程中自动获取并积累相关的知识，自适应地控制搜索过程，逐步进化得到最优解。GA遵循了优胜劣汰、适者生存的原则，在进化中，算法根据种群中每一个个体的适应度值对个体进行选择、交叉和变异操作，产生新的个体，不断进化，使得新产生的个体比原来的个体具有更高的适应度值，更加优秀。GA是最为常见、最为人熟知的智能优化算法之一，原理简单，具有隐含的并行性和全局搜索能力，对问题的依赖性较弱，通用性强，适合求解各类问题。它自从被提出后，已广泛应用到计算科学、数学、物理学、化学、工程学、经济学等诸多学科领域中，取得了很大的成功。

2）模拟退火算法

模拟退火（simulated annealing，SA）算法模拟了物质退火的物理过程，最早由Metropolis等于1953年提出［7］。退火指的是将物质加热后再按照一定的速度进行冷却，物质中的原子初始温度较高，内能较大，在退火过程中内能不断减少，逐步到达稳定状态，找到比原位置具有的内能更小、更加稳定的新位置。SA算法具有一定的并行性，它也是从某一个较高的温度开始降温，伴随温度的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，具有很强的全局搜索能力。SA算法效果的好坏与初始状态的好坏无关，无论初始状态如何，SA算法都可以渐近收敛到最优解，并且已经在理论上被证明是一种以概率1收敛到全局最优解的全局优化算法。

3）禁忌搜索算法

禁忌搜索（tabu search，TS）算法又称tabu搜索算法，最早由美国科罗拉多大学教授Glover于1986年提出［13］。TS算法是局部搜索算法的一种推广，它通过模拟人类记忆的原理，对一些局部最优解进行禁忌操作，期望跳出局部最优解。在TS算法中，首先确定一个初始解，并在初始解的邻域进行搜索，选取其中的最优解作为当前解，将本次搜索的数据存储到禁忌表中，以免重复搜索；再对当前解进行邻域搜索，如果搜索得到的最优解比已记录的最优解更好，则进行替代，并相应地修改禁忌表，否则将当前搜索得到的未被禁忌的最优解作为新的当前解，无论它是否好于已经禁忌的当前解，同时也相应地修改禁忌表；上述过程不断迭代循环，直到满足终止条件为止。TS算法利用禁忌表来记录搜索过的历史结果，在一定程度上使该搜索过程能够避开局部极值点，并且避免对已经搜索过的区域进行重复搜索，有利于开辟新的搜索区域。

4）蚁群优化算法

蚁群优化（ant colony optimization，ACO）算法最早由Dorigo等人在20世纪90年代提出［24］。此算法模拟了蚂蚁在寻找食物过程中发现路径的行为。ACO算法是一种基于种群寻优的智能优化算法，它充分利用了生物蚁群能通过个体间简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征。ACO算法具有两个最显著的特点，即多样性和正反馈，其中多样性保证了算法在运行过程中具有不断找到新解的能力，而正反馈机制则保证了种群中优良的信息能够被保留下来。多样性可以看作一种创造能力，正反馈则可以看作一种学习强化能力，两者的结合能够有效增强算法的搜索能力，提高算法的求解效果。此算法最早用来求解旅行商问题（travelling salesman problem，TSP），随后逐步应用到各个领域，如背包问题、生产调度问题、分配问题、车辆路径问题等。

5）粒子群优化算法

粒子群优化（particle swarm optimization，PSO）算法又称微粒群算法，最早由Kennedy和Eberhart两位学者在1995年提出［10］。PSO算法是通过模拟鸟群觅食行为而发展起来的一种群智能优化算法，它首先随机初始化种群，然后利用个体所寻找到的最优解及全局最优解的信息不断迭代更新寻求最优解。与GA相比，PSO算法种群中的粒子具有记忆功能，进化规则更为简单，不需要进行类似于GA中的交叉和变异操作，只需要根据所有粒子的最优位置和当前粒子的历史最优位置，以一定的机制逐步向它们靠拢即可。PSO算法容易实现，精度高，收敛速度快，自提出以来便很快在各个领域得到了很好的应用。

6）帝国主义竞争算法

帝国主义竞争算法（imperialist competitive algorithm，ICA）是基于帝国主义殖民竞争机制的一种新的优化算法。2007年，Atashpaz-Gargari和Lucas受帝国主义国家与其殖民地国家的竞争历史的启发，在基于人口数量最优化算法的著作中提出了帝国主义竞争算法［25］。该优化算法是一种属于社会启发的智能计算方法，根据帝国主义国家的社会政策来控制更多的国家，在殖民地国家受一些规律支配时使用它们的资源，如果一个帝国主义国家失去强大的势力，其他国家将占有它。在ICA中，由被称为国家的个体来模拟这个过程，帝国主义竞争算法的基本思想是：同其他进化算法相似，在ICA开始部分，将一组个体定义为各个国家，所有的国家被分为帝国主义国家和殖民地国家；将最初比较强大的国家作为帝国主义国家，其他国家作为殖民地国家；根据每个国家的势力将殖民地分配给不同的帝国主义国家；帝国主义国家与其所包含的殖民地国家被称为同一个帝国主义国家；帝国主义国家之间通过竞争以获得更多的殖民地国家，势力更大的帝国主义国家有较大的可能性占有最弱的殖民地国家，势力薄弱的帝国主义国家将逐渐失去其殖民地国家；当所有殖民地国家全部被一个帝国主义国家占有时，该算法结束。帝国主义竞争算法具有简单、准确、省时等优点，是一种十分有效率且易于使用的优化算法，节省内存，寻优时间短，并且能够快速地在搜索空间里收敛到最优解。