动态调度

调度环境和任务存在不可预测扰动情况下所进行的调度

动态调度通常是指在调度环境和任务存在不可预测扰动情况下所进行的调度。与静态调度相比，动态调度能够针对生产现场的实际情况产生更具可操作性的决策方案。

方案简介

传统的对生产调度的研究是在如下假设条件下进行的： 1) 被调度的工件集合是确定的； 2) 工件的加工时间是确定的，并且在安排计划时全部工件都已到达； 3) 加工工件的机器是连续可用的。这类调度问题是静态调度问题。

实际生产中的大量问题是随机发生的。如在机械制造业中，由于工件随机到达，加工机器出现故障等随机事件，使得预调度不能正常执行，这就需要安排重调度。同样，在钢铁企业的炼钢-连铸-热轧一体化生产工艺中，由于要求工序之间的物流衔接和节奏匹配协调一致，且高温连续运作，故其生产调度系统具有以下特点： 1) 能够在线产生实时调度； 2) 对随机扰动实现在线辨识，并能快速进行自动重调度。这类问题是动态环境下生产调度问题。

动态调度的概念出现较早， Jackson于1957年便对静态调度和动态调度的概念做了区分。最初的研究主要采用启发式方法或仿真方法，与实际应用有较大的距离。近年来，计算机技术的迅速发展以及人工智能、神经网络、遗传算法和仿真技术等新方法的产生和发展，为动态调度的研究开辟了新思路，也为生产调度的实用化奠定了基础。目前，动态调度已成为生产调度研究中的热点之一。

研究方法

传统的研究方法

1、最优化方法

最优化方法主要包括数学规划( 动态规划、混合整数线性规划等) 、分支定界法和消去法等。这类方法通常基于某些简化的假设，并能产生一个最优调度方案。

现已证明，绝大多数调度问题是NP 问题，随着调度问题规模的增大，上述方法的求解难度将急剧增加，因而最优化方法往往不能适应生产实际对实时性的要求。此外，该类方法大多基于某些理想化的假设，远不能充分反映实际生产环境的复杂性，而且要充分表达实际生产环境的随机性和动态性也极为困难，所以单独使用此类方法来解决动态调度问题是不现实的。目前在动态调度的研究中，通常将最优化方法同其它方法相结合，用来解决一定的问题。

2、启发式方法

启发式方法针对调度问题的NP 特性，并不企图在多项式时间内求得问题的最优解，而是在计算时间和调度效果之间进行折中，以较小的计算量来得到近优或满意解。启发式方法通常称为调度规则。

由于调度规则计算量小、效率高、实时性好，因而在动态调度研究中被广泛采用。但由于它通常仅对一个目标提供可行解，并且缺乏对整体性能的有效把握和预见能力，因而在实际应用中常将它与其它方法结合使用，利用其它方法根据具体情况选择合适的调度规则。此外，新的启发式方法也不断提出。

3、仿真方法

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

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

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

智能的调度方法

1、专家系统

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

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

2、神经网络方法

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

3、智能搜索算法

应用于调度问题的智能搜索方法包括模拟退火、禁忌搜索和遗传算法等。目前在动态调度中使用最多的是遗传算法。遗传算法解决调度问题的优势在于它可以随机地从一个调度跳到另一个调度，从而可以解决其它方法易于使解陷入局部最优的问题。此外，它还具有计算速度快且易与其它算法相结合的优点，非常适合于解决动态调度问题。

4　Multi-agent 方法

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

关于Multi-agent 系统的结构，不同的人有不同的观点。例如Kouiss 等根据车间的物理布局来确定系统的结构，为每一个加工中心配备了一个Agent，用于解决对应加工中心内的调度。另外还设计了一个全局Agent，用于监视整个制造系统的状态，必要时为满足全局的需要可在各Agent 间进行协调。Nof 等提出了自适应/ 预测调度系统框架，将调度系统按功能划分成5 个模块: 调度器/ 重调度器、监视器、比较器、分辨器和调度恢复适应器。

发展趋势

传统方法中应用最多的是调度规则( 启发式算法) 和仿真方法。仿真方法几乎在每种方法中都有应用。由于调度规则具有计算量小、效率高和实时性好等优点，非常适用于动态调度。但它也有明显的缺点，因而通常需要与智能方法结合使用，通过智能方法根据情况在备选规则间进行选择。典型的研究方法通常同时使用某种智能方法、仿真方法和调度规则。

智能调度方法如专家系统、神经网络和遗传算法等，既有许多优点，也有各自的缺点。例如: 神经网络的训练时间较长，对结果缺乏解释能力，并且网络结构及算法参数不易确定; 专家系统知识获取的难度大且扩展性较差，当问题偏离知识领域时系统的性能将急剧下降; 遗传算法的适应函数较难选取，处理实际问题时有时不能满足实时性和调度效果的要求。因此上述方法经常结合在一起使用，如专家系统与神经网络相结合，遗传算法与神经网络相结合，遗传算法与专家系统相结合等。由于Multi-agent 方法具有速度快、可靠性高、可扩展性强等优点，将成为研究的热点之一。

动态调度不仅是钢铁集成调度的关键技术，也是机械、化工等流程型行业中的必备技术。在科技日益发达的信息技术时代，动态调度问题必将大量应用于信息流处理。在充分了解现有研究方法优缺点的基础上，开发新的更有效的动态调度问题的解决方法十分必要。目前绝大多数调度系统还处于研究原形阶段，工业原形系统也大多由大学或研究机构承担，真正应用于实际生产的调度系统并不多。因而今后应以研究能在实际中应用的调度系统为重点。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省