工序松弛规则及其在动态Job-Shop调度问题中的应用仿真研究

范华丽，熊禾根，钱国洁，蒋国璋，李公法

（武汉科技大学 机械自动化学院，武汉 430081）

0 引言

车间作业调度问题自上个世纪五十年代被Jonson[1]提出以来，一直受到各个学科和领域的广泛关注。车间作业调度有多种类型，其中Job-Shop调度问题[2]由于其在实际生产中存在的广泛性及问题的复杂性，成为了研究的热点。求解Job-Shop问题的方法有多种类型，其中智能算法和启发式算法[3]因其能够快速有效的得到近优解而成为近年来的研究热点。然而在实际企业的生产车间中，通常有成百上千个工件等待加工，且车间参数及工况会随时变化，如机器故障，紧急订单的插入等，因此需要实时地进行重调度，智能算法和启发式算法在针对此类问题时，通常不能很快的得到近优解，而早期的优先规则[4]因其算法的简洁性和易于执行等特点，在求解此类问题时显现出优势。

优先规则有多种，很多文献[5][6]给出了关于它们性能的分析研究，也得出了一些具有参考意义的结论[7]。本文根据已有的优先规则，提出了一个新的规则SOP（slack of operation processing time），在考虑具有扩展工艺约束的调度问题模型中分析和比较了该规则的性能。并从工件总拖期和拖期工件百分比两个性能指标进行分析，探索了扩展工艺约束率和交货期宽裕度系数对调度规则性能的影响。

1 新规则的提出

优先规则有多种类型，根据所包含的信息，一般可分为以下四类：基于加工工时的规则、基于交货期的规则、组合规则和既非基于加工工时也非基于交货期的规则。这些规则中，有不少是在已有基础上进行改进得到的。如Baker[8]对SPT(shortest processing time)和EDD(earliest due date)规则的性能曲线进行分析，发现当交货期较紧时SPT性能较好，当交货期较松时，EDD性能较好，因此进行综合，在松弛较多时取工件交货期为优先值，在工件没有松弛时取加工工时作为优先值，得到了性能较好的MDD(modified due date)规则，MDD实质就是SPT和EDD的组合。又如Conway[9]对工件交货期di进行细化进而提出了工序交货期dij的概念，Baker和Kennet[10]在此基础上得到了改进的规则MOD(modified operation due date)，其实质也是把MDD规则优先值中的工件交货期改成了工序交货期，通过仿真试验结果证明其性能较好。

受到上述文献的启发，在工件松弛SLACK的基础上，提出了工序松弛的概念。工件松弛是指工件交货期减去当前时间和该工件所有剩余加工工时。工序松弛可以定义为工序交货期减去当前时间和工序加工工时，因此工序松弛越小，这道工序就越紧急，也应具有最高的优先级从而最先被加工。我们依此提出SOP规则，它的优先值为：

2 问题的模型

动态Job-Shop调度问题可以描述为有一系列工件J陆续到达具有M台机器的车间，每个工件有一个到达时间ri和交货期di，每个工件都有一定数量的工序ni，它们按照不同的工艺顺序约束在不同机器上加工，工序i的第j道工序的加工工时为pij。要求确定各机器上所有工件的加工开始时间和加工完成时间，使得某个性能指标达到最优。通常这里的工艺约束指的是一个工件内部所定义的工艺路线顺序约束，文献[11]指出，在许多加工装配型离散制造企业中，还存在另外两类工艺约束，即工艺路线中的延时约束和工件间的工艺约束，我们把这类约束定义为扩展工艺约束。本文的仿真模型即考虑具有扩展工艺约束的动态Job-Shop调度问题，调度目标为最小化工件总拖期T和拖期工件百分比%T。

3 调度规则试验处理与分析

工件陆续到达的Job-Shop调度问题是一种典型的动态车间作业调度问题。针对此类问题进行仿真调度试验，在具有扩展工艺约束的动态车间作业调度问题中，比较和分析不同调度规则的性能，并研究不同车间模型参数对调度规则性能的影响。

3.1 仿真试验的设计与生成

仿真试验案例中有10台机器，工件总数为3000个，以指数分布形式分批到达车间，批量大小服从离散均匀分布每个工件的工序数量从离散均匀分布DU[3,6]中产生。工件的工艺路线随机生成，每道工序的加工机器以相同概率按无放回抽样方式从10台机器中产生。每道工序的加工工时从离散均匀分布DU[5,15]中产生，因此每道工序的平均加工时间个单位时间。同时工件间具有扩展工艺约束的工序是随机生成且没有冲突的。

通常，车间利用率Ug是反映工件投放时间的一个因素。对于本文中的考虑扩展约束的动态车间作业调度问题，车间利用率可作如下定义：

式中，m是车间中机器的数量，指平均每个工件的工序数量，指平均每个工件的加工工时，是指工件批量到达的平均时间间隔。因此每给定一个车间利用率，就可以得到相应的工件批量到达的时间间隔。不失一般性，假设第一批工件的到达时间为0，则根据时间间隔tv可计算出每批工件的到达时间，即投放时间ri。

考虑到具有扩展工艺约束的工件的数量或许会是影响调度规则性能的一个因素，我们引进Ec作为工件扩展工艺约束率。本文的仿真试验中，我们选取了四个不同程度的工件扩展工艺约束率，即0%、3%、5%、8%。

此外，工件交货期的设置采用的是TWK(Total Work Content)规则，即式中，c是交货期宽裕度系数，它表示了交货期设置的松紧程度。由于拖期工件百分比%T是衡量交货期松紧程度的一个合理指标，因此可通过不同的%T来控制交货期的松紧程度。对于不同程度的Ug和Ec，我们根据四种不同程度的%T设置相应的四个不同松紧程度的c值，即对应松交货期，对应中等程度的交货期，对应紧交货期。例如，当时，通过仿真试验得到不同程度下的交货期宽裕度系数取值分别为c=10,14,20,28。

仿真试验测试了四种Ec和四种不同c值，因此共有16个不同变量的仿真试验，对于不同仿真参数的试验运行10次取其平均值。考虑到车间稳定状态和所采集数据的有效性及合理性，截除前后各500个工件，采集10次仿真在各调度规则下的工件总拖期和拖期工件百分比。

3.2 调度规则的选择

仿真试验所选用的调度规则包括：SPT、EDD、MDD、ODD、RR、WINQ[12](total work-content of jobs in the queen of the next operation of a job)和SOP。这几种规则都是性能较好且运用较广泛的规则。

3.3 试验结果的分析与评价

3.3.1 基于工件总拖期的分析

为了更加直观的分析Ec和c对调度规则性能的影响，我们对试验数据进行两方面的分析，即固定一个c值，看不同Ec对调度规则性能的影响，以及固定一个Ec，看不同c值下各个调度规则的性能。为了使结果更具有代表性和说明性，我们在考虑这两个方面时，均选取中等程度的交货期宽裕度和适度的扩展工艺约束率。

表1列出了在中等程度的交货期宽裕度即[10%,20%]时，不同Ec下各调度规则的工件总拖期的相对增长程度RPI(the relative percentage increase)。用SR表示调度规则的集合，T(X)表示规则的工件总拖期，规则X的工件总拖期的相对增长程度RPI(T)可定义为：

表1 四种扩展工艺约束下各调度规则的工件总拖期的相对增长程度

表1中各调度规则按照RPI值递增排列。从表中可以看出当交货期程度适度时，SOP在无扩展工艺约束下表现最优，当考虑扩展工艺约束时，它的性能也较好。同时RR规则在不同扩展工艺约束程度下性能也较好，而WINQ在扩展工艺约束程度较高时表现一般，在无扩展工艺约束时性能较好。此外，SPT规则在以工件总拖期为调度目标下的性能较差。

图1中列出了交货期程度适度的情况下，各调度规则在四种不同扩展工艺约束程度下的工件总拖期，从图中可以看出，工件的扩展工艺约束程度影响着工件总拖期，影响趋势表现为随着Ec的增大工件总拖期也随着增大。同时，除SPT受扩展工艺约束程度的影响较大外，其他规则均以合理的程度增长且相应的工件总拖期基本持平。

图1 不同扩展工艺约束下各调度规则的工件总拖期

选择中等程度的扩展工艺约束如Ec=3%时，此时4个不同c值下的各调度规则的RPI(T)如表2所示。从表中可以看出，在不同程度交货期下，SOP均是最好的规则，RR规则次之。且不同c值下，SPT规则的性都能较差。

图2反映出c值影响着T，影响趋势表现为随着c的增大T随之减小。对于各种调度规则，T均随着c值的增加而减小，即c值越大，T也越小。此时，SPT规则受交货期松紧程度的影响也较大，其它规则的工件总拖期在不同c值下变化趋势相似。

综上所述，在考虑具有扩展工艺约束和交货期宽裕度的动态车间作业调度问题中，当以工件总拖期为调度目标时，SOP规则表现较好。且可知，扩展工艺约束程度和交货期宽裕程度同时影响调度规则的性能，即扩展工艺约束程度越大工件总拖期越大；而当交货期宽裕程度增大时，工件总拖期减小。

表2 四种交货期宽裕度系数值下各调度规则的工件总拖期的相对增长程度

图2 不同交货期宽裕度系数下各调度规则的工件总拖期

3.3.2 基于拖期工件百分比的分析

与对工件总拖期的处理相同，我们仍对试验数据进行两方面的分析，即分别从扩展工艺约束程度和交货期宽裕程度进行分析。

表3 四种扩展工艺约束程度下不同调度规则的拖期工件百分比

从表3中可以看出，在中等程度的交货期宽裕度下，各种调度规则的T%都保持在10%～30%之间。在每种参数配置下，按照拖期工件百分比递增排列，即可得当以拖期工件百分比T%为调度目标时，性能较优的规则。此时，SOP性能仍较好。

图3列出了中等程度的交货期宽裕度时四种不同Ec下，各调度规则下的拖期工件百分比T%随扩展工艺约束的变化。

图3 不同扩展工艺约束程度下各调度规则的拖期工件百分比

此时，不同扩展工艺约束程度对调度规则性能的影响不像以工件总拖期为调度目标时那样明显，可见在以拖期工件百分比为调度目标时，扩展工艺约束程度对调度规则的性能影响微小。但仍可看到SOP、RR和MDD的性能与其他规则相比性能较好。同时，从图4中可看到在以T%为调度目标时，交货期宽裕程度对各调度规则性能的影响很明显，且此时SOP的性能仍是最好的。

图4 各调度规则在不同交货期宽裕度系数下的T%

4 结束语

本文提出了一种新的优先规则SOP，以考虑具有扩展工艺约束的动态Job-Shop调度问题为模型，测试了该规则的性能，并分别在以工件总拖期和拖期工件百分比为调度目标下，分析了扩展工艺约束程度和交货期宽裕程度对调度规则性能的影响。结果表明，所提出的优先规则SOP在以工件总拖期和拖期工件百分比为调度目标下性能都较好，具有较好的鲁棒性。当以工件总拖期为调度目标时，扩展工艺约束程度和交货期宽裕程度同时影响调度规则的性能，即扩展工艺约束程度越大工件总拖期越大；而当交货期宽裕程度增大时，工件总拖期减小。当以拖期工件百分比为调度目标时，交货期宽裕程度在以拖期工件百分比为调度目标时对各调度规则性能的影响很明显，而扩展工艺约束程度对调度规则的性能影响较小。

此外，关于各种调度规则性能测试的仿真试验在已有的文献中并不少见，但在实际生产中，要从中选择一个合适的规则并不容易，因为调度规则的数量庞大，而通常这些文献都使用了不同的调度目标来评价调度规则的性能，有不同的运行条件并且有时会给出相互矛盾的结果，因此有必要建立专家系统以选择和生成合适的调度规则以满足实际生产中的调度目标。

[1]Jonson S M.Optional two and three-stage production scheduling with set-up times included[J].Naval Research Logistics Quarterly,1954,1:64-68.

[2]Blazewicz J,Domschke W,Pesch E.The job shop scheduling problem: conventional and new techniques[J].European Journal of Operational Research,1996,93(1):1-33.

[3]刑文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,2001.

[4]Haupt R.A survey of priority rule-based scheduling[J].OR Spektrum.1989,11:3-16.

[5]Vinod V,Sridharan R.Scheduling a dynamic job shop production system with sequence-dependent setups: An experimental study[J].Robotics and Computer-Integrated Manufacturing,2008,24(3):435-449.

[6]Binchao Chen, Timothy I.Matis.A flexible dispatching rule for minimizing tardiness in job shop scheduling[J].International Journal of Production Economics,2013,141(1):360-365.

[7]Eva Vallada, Rubén Ruiz, Gerardo Minella.Minimising total tardiness in the m-machine flowshop problem:A review and evaluation of heuristics and metaheuristics[J].Computers and Operations Research.2008,35(4):1350-1373.

[8]Baker K R, Bertrand J W M.A dynamic priority rule for scheduling against due-dates[J].Journal of Operations Management,1982,3(1):37-42.

[9]Conway R W, Maxwell WL, Miller LW.Theory of scheduling [J].Addison-Wesley, 1967, Reading, MA.

[10]Baker K R,Kennet J J.Job shop scheduling with modified due dates[J].Operations Management.1983,4:11-22.

[11]熊禾根,李建军,孔建益,杨金堂,等.考虑工序相关性的动态Jobshop调度问题启发式算法[J].机械工程学报,2006,42(8):50-55.

[12]Rajendran C, Holthaus O.A comparative study of dispatching rules in dynamic flowshops and job shops [J].European Journal of Operational Research,1999,116(1):156-170.