周亞勤 李蓓智 楊建國 楊 鵬

（東華大學機械工程學院，上海201620）

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

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

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

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

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

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

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

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

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

2.1 符號設(shè)定

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

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

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

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

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

nom為機床上的下一工序（機床分枝）。

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

mST為工序的開始加工時間，受機床上前道工序的約束。

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

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

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

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

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

readyTime為機床可用于加工的時間。

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，首先判斷第一個受影響的工序O［1］，擾動（機床發(fā)生故障）對原調(diào)度方案的影響有3種情況，見圖2。在圖2中，機床M3在時刻t發(fā)生故障，故障持續(xù)時間為r，由此，可以得出O［1］屬于下面3種情況之一:

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

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

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

Step 2:將O［1］作為當前工序，它的mST等于停機機床的readyTime，g加1。

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

當前工序的newET=當前工序的newST+當前工序的加工時間

Step 4:如果當前工序不能匹配到集合A中的任一受影響的工序v，那么轉(zhuǎn)到Step 5，否則，重新設(shè)置A［v］的屬性如下，然后轉(zhuǎn)到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:設(shè)置第i個受影響的工序A［i］=當前工序，i加1。

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

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

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

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

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

3 性能測量

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

（1）Makespan的變化率（Mp）

Makespan的變化率Mp定義如下:

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

（2）開始時間偏移（devST）

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

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

（3）次序偏移（devSQ）

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

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

對于受影響工序重調(diào)度方法，Makespan的變化率、開始時間偏移比較小，因為它只對受影響的剩余工序進行重調(diào)度，同時它也沒有次序偏移。

4 測試實例

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

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

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

5 結(jié)語

生產(chǎn)調(diào)度方案在車間的加工過程中會受到各種隨機擾動的影響，因此重新調(diào)度，產(chǎn)生新的調(diào)度方案響應(yīng)隨機擾動對實際生產(chǎn)有著很好的指導(dǎo)意義。本文對響應(yīng)隨機擾動的受影響工序重調(diào)度方法進行了研究，給出了此重調(diào)度方法的原理和算法過程，同時研究了評價重調(diào)度方法的性能指標，并對一案例進行了測試分析，結(jié)果表明所提出的重調(diào)度方法能產(chǎn)生優(yōu)化的新調(diào)度方案響應(yī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］王志亮，汪惠芬，張友良.動態(tài)Job Shop調(diào)度問題的一種自適應(yīng)遺傳算法［J］.中國機械工程，2004，15（11）:995 －999.

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