1.3.2 车间调度问题的研究方法

从Johnson揭开调度问题研究的序幕以来，调度问题一直是极其困难的组合优化问题，调度模型从简单到复杂，研究方法随着调度模型的变迁从开始的数学方法到启发式的智能算法。解决调度问题的方法主要分为两类：精确方法（Exact Method）和近似方法（Approximation Method）。精确方法也可称为最优化方法，能够保证得到全局最优解，但只能解决较小规模的问题，且速度很慢。用近似方法求解时，可以很快地得到问题的解，但不能保证得到的解是最优的，不过对于大规模问题是非常合适的，可以较好地满足实际问题的需求。图1.1列举了近年来求解调度问题的主要研究方法，下面分别针对部分研究方法进行简要介绍。

1.精确方法

精确方法主要包括整数规划、混合整数规划、拉格朗日松弛法、分解方法及分支定界法等。

1）数学规划方法

数学规划方法中求解调度问题的最常见方法是混合整数规划。混合整数规划有一组线性约束和一个线性目标函数，限制决策变量必须是整数，导致在运算中出现的整数个数呈指数级增长，即便使用更好、更简洁的公式表述，也需要大量约束条件。

较多成功的数学模型方法归功于拉格朗日松弛法（Lagrangian Relaxation）和分解方法（Decomposition Method）。拉格朗日松弛法用非负拉格朗日乘子将工艺约束和资源约束进行松弛，然后将惩罚函数加入目标函数。上海交通大学的刘学英用拉格朗日松弛法解决了车间调度问题。利用分解方法可将原问题分解为多个小的易于解决的子问题，然后对子问题寻找最优。

2）分支定界法

分支定界法（Branch&Bound，B&B）是指用动态树结构来描述所有可行解排序的解空间，树的分支隐含要被搜索的可行解。Balas在1969年提出的基于析取图的枚举算法是最早应用于调度问题求解的分支定界法。分支定界法非常适合解决总工序数小于250的问题；在解决大规模问题时，由于其需要大量的计算时间，故限制了使用。目前，这种方法的研究重心是如何与智能算法相结合，以减少最初搜索阶段中的节点，提高搜索效率和求解效果。

2.近似方法

大多数调度问题的复杂性和精确枚举方法所存在的问题，使得近似方法成了一种可行的选择。近似方法可以在较为合理的时间内迅速求得可以接受的满意解。由于其求解速度快，解的质量还可接受，故可用于解决较大规模的调度问题。

1）构造方法

构造方法主要包括优先分派规则法、插入方法和基于瓶颈的启发式方法等。

（1）优先分派规则法

优先分派规则法（Priority Dispatch Rules，PDR）是最早的近似方法。该方法的具体操作是给所有被加工工序分派优先权，优先权最高的加工工序被最先选出排序，再按优先权次序依次进行排序。由于该方法非常容易实现且计算复杂度低，在实际调度问题中常常被使用。Panwalkar和Iskander对各种不同规则进行了归纳和总结。实际中常用的规则有SPT、LPT、EDD、MOR和FCFS等。大量该领域的研究表明：对于大规模的车间调度问题，多种优先分派规则组合起来使用更具优势；另外，该方法具有短视的缺点，如只考虑机器的当前状态和解的质量等级等。

（2）基于瓶颈的启发式方法

一般而言，基于瓶颈的启发式方法（Bottleneck Based Heuristic）主要包括瓶颈移动方法（Shifting Bottleneck Procedure，SBP）和射束搜索方法。SBP是目前求解调度问题最有效的构造方法之一，由Adams于1988年提出，也是第一个解决FT10标准测试实例的启发式算法。SBP是按照解的大小顺序对所有机器进行排序的，有着最大下界的机器被确定为瓶颈机器。实际求解时，把问题转化为多个单一机器问题，每次解决一个子问题，把每个子问题的解与所有其他子问题的解比较，每台机器依解的好坏排列，有着最大下限值的机器被认为是瓶颈机器。而单一机器问题的排序用Carlier方法通过迭代来解决，这个方法可以快速给出一个精确的解。每次瓶颈机器排序后，每台先前被排定的有改进能力的机器通过解决单一机器问题的方法，再次被重新局部最优化。虽然SBP可以得到比优先分派规则法质量更好的解，但是计算时间较长，并且实现起来比较复杂。

2）迭代方法

迭代方法主要包括人工智能方法和局部搜索算法。

（1）人工智能方法

20世纪80年代出现的人工智能方法在调度研究中占据重要地位，也为解决调度问题提供了一个较好的途径，主要包括约束满足、神经网络、专家系统、多智能体系统，以及后来人们通过模拟或揭示某些自然现象、过程和规律而发展的元启发式算法（如进化算法、免疫算法、蚁群优化算法和粒子群优化算法等）。

①约束满足

约束满足（Constraint Satisfaction，CS）是指通过运用约束减小搜索空间的有效规模。这些约束限制了选择变量的次序和分配到每个变量可能值的排序。一个值被分配给一个变量后，不一致的情况被剔除。去掉不一致的过程称为一致性检查（Consistency Checking），但是这需要进行回访修正，当所有变量都得到分配的值且不与约束条件冲突时，约束满足问题就得到解决。Pesch和Tetzlaff指出，该方法只是在一定程度上给调度者高水平的指导方针，较少应用于实际调度。

②神经网络

神经网络（Neural Networks，NN）通过一个Lyaplmov能量函数构造网络的极值，当网络迭代收敛时，能量函数达到极小值，使与能量函数对应的目标函数得到优化。用NN解决旅行商问题（TSP）是其在组合优化问题中最成功的应用之一。Foo和Takefuji最早提出用Hopfield模型求解车间调度问题，之后大量学者进行了改进性研究。除Hopfield模型之外，BP（Back Propagation）模型也较多地应用于求解车间调度问题。Remus最早利用BP模型求解调度问题，之后大量学者对此模型进行研究。目前，神经网络仅能解决规模较小的调度问题，并且计算效率非常低，以至于不能较好地用于求解实际大的规模调度问题。

③专家系统

专家系统（Expert System，ES）是一种能够在特定领域内模拟人类专家思维解决复杂问题的计算机程序。专家系统通常由人机交互界面、知识库、推理机、解释器、综合数据库和知识获取六个部分构成。它将传统的调度方法与基于知识的调度评价相结合，根据给定的优化目标和系统的当前状态，对知识库进行有效的启发式搜索和并行模糊推理，避开烦琐的计算，选择最优的调度方案，为在线决策提供支持。比较著名的专家系统有ISIS、OPIS、CORTES、SOJA等。由于专家系统需要丰富的调度经验和大量的知识积累，使得开发周期较长，并且成本昂贵，对新环境的适应能力较差，故一般对领域的要求非常严格，且非常特定。

④多智能体系统

为了解决复杂问题，克服由于单一专家系统所造成的知识有限、处理能力弱等缺点，出现了分布式人工智能（Distributed Artificial Intelligence，DAI）。多个智能体的协作正好符合分布式人工智能的要求，因此出现了多智能体系统（Multi-Agent System，MAS）。由于MAS对开放和动态的实际生产环境具有良好的灵活性和适应性，所以其在实际生产中不确定因素较多的车间调度等领域得到越来越多的应用。不过，MAS和专家系统具有同样的不足，即需要丰富的调度经验和大量的知识积累等。

⑤进化算法

进化算法（Evolutionary Algorithm，EA）通常包括遗传算法（Genetic Algorithm，GA）、遗传规划（Genetic Programming，GP）、进化策略（Evolutionary Strategies，ES）和进化规划（Evolutionary Programming，EP）。这些都是模仿生物遗传和自然选择机理，用人工方式构造的一类优化搜索算法，但侧重点不一样，GA主要发展自适应系统，是应用最广的算法；ES主要解决参数优化问题；EP主要求解预期问题。1985年，Davis最早将GA应用于调度问题，通过一个简单的20×6车间调度问题验证了采用GA的可行性。此后，Falkenauer和Bouffouix对其进行了改进提高。1991年，Nakano首先将GA应用于一系列JSP典型问题中。Yamada和Nakano在1992年提出一种基于Giffler和Thompson的算法GA/GT。自1975年Holland教授提出GA以来，国内关于其在求解车间调度问题的文献非常多，其中，清华大学的王凌和郑大钟较好地对GA及其在调度问题中的应用进行了分析和总结。

⑥蚁群优化算法

蚁群优化（Ant Colony Optimization，ACO）算法是意大利学者Dorigo等人于1991年提出的，这种算法的核心思想是模拟蚂蚁在寻找食物过程中发现路径的行为。蚂蚁在寻找食物过程中，会在它们经过的地方留下一些化学物质—外激素（Stigmergy）[或信息素（Pheromone）]，这些物质能被同一蚁群中后来的蚂蚁感受到，并作为一种信号影响后来者的行动，而后来者也会留下外激素对原有外激素进行修正，如此反复循环下去，使外激素最强的地方形成一条路径。蚁群算法在求解复杂组合优化方面有一定优越性，不过容易出现停滞现象，收敛速度慢。

⑦粒子群优化算法

粒子群优化（Particle Swarm Optimization，PSO）算法由Eberhart博士和Kennedy博士于1995年提出，源于对鸟群捕食行为的模拟研究。在PSO算法中，系统初始化为一组随机解，称为粒子。每个粒子都有一个适应度值表示粒子的位置，另外还有一个速度决定粒子飞翔的方向和距离。在每一次迭代中，粒子都通过两个极值来更新自己，一个极值是粒子自身所找到的最优解，称为个体极值；另一个极值是整个种群目前找到的最优解，称为全局极值。国内关于PSO算法在车间调度中的应用的研究较多，特别是华中科技大学的高亮等人，在PSO算法应用方面做了大量工作。PSO算法最初应用于连续问题优化，如何较好地离散化应用于组合优化问题是一个研究热点。

（2）局部搜索算法

局部搜索（Local Search，LS）算法是人们从生物演化、物理过程中受到启发用于组合优化问题的，从早期的启发式算法变化而来。以模拟退火、禁忌搜索为代表，应用广泛。局部搜索算法必须依据问题设计优良的邻域结构产生较好的邻域解来提高算法的搜索效率和能力。

①模拟退火

模拟退火（Simulated Annealing，SA）是Kirkpatrick等人在1983年提出的，源于模拟物理退火的过程，且结合Metropolis准则。在利用模拟退火算法在进行局部搜索过程中，即使某个解的目标函数值变坏，也仍可以采用Metropolis准则以一定的概率接受新的较差解或继续在当前邻域内搜索，以避免陷入局部最优解，整个过程由一个称为温度的参数t来控制。Laarhoven和Matsuo在1988年首先将SA算法用于求解车间调度问题。此后Laarhoven对SA算法进行改进，取得了较好的求解结果。由于SA算法是一般随机搜索算法，搜索过程也没有记忆功能，故在求解调度问题时不能非常迅速地得到较好解。不过，SA算法与其他算法相结合可以增强局部搜索能力，同时在结果和计算时间上有明显改善。

②禁忌搜索

禁忌搜索（Tabu Search，TS）由Golver和Hansen于1986年提出。TS在运行时，按照某种方式产生一个初始解，然后搜索其邻域内的所有可行解，取其最优解作为当前解。为了避免重复搜索，引入灵活的存储结构和相应的禁忌准则（禁忌表和禁忌对象）；为了避免陷入局部最优，引入特赦准则，允许在一定程度上接受较差解。1996年，Nowicki和Smutnicki设计了一种基于关键路径的邻域结构，对TS求解调度问题影响非常大。TS算法的求解速度较快，且应用较为广泛，但它依赖问题模型和邻域结构等，可以与其他算法相结合，以提高局部搜索能力。

除上述方法之外，还有很多种方法对调度问题进行求解，如Petri网和仿真调度法、文化算法（Cultural Algorithm）、DNA算法、Memetic算法、分散搜索（Scatter Search）等。每种算法都有一定优势，也存在一定缺点，如何将它们取长补短地混合在一起使用是当前及未来研究的热点。