响应随机扰动的受影响工序重调度方法研究*

周亚勤 李蓓智 杨建国 杨 鹏

（东华大学机械工程学院，上海201620）

生产调度问题的多数文献主要研究在问题特性已知的前提假设下，如何来确定给定时间内的生产调度方案来指导生产。所产生的生产调度方案要能确定资源的冲突、控制工件释放的释放时间并支持刀具、原材料供应和资源分配等。调度问题是典型的NP完全问题［1］，对于静态调度问题，研究者们已提出许多求解最优调度方案的优化方法，如人工神经网络［2］、模拟退火［3］、禁忌搜索［4］、遗传算法［5］等。而在动态加工车间环境中，调度方案在执行过程中会遭受各种随机扰动的干扰，这些扰动可能会使原调度方案变得不再可行，需要进行重调度。这些扰动事件主要包括机器故障、原材料延误到达、紧急订单或工件插入、订单的取消等。大多数的扰动事件可以建模成机器故障，因为它们会使停机机床或其他机床上工序的加工中断一段时间。

重调度是指当扰动发生时，产生一新的可行的调度方案的过程。由于多数加工车间具有动态特性，这个问题实际意义比一般的调度问题更重要，但是在生产调度研究中研究者一直忽略这一点，直到最近才开始引起研究者的重视［6－7］。本文研究用于job shop调度问题的受影响工序重调度方法，首先给出受影响工序重调度的基本原理，然后介绍受影响工序重调度方法的算法过程，并给出对重调度方法进行测量的性能指标函数，最后通过一个案例证明所提出的重调度方法能够响应随机扰动，重新产生优化的新调度方案指导生产。

1 受影响工序重调度的基本原理

受影响的工序重调度仅对正在执行的调度方案中受扰动直接或间接影响的工序进行重调度，此算法基于Li等人提出的二叉树算法［8］。受影响的工序重调度是一种启发式重调度方法，它的目标是使新产生的调度方案的Makespan（完工时间）的增量最小，同时保留原调度方案中工件的加工顺序。

在大多数制造系统生产调度中，工序安排是基于工件工艺路线的，即不能违背工艺部门制定的工艺路线。任何一个可行的调度方案都必须满足这些工艺路线约束，同时描述机床上各工序的加工顺序及起始加工和结束时间，使得选定的目标最优或近优。

可以用二叉树来表示工件和机床加工的次序，树是一个单（根）节点（第一个受影响的工序）开始的图，二叉树是具有相连而不循环的节点的树，也就是从每个节点至多只发出两个分枝（见图1）。节点表示工序，每个节点的左分枝表示它的工件分枝，即该工序的下一道工序（noj），可以由工件的工艺路线约束得到，右边的分枝表示它的机床分枝，即该工序所在机床的下一个加工的工序（nom），可以由原调度方案中机床上工序的加工顺序得到。

受影响的工序重调度的基本原理是:通过将某些工序的起始加工时间向后延迟最小时间量来响应任何扰动。这个最小的时间量必须:（1）使得工件的工艺路线约束被满足;（2）保持原调度方案中每台机床上工序的初始加工顺序。

为了解决扰动引起的影响，研究开始受影响的工序（首先被扰动影响的工序）在它的工件和机床分枝上以及它们相应的工件和机床分枝上延误的影响。也就是，跟踪扰动的影响在“重调度”二叉树的分枝上的传播，重新更新二叉树，以开始受影响的工序为根节点，每个后继节点表示一个受影响的工序。

2 受影响工序重调度算法

2.1 符号设定

下面给出受影响的工序重调度算法中需要用到的符号定义:

R为扰动发生时需重新调度的剩余工序集合（包括中断工序和中断时还没有开始的工序）。

O为可能受影响的工序集合。

A为重调度后受影响的工序集合（有新的开始加工时间和结束时间）。

noj为工件的下一工序（工件分枝）。

nom为机床上的下一工序（机床分枝）。

jST为工序的开始加工时间，受工件上道工序的约束。

mST为工序的开始加工时间，受机床上前道工序的约束。

ST为原调度方案中工序的开始加工时间。

ET为原调度方案中工序加工的结束时间。

newST为新调度方案中工序的开始时间。

newET为新调度方案中工序的结束时间。

devST为原调度方案和新调度方案间开始时间的偏移。

readyTime为机床可用于加工的时间。

noR为集合R的基数（剩余工序的数量）。

noA为集合A的基数（受影响工序的数量）。

i为集合“A”的索引。

g为集合“O”的索引。

2.2 受影响的工序重调度算法

Step 1:设置i=1，g=1，devST=0，O=Φ，A=Φ，所有工序的jST=mST=0，首先判断第一个受影响的工序O［1］，扰动（机床发生故障）对原调度方案的影响有3种情况，见图2。在图2中，机床M3在时刻t发生故障，故障持续时间为r，由此，可以得出O［1］属于下面3种情况之一:

（1）被中断的工序，如果中断影响情况属于图2a中的情况。

（2）如果没有被中断的工序，那么选择停机机床上的第一道剩余工序;如果存在这道工序，且这道工序的ST比停机机床的readyTime小（停机机床的ready-Time等于停机时刻加上停机时间），见图2b。

（3）否则，算法中止，没有受影响的工序（即不需进行重调度），见图2c。

Step 2:将O［1］作为当前工序，它的mST等于停机机床的readyTime，g加1。

Step 3:当前工序的newST=Max（当前工序的jST，当前工序的mST）

当前工序的newET=当前工序的newST+当前工序的加工时间

Step 4:如果当前工序不能匹配到集合A中的任一受影响的工序v，那么转到Step 5，否则，重新设置A［v］的属性如下，然后转到Step 7。

devST=devST+Max（当前工序的newET－A［v］的newET，0）

A［v］的newST=Max（当前工序的newST，A［v］的newST）

A［v］的newET=A［v］的newST+A［v］的加工时间

Step 5:设置第i个受影响的工序A［i］=当前工序，i加1。

Step 6:devST=devST+（A［i］的newET－A［i］的ET）。

Step 7:由工件的工艺路线获得当前工序的工件分枝noj，如果noj存在，且它的ST＜当前工序的newET，那么，设置O［g］=noj，O［g］的jST= 当前工序的new-ET，g加1。

Step 8:由原调度方案获得当前工序的机床分枝nom，如果nom存在，且它的ST＜当前工序的newET，那么，设置O［g］=nom，O［g］的mST=当前工序的newET，g加1。

Step 9:从集合O中移去当前工序，将第7步和第8步中的新成员加入O。

Step 10:如果O=Φ，结束，否则，从集合O中随机选择一个工序作为当前工序，转到Step 3。

3 性能测量

我们采用3种性能测量指标对受影响工序重调度方法产生的新调度方案进行评价，进而评价此重调度方法的性能:新调度方案与原调度方案Makespan的变化率、各工序的开始加工时间偏移以及次序偏移。

（1）Makespan的变化率（Mp）

Makespan的变化率Mp定义如下:

式中:M0是原调度方案的Makespan，Mm是右移重调度方法产生的新调度方案的Makespan。

（2）开始时间偏移（devST）

这是对重调度方法效率的有效测量，特别是在辅助资源（如刀具和夹具）基于原调度方案运送到机床的工件环境下。很显然，如果材料比需求更早运输到的话，工件开始时间的改变可能会招致存储成本，如果刀具和材料的需求比原进度表中计划的时间更早，则会招致紧急订货成本。通过计算新调度方案和原调度方案之间工序结束时间差的绝对值的和，来计算开始时间的偏移，由两部分组成:延误=正的结束时间差的和，提前=负的结束时间差的绝对值的和

其中，n为工件数，hi为工件i的工序数。

（3）次序偏移（devSQ）

如果调整是基于机床上的初始工序序列提前准备的，那么这个测量是很关键的，采用下面的方法对次序偏移进行测量。

对新调度方案中每台机床k上的每道工序j，定义:S1=原调度方案中在工序j前加工的工序集合，S2=新调度方案中在工序j后加工的工序集合，S=S1∩s2，Njk=S的基数（集合的容量）。对机床k上的每道工序j，获得次序偏移，然后对所有机床上的偏移求和，求得次序偏移。

对于受影响工序重调度方法，Makespan的变化率、开始时间偏移比较小，因为它只对受影响的剩余工序进行重调度，同时它也没有次序偏移。

4 测试实例

我们以 Muth和 Thompson［9］提出的著名6×6标准检测问题（FT06）来进行测试，首先利用生物智能计算方法求得原调度方案，原调度方案的最优解Makespan等于55个时间单位，甘特图见图3。

生产中发生的多数扰动事件可以映射为机床发生故障，现在对机床发生故障扰动事件进行测试。假设图3所表示的原调度方案在执行过程中，机床M3在时刻25发生故障，故障持续时间为5个时间单位。

受影响工序重调度方法产生的新的调度方案的甘特图见图4。新调度方案中，中断前已调度工序的加工不变，只是将原调度方案中中断发生时刻之后受中断影响的工序进行重调度。根据算法判断各道工序新的起始加工时间和结束时间，新调度方案的Makespan等于60个时间单位。比较图3和4，可以看出，在机床M1和M2上，剩余工序没有受到影响;机床M3上，工件J4、J6;机床 M4上，工件 J4、J1，机床 M5上，工件J4、J3、J6、J1，机床 M6 上，J1、J4 这些工件相应的剩余工序受到影响，工序有新的开始加工时间和结束时间。受影响工序重调度产生的新调度方案与原调度方案中，Mapespan的变化率为9.1%，开始时间偏移为43个时间单位，工件各工序的加工顺序不变，没有次序偏移。

5 结语

生产调度方案在车间的加工过程中会受到各种随机扰动的影响，因此重新调度，产生新的调度方案响应随机扰动对实际生产有着很好的指导意义。本文对响应随机扰动的受影响工序重调度方法进行了研究，给出了此重调度方法的原理和算法过程，同时研究了评价重调度方法的性能指标，并对一案例进行了测试分析，结果表明所提出的重调度方法能产生优化的新调度方案响应扰动。

［1］Garey E L，Johnson D S，Sethi R.The complexity of flowshop and jobshop scheduling［J］.Maths Ops Res，1976，1（2）:117 －129.

［2］Ibrahim S，El－Baz M A，Esh E.Neural networks for job shop scheduling problems［J］.Journal of Engineering and Applied Science，2009，56（2）:169－183.

［3］Zhang R，Wu C.A hybrid immune simulated annealing algorithm for the job shop scheduling problem［J］.Applied Soft Computing Journal，2010，10（1）:79 －89.

［4］Eswaramurthy V P，Tamilarasi A.Tabu search strategies for solving job shop scheduling problems［J］.Journal of Advanced Manufacturing Systems，2007，6（1）:59 －75.

［5］Ritwik K，Deb S.A genetic algorithm－based approach for optimization of scheduling in job shop environment［J］.Journal of Advanced Manufacturing Systems，2011，10（2）:223 －240.

［6］王志亮，汪惠芬，张友良.动态Job Shop调度问题的一种自适应遗传算法［J］.中国机械工程，2004，15（11）:995 －999.

［7］舒海生，赵刚，赵丹，等.考虑刀具流的Job Shop动态调度的研究［J］.制造技术与机床，2008（3）:21 －23，27.

［8］Li R，Shyu Y，Adiga S.A heuristic rescheduling algorithm for computer－ based production scheduling systems［J］.International Journal of Production Research，1993，31（8）:1815 －1826.

［9］Lawrence S.Resource constrained project scheduling:an experimental investigation of heuristic scheduling techniques（Supplement）［D］.Graduate School of Industrial Administration，Carnegie－Mellon University，1984.

［10］周亚勤，李蓓智，杨建国.考虑批量和辅助时间等生产工况的智能调度方法［J］.机械工程学报，2006，42（1）:57 －61.