动态调度

出自 MBA智库百科(https://wiki.mbalib.com/)

　　动态调度指在决策时刻，调度环境的部分信息可知，根据逐步获得的信息，不断更新调度。

　　动态调度通常是指在调度环境和任务存在不可预测扰动情况下所进行的调度。与静态调度相比，动态调度能够针对生产现场的实际情况产生更具可操作性的决策方案。动态调度的实现方式有两种:一是事先不存在静态调度方案，直接按照生产系统中工件和设备的状况以及相关信息，使用某种计算方法，确定工件的加工优先级，即实时调度;二是在已有静态调度方案的基础上，根据生产系统的现场状态，及时进行静态调度方案的调整，确定工件的加工优先级，此种方式常常被称作“重调度”(又称在线优化)。

　　以上两种方式皆可获得可操作的调度决策方案，但又有所不同。实时调度在决策中往往只考虑局部信息，因此得到的调度结果可能与优化的调度方案有较大的偏差，虽然可行，但与优化方案还有较大距离;重调度则是在已有静态调度方案的基础上，根据实际生产状况，进行静态方案的动态调整，保证其可操作性。由于静态调度方案往往是通过优化方法考虑多个性能指标获得的，因此重调度(即在线优化)能够获得更加优化的动态调度结果。

　　目前，关于动态调度研究方法的综述性文献仅对动态调度的某类研究方法进行综述。例如:Ra-mash对动态调度仿真研究方法的综述，Szelde等对基于知识的反应调度方法的综述;Suresh等对单件车间动态调度的综述。这些文献不但没有对动态调度的各类研究方法进行全面的综述，而且对每种方法的适用条件也缺乏必要的分析。近年来，动态调度的理论和应用研究都取得了很大进展，因此有必要对动态调度的研究方法进行系统的分类和评价。本文将研究动态调度的方法分成两大类，即传统方法和智能方法。传统方法包括最优化方法、仿真方法和启发式方法;智能方法包括专家系统、人工神经网络、智能搜索算法和Multiagent方法。

　　1、传统的研究方法

　　（1）最优化方法

　　最优化方法主要包括数学规划(动态规划、混合整数线性规划等)、分支定界法和消去法等。这类方法通常基于某些简化的假设，并能产生一个最优调度方案。现已证明，绝大多数调度问题是NP问题，随着调度问题规模的增大，上述方法的求解难度将急剧增加，因而最优化方法往往不能适应生产实际对实时性的要求。此外，该类方法大多基于某些理想化的假设，远不能充分反映实际生产环境的复杂性，而且要充分表达实际生产环境的随机性和动态性也极为困难，所以单独使用此类方法来解决动态调度问题是不现实的。目前在动态调度的研究中，通常将最优化方法同其它方法相结合，用来解决一定的问题。例如Matsuura提出的重调度算法，首先用分支定界法产生一个调度，当工况发生变化时，再用调度规则来分配工件。

　　（2）启发式方法

　　启发式方法针对调度问题的NP特性，并不企图在多项式时间内求得问题的最优解，而是在计算时间和调度效果之间进行折中，以较小的计算量来得到近优或满意解。启发式方法通常称为调度规则。关于调度规则的研究在很早以前便开始了，例如Johnson于1954年提出的Johnson算法等。Panwalker等对113个调度规则做了经典的分类，将调度规则分成3大类，即优先级规则(包括简单的优先级规则、简单优先级规则的组合和加权优先级规则)、启发式调度规则及其它规则，并对各规则的适应情况做了总结。关于调度规则比较经典的综述性文献还有文献。

　　由于调度规则计算量小、效率高、实时性好，因而在动态调度研究中被广泛采用。但由于它通常仅对一个目标提供可行解，并且缺乏对整体性能的有效把握和预见能力，因而在实际应用中常将它与其它方法结合使用，利用其它方法根据具体情况选择合适的调度规则。此外，新的启发式方法也不断提出。例如Abumizar等提出一种重调度算法，当扰动发生时，不是全部重新调度也不是等扰动解除后再继续原调度，而是仅仅重新调度那些直接或间接受扰动影响的工件，从而减少了由于扰动引起的生产周期的增加，同时也减少了与初始调度的偏差，效率和稳定性都较好。

　　（3）仿真方法

　　仿真方法是动态调度研究中最常用的方法。该方法通过对实际生产环境的建模来模拟实际生产环境，从而避开了对调度问题进行理论分析的困难。目前，仿真方法在动态调度研究中主要有以下两方面内容:

　　1)研究各种仿真参数对仿真结果的影响，以便在进行仿真实验时能做出恰当选择，从而使仿真所取得的结论更全面、更具说服力。Ramash总结了大量的相关文献，对仿真时应考虑的参数及各参数的取值范围做了详细介绍。

　　2)将某些方法应用于某个仿真环境，通过仿真评价现有方法之间或新方法与现有方法之间的优劣，从而总结出各方法的适用范围，或根据结论数据建立知识库或产生神经网络的训练样本。Liu等做了大量仿真实验，从仿真数据中产生出训练样本用于训练神经网络，并将训练后的神经网络用于动态调度。

　　由于仿真方法在模拟实际环境时做了某些假设和近似，而且仿真模型的建立较多地依赖于诸如随机分布等参数的选择，因而仿真结论往往因模型的不同而不同，很难取得一个一致的结论。然而，对多数生产调度问题而言，在缺乏有效的理论分析的情况下，仿真仍不失为一种最受欢迎的方法。

　　2、智能的调度方法

　　（1）专家系统

　　专家系统在动态调度研究中占有重要地位，目前已有一些较成熟的调度专家系统，例如ISIS和OPIS等。调度专家系统通常将领域知识和现场的各种约束表示成知识库，然后按照现场实际情况从知识库中产生调度方案，并能对意外情况采取相应的对策。

　　有效的领域模型和知识表示对于动态调度专家系统的设计十分重要。此外，约束在调度知识库中也占据重要地位，因为调度的好坏在很大程度上依赖于其对约束的满足程度。动态调度的决策参数具有很强的不确定性，为了有效地表示这种不确定性，许多学者选择了概率论，而应用模糊集理论则是一种更为有效的方法。在调度问题中应用模糊方法的优点在于，可为不精确约束的表示和应用提供丰富的表述语言和系统的框架，并且能对模糊目标进行评价。

　　ISIS是最早的基于AI的调度系统之一。该系统采用约束指导的搜索方法产生一个调度，动态情况则由重调度组件进行处理，当冲突发生时，它通过有选择地放松某些约束来重新调度那些受影响的定单。基于ISIS开发的OPIS是现有的基于知识的车间调度系统中最成熟的系统之一，它根据情况使用面向资源或面向定单的动态调度策略。SONI-A是一个包含预测和反应调度组件的单件车间调度系统，反应组件用于解决由于各种原因产生的调度效果与预期效果间的偏差，系统考虑的意外事件有操作延误、容量冲突和机器故障。OPAL也是一个为单件车间设计的调度系统，它采用调度规则和启发式方法进行调度。尽管OPAL中没有反应调度组件，但是当调度延误时，它可以根据车间的当前状态重新产生一个调度。

　　（2）神经网络方法

　　神经网络应用于调度问题已有十多年的历史，它在动态调度研究中的应用主要集中在以下两方面:1)将调度问题看成一类组合优化问题，利用其并行处理能力来降低计算的复杂性;2)利用其学习和适应能力将它用于调度知识的获取，以构造调度决策模型。目前，利用神经网络解决动态调度问题已成为动态调度研究的一个热点。在动态调度研究中应用最多的是BP网，通过对它的训练来构造调度决策模型。

　　Sim等提出一种专家神经网络方法，该方法用16个神经网络分别从相应的训练样本集中获取调度知识，用专家系统确定各子网的输入。由于神经网络的训练由16个子网分担，并且各子网可以并行训练，从而减少了训练时间。Cho等提出一种基于神经网络和仿真的鲁棒自适应调度器，该方法根据他人研究的结论确定神经网络的结构和训练样本。尽管该网络结构具有较强的通用性，但由于每个人研究的背景不尽相同，因此通过量化他人结论来产生训练样本必然会对网络性能造成影响。Jones等提出一种解决实时排序和调度问题混合方法的框架，综合运用了神经网络、遗传算法和实时仿真等方法。但只是提供了一个框架，真正实施起来还需进一步研究。Liu等提出一种用神经网络选择调度规则的方法，神经网络的输入对应于所有待调度工件的加工路线和加工时间信息，输出对应于待选的调度规则。但该方法需要大量的训练样本和很长的训练时间才能保证调度的效果;另外，随着问题规模的增大，网络的规模也将急剧增大。

　　（3）智能搜索算法

　　应用于调度问题的智能搜索方法包括模拟退火、禁忌搜索和遗传算法等。目前在动态调度中使用最多的是遗传算法。遗传算法解决调度问题的优势在于它可以随机地从一个调度跳到另一个调度，从而可以解决其它方法易于使解陷入局部最优的问题。此外，它还具有计算速度快且易与其它算法相结合的优点，非常适合于解决动态调度问题。应用遗传算法解决动态调度的文献较多，其中大多将遗传算法与其它方法结合使用。Lee等用遗传算法和机器学习来解决单件车间的调度问题，用机器学习来产生将工件下发到车间层的知识库，而用遗传算法在各台机器上分配工件。Jian等提出一种FMS的调度和重调度算法，该算法考虑了4种动态事件，即机器损坏、定单优先级提高、紧急定单下达和定单取消，用稳态遗传算法产生一个初始调度，当意外事件发生时，根据具体情况仅重新调度那些直接受影响的工序。Jones等提出一种实时排序和调度算法，它集成了神经网络、实时仿真和遗传算法等方法，其中遗传算法主要用于对几个备选的调度规则进行优选。

　　（4）Multi-agent方法

　　Multiagent通过在一系列分散的智能单元(Agent)间进行协调来解决问题。这些单元有各自的目标和自治的行为，并且可以有子单元。但是没有一个单元能够解决全局问题，因而它们之间必须进行协调。

　　关于Multiagent系统的结构，不同的人有不同的观点。例如Kouiss等根据车间的物理布局来确定系统的结构，为每一个加工中心配备了一个Agent，用于解决对应加工中心内的调度。另外还设计了一个全局Agent，用于监视整个制造系统的状态，必要时为满足全局的需要可在各Agent间进行协调。Nof等提出了自适应/预测调度系统框架，将调度系统按功能划分成5个模块:调度器/重调度器、监视器、比较器、分辨器和调度恢复适应器。关于每个Agent的结构，不同的人有不同的理解。但是每个Agent至少应有以下3个组成部分:1)知识库，包含Agent执行其功能所必需的知识和数据;2)控制功能，根据环境状态及与其它Agent间的相互作用，从知识库中提取知识来完成调度功能;3)通讯功能，用来与其它Agent和环境之间进行信息传递。

　　研究表明，Multiagent特别适用于解决复杂问题，尤其是那些经典方法无法解决的单元间有大量交互作用的问题。其优点是速度快、可靠性高、可扩展性强、能处理带有空间分布的问题、对不确定性数据和知识有较好的容错性;此外，由于是高度模块化系统，因而能澄清概念和简化设计。