下载掌阅APP，畅读海量书库
立即打开
在企业的实际生产过程中，无论是离散事件系统，还是连续过程的生产系统，都存在着由市场需求变化等企业外部原因及生产设备故障等企业内部原因所产生的干扰，这使得静态调度的性能遭到破坏，甚至变得不再可行。因此，在车间调度的研究中需要适当考虑实际生产车间中的动态因素。
动态调度是指充分考虑事前调度环境和任务及系统当前的状态，及时给出正确或合理的调度策略或方案，从而达到全局优化。
与静态调度相比，动态调度是一个更加复杂的控制与优化过程，即在满足车间内在约束的前提下，有效处理生产环境中发生的动态事件所产生的干涉，为工件合理分配设备，并确定工件在相关设备上的加工顺序和开工/完工时间，以优化生产系统的性能。动态调度不仅要求能够快速响应变化以使得调度过程平稳、持续地得以进行，还要保持良好的调度性能。Vieira、Aytug和Potts及Strusevich等人分别从不同角度对早期一些探索性研究成果进行了综述。目前关于动态调度方式的研究可以归结为三类，见表1.1，下面分别进行简单介绍。
表1.1 动态调度方式
1.鲁棒调度
鲁棒调度是指根据当前信息或未来一部分可测信息预先生成一个调度方案，该方案尽可能考虑到调度在执行过程中发生的干扰事件。
鲁棒调度研究的热点是试图产生具有健壮性的调度方案，即按照生成的调度方案实施车间调度可以保证生产系统的性能在实际发生动态事件的干涉下不会出现大幅度恶化。Yellig和Mackulak根据设备的历史表现，采用统计方法得出分布函数，从而估计设备可能出故障的时间间隔。李素粉等采用数学期望预测设备发生故障时刻，然后将启发式规则和遗传算法相结合，计算鲁棒调度计划。O'Donovan等人在建立具有健壮性的调度模型时估计可能的动态事件导致系统性能下降的程度，在调度方案中加入额外的设备空闲时间，以吸纳动态事件产生的干涉。刘琳研究了在三种典型情况：加工时间不确定、机器随机故障和工件到达时间未知下的鲁棒调度方法。
由于在实际的动态事件发生之前进行了积极预防，故鲁棒调度具有容纳可能发生的动态事件的能力，具有较好的健壮性。但是，鲁棒调度常常含有过多的设备空闲时间，这是对资源的极大浪费。另外，鲁棒调度几乎不考虑当实际发生的动态事件与预测的、可能发生的动态事件有偏差时该如何处理，因此对预测之外的突发事件的反应能力较差，从而很可能导致系统性能的大幅度下降。
2.预-反应调度/重调度
预-反应调度一般分两个阶段进行：首先根据已获得信息而不考虑未来干扰事件的发生，生成一个优化某一目标的调度方案，这个方案称为预调度；然后在执行这个预调度的过程中检测其执行情况，当执行过程中发生的一些动态事件使得实际调度偏离了预调度且偏离累积到一定程度时，触发重调度（反应调度）过程，对预调度的部分或全部进行修改，从而保持调度的可行性或改善调度的性能，以消除发生的干扰事件产生的影响。预-反应调度也被很多学者称为重调度。
预-反应调度研究的关键问题之一是如何确定重调度时刻，即何时应该启动重调度。Church和Uzsoy归纳了三种确定重调度时刻的方法：事件驱动、周期驱动及事件和周期混合驱动。很多学者研究了重调度的频率对系统性能的影响，如Church和Uzsoy、Sabuncuoglu和Bayiz，以及Perry和Uzsoy等人。他们的研究显示，提高重调度的频率可以有效提高系统性能，但重调度的频率增加达到一定程度后不会带来更多系统性能提高，只会导致系统的混乱，增加重调度引起的成本。研究者开发了滚动窗口方法来实现周期驱动或混合驱动的重调度，以降低计算复杂度。这种方法将复杂的动态调度过程分解为一系列窗口内的静态调度，从而可以在每个窗口内直接应用一些成熟的静态调度理论及方法，如Singe使用了基于瓶颈漂移过程的启发式分解方法；Shafaei和Brun利用调度规则生成周期调度计划；Qi等人使用了多种群遗传算法；潘全科和朱剑英用遗传算法实行多目标优化。很多研究者的实验结果显示，滚动窗口的大小在一定程度上影响调度的效率和质量，然而窗口大小的确定是难点。在实际生产中，为了简便，通常把窗口设定为固定时间长度的窗口，如一个班次。
预-反应调度研究的另一个关键问题是如何生成预调度和修补预调度。生成预调度的方法非常多，关于这方面的综述也很多，比较具有代表性的有Pindo和Chao的工作。关于预调度的修补通常有三种办法：右移、部分修改和全部修改。Abumizar和Svestka认为在干涉发生时，仅仅重新调度那些直接或间接受干涉影响的工件能有效降低由于干涉引起的生产周期的增加，同时减小了与预调度的偏差，效率和稳定性都较好。然而，这样的修改很难操作。
预-反应调度实际上在必要时才对干扰进行响应，相对于鲁棒调度，该方法对突发事件的响应能力有所提高，但是可能导致较差的健壮性和稳定性。在很多制造车间中，预调度根据当前车间层状态和订单信息来生成从现在到未来某段时间内的计划，如一天或一个班次。预调度在计划时段的开始时刻下放到车间层，其发挥着两个重要功能：对不同的工件分配资源，来优化某些性能指标；指导车间层外部活动的计划安排，如原料购买、设备维护和订单下放等。因此，在执行过程中尽量跟随预调度是很重要的。调度的频繁修改可能延迟或导致以预调度为基础的外部活动无法正常执行。有学者对预-反应调度的实用性进行了研究，研究结果表明，在动态事件发生不频繁、不确定程度低的生产环境中，预-反应调度的效果比较好；然而在动态事件发生频繁、不确定程度高的生产环境中，频繁进行重调度很容易导致生产系统混乱，降低生产系统的性能。
3.完全反应调度/动态（在线、实时）调度
完全反应调度与前两种调度方法不同，其并不生成一个完整的预调度方案，而是在必要时刻（决策时刻），根据生产系统当前暂时的状态和可获得的局部信息，采用某种策略快速、经济地做出局部调度决策，对动态事件产生的干涉进行处理，使得生产系统在动态事件的干扰下依然保持高效、平稳生产。完全反应调度也被某些研究者称为动态调度（Dynamic Scheduling）、在线调度（Online Scheduling）或实时调度（Reactive Scheduling）。
完全反应调度能够对突发事件实现实时响应，其调度决策取决于系统的当前状态，因此与实时信息获取密切相关。虽然完全反应调度只是在必要时刻基于生产系统的现行状态和局部信息做出局部调度决策，但它能从上层系统中获得工件交货期等全局信息，能够以长远的眼光安排调度过程，从而实现全局优化的目的。另外，它不需要频繁修改调度不会因此使得车间生产状态变得混乱。因此，完全反应调度具有很好的实用性，在实际生产中的应用非常广泛。已有研究表明，在动态事件发生频繁、不确定程度高的生产环境中，完全反应调度的性能比较好。现在对完全反应调度的研究已成为动态调度领域的研究热点之一。