基于规则的任务调度优化方案

1）基本原理

基于规则的调度方法（简称为规则调度方法）的基本原理是：针对特定的制造系统设计或选用一定的调度规则，系统运行时，调度控制器根据这些规则和制造过程的某些易于计算的参数（如加工时间、交付期、队列长度、机床负荷等）确定每一步的操作（如选择1个新零件投入系统、从工作站队列中选择下一个零件进行加工等），由此实现对生产过程的调度控制。

2）调度规则简介

实现规则调度方法的前提是必须有适用的规则，由此推动了对调度规则的研究。目前研究出的调度规则已达100多种。这些规则概括起来可分为4类，即简单优先规则、组合优先规则、加权优先规则和启发式规则。下面分别作介绍。

（1）简单优先规则。简单优先规则是一类直接根据系统状态和参数确定下一步操作的调度规则。这类规则的典型代表有如下几种。

①先进先出（first in first out，FIFO）规则：根据零件到达工作站的先后顺序来执行加工作业，先来的先进行加工。

②处理时间最短（shortest processing time，SPT）规则：优先选择具有最短加工时间的零件进行处理。SPT规则是经常使用的规则，它可以获得最少的在制品、最短的平均工作完成时间以及最短的平均工作延迟时间。

③交付期最早（earliest due date，EDD）规则：根据订单交货期的先后顺序安排加工，即优先选择具有最早交付期的零件进行处理。这种方法在作业时间相同时往往效果较好。

④剩余工序数最小（fewest operation remaining，FOPNR）规则：根据剩余作业数来安排加工顺序，剩余作业数越少的零件越先加工。这是考虑到较少的作业意味着有较少的等待时间。因此使用该规则可使平均在制品少、制造提前期和平均延迟时间较少。

⑤下一队列工作量（work in next queue，WINQ）规则：优先选择下一队列工作量最少的零件进行处理。所谓下一队列工作量是指零件下一工序加工处的总工作量（加工和排队零件工作量之和）。

⑥剩余松弛时间（slack time remained，STR）规则：剩余松弛时间越短的越先加工。剩余松弛时间是将在交货期前所剩余的时间减去剩余的总加工时间所得的差值，其计算公式为

式中，Sk为剩余松弛时间；D为交付时间；t为当前时间；pj为第j工序的加工时间；k为当前要进行的工序号；j为零件工序总数。

该规则考虑的是，剩余松弛时间值越小，越有可能拖期，故STR最短的任务应最先进行加工。

（2）组合优先规则。组合优先规则是根据某些参数（如队列长度等）交替运用两种或两种以上简单优先规则对零件进行处理的复合规则。例如，FIFO/SPT就是FIFO规则和SPT规则的组合，即当零件在队列中等待时间小于某一设定值时，按SPT规则选择零件进行处理；若零件等待时间超过该设定值，则按FIFO规则选择零件进行处理。

（3）加权优先规则。加权优先规则是通过引入加权系数对以上两类规则进行综合运用而构成的复合规则。例如，SPT+WINQ规则就是一个加权规则。其含义是，对SPT和WINQ分别赋予加权系数W1和W2，进行调度控制时，先计算零件处理时间与下一队列工作量，然后按照W1和W2对其求加权和，最后选择加权和最小的零件进行处理。

（4）启发式规则。启发式规则是一类更复杂的调度规则，它将考虑较多的因素并涉及人类智能的非数学方面。例如，Alternate Operation规则这样一条启发式调度规则，其决策过程如下：如果按某种简单规则选择了一个零件而使得其他零件出现“临界”状态（如出现负的松弛时间），则观察这种选择的效果；如果某些零件被影响，则重新选择。

一些研究结果表明，组合优先规则、加权优先规则和启发式规则比起简单优先规则来有较好的性能。例如，组合优先规则FIFO/SPT可以在不增加平均通过时间的情况下有效减小通过时间方差。(www.xing528.com)

3）规则调度方法的优点和不足分析

（1）优点：计算量小，实时性好，易于实施。

（2）不足：该方法不是一种全局最优化方法。一种规则只适应特定的局部环境，没有任何一种规则在任何系统环境下的各种性能上都优于其他规则。

例如，松驰量最小（SLACK），规则虽然能使调度控制获得较好的交付期性能（如延期时间最小），但却不能保证设备负荷平衡度、队列长度等其他性能指标最优。这样，当设备负荷不平衡造成设备忙闲不均而影响生产进度时，便会反过来影响交付时间。同样，由于制造系统中缓冲容量是有限的，如果队列长度指标恶化，很容易造成系统堵塞，反过来也会影响交付时间。因此，基于规则的调度方法难以适用于更广泛的系统环境，更难以适用于动态变化的系统环境。

4）规则动态切换调度控制系统

由以上讨论可知，静态、固定地应用调度规则不易获得好的调度效果，为此应根据制造系统的实际状态，动态地应用多种调度规则来实现调度控制。由此构成的调度控制系统称为规则动态切换调度控制系统。下面介绍这类系统的实现方法。

（1）系统原理。规则动态切换调度控制系统的实现原理是：根据制造系统的实际情况，确定适当调度规则集，并设计规则动态选择逻辑和相关的计算决策装置。系统运行时，根据实际状态，动态选择规则集中的规则，通过实时决策实现调度控制。

（2）实现框图。规则动态切换调度控制系统的实现框图如图5-22所示。其中，R1，R2，…，Rr为调度规则集中的r条调度规则。动态选择模块是一个逻辑运算装置，可根据输入指令和系统状态，动态选择规则集中的某一条规则。计算决策模块的作用是，根据被选中的规则计算每一候选调度方案对应的性能准则值，然后根据准则值的大小做出选择调度方案的决策，并向制造过程发出相应的调度控制指令。

（3）应用举例。

例用SPT、FIFO规则进行动态切换调度控制。规则动态调度控制系统如图5-22所示。

图5-22　规则动态切换调度控制系统

①选取状态变量：零件在队列中的平均等待时间。

②确定切换阈值。

③确定性能准则：零件加工时间、零件到达时间。

④动态选择模块功能设计：当零件在队列中的平均等待时间（状态变量取值）小于设定的阈值Tk时，选用SPT规则进行调度，若零件等待时间超过该设定值，则选用FIFO规则进行调度。

⑤计算决策模块功能设计：SPT有效时，计算各零件的加工时间（性能准则1），选择最短者进行处理；FIFO有效时，计算各零件的到达时间（性能准则2），选择最早者进行处理。