響應(yīng)隨機(jī)擾動(dòng)的受影響工序重調(diào)度方法研究*

周亞勤 李蓓智 楊建國(guó) 楊 鵬

（東華大學(xué)機(jī)械工程學(xué)院，上海201620）

生產(chǎn)調(diào)度問題的多數(shù)文獻(xiàn)主要研究在問題特性已知的前提假設(shè)下，如何來確定給定時(shí)間內(nèi)的生產(chǎn)調(diào)度方案來指導(dǎo)生產(chǎn)。所產(chǎn)生的生產(chǎn)調(diào)度方案要能確定資源的沖突、控制工件釋放的釋放時(shí)間并支持刀具、原材料供應(yīng)和資源分配等。調(diào)度問題是典型的NP完全問題［1］，對(duì)于靜態(tài)調(diào)度問題，研究者們已提出許多求解最優(yōu)調(diào)度方案的優(yōu)化方法，如人工神經(jīng)網(wǎng)絡(luò)［2］、模擬退火［3］、禁忌搜索［4］、遺傳算法［5］等。而在動(dòng)態(tài)加工車間環(huán)境中，調(diào)度方案在執(zhí)行過程中會(huì)遭受各種隨機(jī)擾動(dòng)的干擾，這些擾動(dòng)可能會(huì)使原調(diào)度方案變得不再可行，需要進(jìn)行重調(diào)度。這些擾動(dòng)事件主要包括機(jī)器故障、原材料延誤到達(dá)、緊急訂單或工件插入、訂單的取消等。大多數(shù)的擾動(dòng)事件可以建模成機(jī)器故障，因?yàn)樗鼈儠?huì)使停機(jī)機(jī)床或其他機(jī)床上工序的加工中斷一段時(shí)間。

重調(diào)度是指當(dāng)擾動(dòng)發(fā)生時(shí)，產(chǎn)生一新的可行的調(diào)度方案的過程。由于多數(shù)加工車間具有動(dòng)態(tài)特性，這個(gè)問題實(shí)際意義比一般的調(diào)度問題更重要，但是在生產(chǎn)調(diào)度研究中研究者一直忽略這一點(diǎn)，直到最近才開始引起研究者的重視［6－7］。本文研究用于job shop調(diào)度問題的受影響工序重調(diào)度方法，首先給出受影響工序重調(diào)度的基本原理，然后介紹受影響工序重調(diào)度方法的算法過程，并給出對(duì)重調(diào)度方法進(jìn)行測(cè)量的性能指標(biāo)函數(shù)，最后通過一個(gè)案例證明所提出的重調(diào)度方法能夠響應(yīng)隨機(jī)擾動(dòng)，重新產(chǎn)生優(yōu)化的新調(diào)度方案指導(dǎo)生產(chǎn)。

1 受影響工序重調(diào)度的基本原理

受影響的工序重調(diào)度僅對(duì)正在執(zhí)行的調(diào)度方案中受擾動(dòng)直接或間接影響的工序進(jìn)行重調(diào)度，此算法基于Li等人提出的二叉樹算法［8］。受影響的工序重調(diào)度是一種啟發(fā)式重調(diào)度方法，它的目標(biāo)是使新產(chǎn)生的調(diào)度方案的Makespan（完工時(shí)間）的增量最小，同時(shí)保留原調(diào)度方案中工件的加工順序。

在大多數(shù)制造系統(tǒng)生產(chǎn)調(diào)度中，工序安排是基于工件工藝路線的，即不能違背工藝部門制定的工藝路線。任何一個(gè)可行的調(diào)度方案都必須滿足這些工藝路線約束，同時(shí)描述機(jī)床上各工序的加工順序及起始加工和結(jié)束時(shí)間，使得選定的目標(biāo)最優(yōu)或近優(yōu)。

可以用二叉樹來表示工件和機(jī)床加工的次序，樹是一個(gè)單（根）節(jié)點(diǎn)（第一個(gè)受影響的工序）開始的圖，二叉樹是具有相連而不循環(huán)的節(jié)點(diǎn)的樹，也就是從每個(gè)節(jié)點(diǎn)至多只發(fā)出兩個(gè)分枝（見圖1）。節(jié)點(diǎn)表示工序，每個(gè)節(jié)點(diǎn)的左分枝表示它的工件分枝，即該工序的下一道工序（noj），可以由工件的工藝路線約束得到，右邊的分枝表示它的機(jī)床分枝，即該工序所在機(jī)床的下一個(gè)加工的工序（nom），可以由原調(diào)度方案中機(jī)床上工序的加工順序得到。

受影響的工序重調(diào)度的基本原理是:通過將某些工序的起始加工時(shí)間向后延遲最小時(shí)間量來響應(yīng)任何擾動(dòng)。這個(gè)最小的時(shí)間量必須:（1）使得工件的工藝路線約束被滿足;（2）保持原調(diào)度方案中每臺(tái)機(jī)床上工序的初始加工順序。

為了解決擾動(dòng)引起的影響，研究開始受影響的工序（首先被擾動(dòng)影響的工序）在它的工件和機(jī)床分枝上以及它們相應(yīng)的工件和機(jī)床分枝上延誤的影響。也就是，跟蹤擾動(dòng)的影響在“重調(diào)度”二叉樹的分枝上的傳播，重新更新二叉樹，以開始受影響的工序?yàn)楦?jié)點(diǎn)，每個(gè)后繼節(jié)點(diǎn)表示一個(gè)受影響的工序。

2 受影響工序重調(diào)度算法

2.1 符號(hào)設(shè)定

下面給出受影響的工序重調(diào)度算法中需要用到的符號(hào)定義:

R為擾動(dòng)發(fā)生時(shí)需重新調(diào)度的剩余工序集合（包括中斷工序和中斷時(shí)還沒有開始的工序）。

O為可能受影響的工序集合。

A為重調(diào)度后受影響的工序集合（有新的開始加工時(shí)間和結(jié)束時(shí)間）。

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

nom為機(jī)床上的下一工序（機(jī)床分枝）。

jST為工序的開始加工時(shí)間，受工件上道工序的約束。

mST為工序的開始加工時(shí)間，受機(jī)床上前道工序的約束。

ST為原調(diào)度方案中工序的開始加工時(shí)間。

ET為原調(diào)度方案中工序加工的結(jié)束時(shí)間。

newST為新調(diào)度方案中工序的開始時(shí)間。

newET為新調(diào)度方案中工序的結(jié)束時(shí)間。

devST為原調(diào)度方案和新調(diào)度方案間開始時(shí)間的偏移。

readyTime為機(jī)床可用于加工的時(shí)間。

noR為集合R的基數(shù)（剩余工序的數(shù)量）。

noA為集合A的基數(shù)（受影響工序的數(shù)量）。

i為集合“A”的索引。

g為集合“O”的索引。

2.2 受影響的工序重調(diào)度算法

Step 1:設(shè)置i=1，g=1，devST=0，O=Φ，A=Φ，所有工序的jST=mST=0，首先判斷第一個(gè)受影響的工序O［1］，擾動(dòng)（機(jī)床發(fā)生故障）對(duì)原調(diào)度方案的影響有3種情況，見圖2。在圖2中，機(jī)床M3在時(shí)刻t發(fā)生故障，故障持續(xù)時(shí)間為r，由此，可以得出O［1］屬于下面3種情況之一:

（1）被中斷的工序，如果中斷影響情況屬于圖2a中的情況。

（2）如果沒有被中斷的工序，那么選擇停機(jī)機(jī)床上的第一道剩余工序;如果存在這道工序，且這道工序的ST比停機(jī)機(jī)床的readyTime?。ㄍC(jī)機(jī)床的ready-Time等于停機(jī)時(shí)刻加上停機(jī)時(shí)間），見圖2b。

（3）否則，算法中止，沒有受影響的工序（即不需進(jìn)行重調(diào)度），見圖2c。

Step 2:將O［1］作為當(dāng)前工序，它的mST等于停機(jī)機(jī)床的readyTime，g加1。

Step 3:當(dāng)前工序的newST=Max（當(dāng)前工序的jST，當(dāng)前工序的mST）

當(dāng)前工序的newET=當(dāng)前工序的newST+當(dāng)前工序的加工時(shí)間

Step 4:如果當(dāng)前工序不能匹配到集合A中的任一受影響的工序v，那么轉(zhuǎn)到Step 5，否則，重新設(shè)置A［v］的屬性如下，然后轉(zhuǎn)到Step 7。

devST=devST+Max（當(dāng)前工序的newET－A［v］的newET，0）

A［v］的newST=Max（當(dāng)前工序的newST，A［v］的newST）

A［v］的newET=A［v］的newST+A［v］的加工時(shí)間

Step 5:設(shè)置第i個(gè)受影響的工序A［i］=當(dāng)前工序，i加1。

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

Step 7:由工件的工藝路線獲得當(dāng)前工序的工件分枝noj，如果noj存在，且它的ST＜當(dāng)前工序的newET，那么，設(shè)置O［g］=noj，O［g］的jST= 當(dāng)前工序的new-ET，g加1。

Step 8:由原調(diào)度方案獲得當(dāng)前工序的機(jī)床分枝nom，如果nom存在，且它的ST＜當(dāng)前工序的newET，那么，設(shè)置O［g］=nom，O［g］的mST=當(dāng)前工序的newET，g加1。

Step 9:從集合O中移去當(dāng)前工序，將第7步和第8步中的新成員加入O。

Step 10:如果O=Φ，結(jié)束，否則，從集合O中隨機(jī)選擇一個(gè)工序作為當(dāng)前工序，轉(zhuǎn)到Step 3。

3 性能測(cè)量

我們采用3種性能測(cè)量指標(biāo)對(duì)受影響工序重調(diào)度方法產(chǎn)生的新調(diào)度方案進(jìn)行評(píng)價(jià)，進(jìn)而評(píng)價(jià)此重調(diào)度方法的性能:新調(diào)度方案與原調(diào)度方案Makespan的變化率、各工序的開始加工時(shí)間偏移以及次序偏移。

（1）Makespan的變化率（Mp）

Makespan的變化率Mp定義如下:

式中:M0是原調(diào)度方案的Makespan，Mm是右移重調(diào)度方法產(chǎn)生的新調(diào)度方案的Makespan。

（2）開始時(shí)間偏移（devST）

這是對(duì)重調(diào)度方法效率的有效測(cè)量，特別是在輔助資源（如刀具和夾具）基于原調(diào)度方案運(yùn)送到機(jī)床的工件環(huán)境下。很顯然，如果材料比需求更早運(yùn)輸?shù)降脑?，工件開始時(shí)間的改變可能會(huì)招致存儲(chǔ)成本，如果刀具和材料的需求比原進(jìn)度表中計(jì)劃的時(shí)間更早，則會(huì)招致緊急訂貨成本。通過計(jì)算新調(diào)度方案和原調(diào)度方案之間工序結(jié)束時(shí)間差的絕對(duì)值的和，來計(jì)算開始時(shí)間的偏移，由兩部分組成:延誤=正的結(jié)束時(shí)間差的和，提前=負(fù)的結(jié)束時(shí)間差的絕對(duì)值的和

其中，n為工件數(shù)，hi為工件i的工序數(shù)。

（3）次序偏移（devSQ）

如果調(diào)整是基于機(jī)床上的初始工序序列提前準(zhǔn)備的，那么這個(gè)測(cè)量是很關(guān)鍵的，采用下面的方法對(duì)次序偏移進(jìn)行測(cè)量。

對(duì)新調(diào)度方案中每臺(tái)機(jī)床k上的每道工序j，定義:S1=原調(diào)度方案中在工序j前加工的工序集合，S2=新調(diào)度方案中在工序j后加工的工序集合，S=S1∩s2，Njk=S的基數(shù)（集合的容量）。對(duì)機(jī)床k上的每道工序j，獲得次序偏移，然后對(duì)所有機(jī)床上的偏移求和，求得次序偏移。

對(duì)于受影響工序重調(diào)度方法，Makespan的變化率、開始時(shí)間偏移比較小，因?yàn)樗粚?duì)受影響的剩余工序進(jìn)行重調(diào)度，同時(shí)它也沒有次序偏移。

4 測(cè)試實(shí)例

我們以 Muth和 Thompson［9］提出的著名6×6標(biāo)準(zhǔn)檢測(cè)問題（FT06）來進(jìn)行測(cè)試，首先利用生物智能計(jì)算方法求得原調(diào)度方案，原調(diào)度方案的最優(yōu)解Makespan等于55個(gè)時(shí)間單位，甘特圖見圖3。

生產(chǎn)中發(fā)生的多數(shù)擾動(dòng)事件可以映射為機(jī)床發(fā)生故障，現(xiàn)在對(duì)機(jī)床發(fā)生故障擾動(dòng)事件進(jìn)行測(cè)試。假設(shè)圖3所表示的原調(diào)度方案在執(zhí)行過程中，機(jī)床M3在時(shí)刻25發(fā)生故障，故障持續(xù)時(shí)間為5個(gè)時(shí)間單位。

受影響工序重調(diào)度方法產(chǎn)生的新的調(diào)度方案的甘特圖見圖4。新調(diào)度方案中，中斷前已調(diào)度工序的加工不變，只是將原調(diào)度方案中中斷發(fā)生時(shí)刻之后受中斷影響的工序進(jìn)行重調(diào)度。根據(jù)算法判斷各道工序新的起始加工時(shí)間和結(jié)束時(shí)間，新調(diào)度方案的Makespan等于60個(gè)時(shí)間單位。比較圖3和4，可以看出，在機(jī)床M1和M2上，剩余工序沒有受到影響;機(jī)床M3上，工件J4、J6;機(jī)床 M4上，工件 J4、J1，機(jī)床 M5上，工件J4、J3、J6、J1，機(jī)床 M6 上，J1、J4 這些工件相應(yīng)的剩余工序受到影響，工序有新的開始加工時(shí)間和結(jié)束時(shí)間。受影響工序重調(diào)度產(chǎn)生的新調(diào)度方案與原調(diào)度方案中，Mapespan的變化率為9.1%，開始時(shí)間偏移為43個(gè)時(shí)間單位，工件各工序的加工順序不變，沒有次序偏移。

5 結(jié)語

生產(chǎn)調(diào)度方案在車間的加工過程中會(huì)受到各種隨機(jī)擾動(dòng)的影響，因此重新調(diào)度，產(chǎn)生新的調(diào)度方案響應(yīng)隨機(jī)擾動(dòng)對(duì)實(shí)際生產(chǎn)有著很好的指導(dǎo)意義。本文對(duì)響應(yīng)隨機(jī)擾動(dòng)的受影響工序重調(diào)度方法進(jìn)行了研究，給出了此重調(diào)度方法的原理和算法過程，同時(shí)研究了評(píng)價(jià)重調(diào)度方法的性能指標(biāo)，并對(duì)一案例進(jìn)行了測(cè)試分析，結(jié)果表明所提出的重調(diào)度方法能產(chǎn)生優(yōu)化的新調(diào)度方案響應(yīng)擾動(dòng)。

［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］王志亮，汪惠芬，張友良.動(dòng)態(tài)Job Shop調(diào)度問題的一種自適應(yīng)遺傳算法［J］.中國(guó)機(jī)械工程，2004，15（11）:995 －999.

［7］舒海生，趙剛，趙丹，等.考慮刀具流的Job Shop動(dòng)態(tài)調(diào)度的研究［J］.制造技術(shù)與機(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］周亞勤，李蓓智，楊建國(guó).考慮批量和輔助時(shí)間等生產(chǎn)工況的智能調(diào)度方法［J］.機(jī)械工程學(xué)報(bào)，2006，42（1）:57 －61.