宋存利

( 大連交通大學 軟件學院, 遼寧 大連 116028)*

0 引言

無等待流水車間調(diào)度問題是一種典型的生產(chǎn)車間調(diào)度問題，在煉鋼、食品生產(chǎn)、化工、機械等行業(yè)有廣泛的應用背景.用Graham等人[1]的三參數(shù)表示法表示該問題為F|nwt|Cmax.文獻[2]已經(jīng)證明在設備數(shù)量大于等于3時為NP難題.針對此問題大量的學者對其進行了研究.宋存利等[3]在總結(jié)該問題特性的基礎上，提出了求解大規(guī)模無等待流水車間的迭代鄰域搜索算法；潘全科等[4]提出了一種通過延長工序加工時間進一步改進調(diào)度方案的離散的粒子群算法；Aldowaisan等[5]提出了一種高效的模擬退火和遺傳算法；Ventura[6]提出了禁忌搜索算法.以最小化總流水時間為研究目標的文獻有：Sapkal等[7]提出了一種啟發(fā)式算法，該算法以工件在瓶頸設備上的加工時間和來初始化初始解，實驗證明該算法的有效性.文獻[8]提出了一種遺傳算法，文獻[9]提了模擬退火算法，文獻[10]提出人工免疫系統(tǒng).以上這些文獻的共同點是都沒有考慮工件的交貨期.文獻[11-13]考慮了車間調(diào)度問題的交貨期限，但是以最小的提前或延遲代價為目標，也就是說交貨期不是嚴格的約束，允許以最小代價超出交貨期限.而以嚴禁拖期交付且最小化完工時間為目標的文獻鮮見相關(guān)報道.基于此，本文研究了禁止拖期交付的無等待流水車間調(diào)度問題，研究目標是在滿足約束條件的基礎上使得加工時間makespan達到最小，提出了求解該問題的基于有向圖搜索的精確算法ESA和基于ESA的分段迭代搜索算法SISA-ESA.

1 問題描述及建模

禁止拖期交付的無等待流水車間調(diào)度(no-wait flow shop scheduling即NWFS)問題可表示為F|nwt,Ti|Cmax，也就是n個帶有嚴格交貨日期的工件在m臺設備上加工，每個工件在每臺設備上都有相應的加工工序及加工時間要求，且每個工件流經(jīng)設備的加工順序相同.一個工件一旦進入到加工流程，必須保證從第一道工序到最后一道工序連續(xù)加工，中間不能停頓，不能被搶占.一臺設備在同一時間只能加工一個工件，并且每一個工件都必須在交貨期前完成加工.本文要研究的目標是尋找一個調(diào)度序列π，使得所有工件都在其交貨期內(nèi)完工且完工時間makespan達到最小化.為方便問題描述，定義數(shù)學符號如下：

n：待加工工件的個數(shù)

m：加工設備的數(shù)量

Ji：代表第i個工件，i為工件序號

Ti：代表工件Ji的交貨期限

Ci：代表工件Ji的完工時間

Si,j：代表工件Ji在設備Mj的加工開始時間

Pi,j：代表工件Ji在設備Mj上的加工時間

Di,k：當工件Ji的直接后繼加工工件是Jk時，工件Jk與工件Ji的最小完工時間距離差.

為了討論問題方便，在調(diào)度序列π之前插入了一個虛擬工件J0.

定義決策變量Xi,j：

(1)

問題目標：

Cmax=min{max{Ci|i=1,2,…,n}}

(2)

s.t.

Ci=Si,m+Pi,m

(3)

Si,j+1=Si,j+Pi,j

(4)

(5)

Xi,k+Xk,i≤1, 其中i,k=1,2,…,n

(6)

(7)

Xi,i=0, 其中i=0,1,2,…,n

(8)

Si,1≥0

(9)

Ci≤Ti

(10)

(11)[3]

對上述公式的解釋如下：式(1)的取值確定了一個調(diào)度序列，式(2)為本問題的目標函數(shù)；式(3)提供了每個工件的完工時間計算方式；式(4)約定了每個工件的后一道工序必須在其前一道工序完工后立即加工，即實現(xiàn)無等待；式(5)約定了在一個調(diào)度序列中，每個工件只能有一個直接前驅(qū)工件；式(6)～(8)約定一個給定調(diào)度工件的直接前驅(qū)關(guān)系；式(9)說明每個工件的最早開工時間為0；式(10)約定每個工件的完工時間必須小于交貨期；式(11)描述兩相鄰工件的最小完工時間距離[3]，即工件Jk在工件Ji緊后加工，則工件Jk最快在工件Ji完工之后過Di,k時間完工.目標函數(shù)的計算如式(12)所示：

(12)

根據(jù)式(11)，由于兩工件的最小完工時間距離和兩對應工件的加工時間有關(guān)，因此可事先計算出來，形成最小完工時間距離矩陣D.

(13)

2 問題的圖形化表示及搜索算法

2.1 圖形化表示

定義NWFS的有向無環(huán)圖G={V,E}，其中V代表結(jié)點，在圖G中共有n×n+1個結(jié)點，每個結(jié)點對應一個工件，圖G的結(jié)點共有n+1列，除第0列只有一個虛擬結(jié)點0外，其他n列每列都有n個結(jié)點，用工件J1,J2,…,Jn表示.E代表兩結(jié)點之間的一條有向邊.第0列虛擬結(jié)點J0到第一列的每個結(jié)點共發(fā)出n條有向邊.第1列到第n-1列節(jié)點只向下一列不同節(jié)點發(fā)出有向邊，因此每個節(jié)點發(fā)出n-1條有向邊，最后一列節(jié)點不發(fā)出有向邊，邊的權(quán)值為Di,j.問題的實質(zhì)就是從有向圖G中找到一條從虛擬結(jié)點出發(fā)，經(jīng)過每列一個結(jié)點且僅一個，且經(jīng)過不同列上的的結(jié)點編號不能相同的一條最短路徑.

具體以4工件的加工為例，形成的有向無環(huán)圖共有5列結(jié)點，第0列只有虛擬結(jié)點J0，第1列到第4列每列都有4個結(jié)點，依次為(J1,J2,…,J4)，如圖1所示，圖2為其中一條加工路徑實例.

圖1 由4個工件形成的有向無環(huán)圖

圖2 加工路徑實例

2.2 問題性質(zhì)特點

性質(zhì)1：在F/nwt,Ti/Cmax問題，對任意一個工件Ji，其最早的完工時間為Ci=D0,i，若其最早完工時間D0,i>Ti，則此調(diào)度任務無解.證明略.

性質(zhì)2：根據(jù)文獻[4]主動調(diào)度的概念，F(xiàn)/nwt,Ti/Cmax問題的優(yōu)化解一定是一個主動調(diào)度，因此若給定一個主動調(diào)度，他包括的調(diào)度序列有(Ji,…,Jk,…,Jq,…)，則一定有Di,k

性質(zhì)3：在F/nwt,Ti/Cmax問題中，給定一個滿足交貨期要求的部分調(diào)度π′，若將工件Jk安排在π′之后加工時，有Ck>Tk，即不滿足Jk的交貨期約束，則工件Jk在部分調(diào)度π′的其他任何一個后續(xù)位置進行加工都會有Ck>Tk成立；則在圖G中沒有必要繼續(xù)沿著π′這條路探索下去.證明略.

2.3 搜索算法描述

針對圖G，提出精確搜索算法(ESA)如下：

步驟1：計算工件之間的最小完工時間距離矩陣D.

步驟2：定義數(shù)組A[n]，用來記錄每一列結(jié)點的探測位置.其初始值為1，定義變量j為當前要探測的列號，令j=1，定義變量i，令i=1，代表第j列第一個結(jié)點的位置，定義部分調(diào)度序列P={0}；定義變量num，令num=1定義，代表部分調(diào)度P的結(jié)點的個數(shù)；Cmax為最小化的最大完工時間，令Cmax=M，M無限大，定義Pbest為最好的調(diào)度，初始值為φ.

步驟3：首先從虛擬結(jié)點0出發(fā)，分別訪問第一列中的所有結(jié)點Vi,1，計算每個結(jié)點的完工時間Ci=D0,i，若存在結(jié)點Vi,1，其完工時間Ci>Ti，則根據(jù)性質(zhì)1，此問題無可行解，算法終止.否則結(jié)點V1,1進入到調(diào)度序列P中，P={0,V1,1}，num=num+1，A(j)=1，j=j+1，i=1，轉(zhuǎn)步驟4.

步驟4：從位置i探測第j列中還沒有進入到部分調(diào)度P中的所有結(jié)點Vi,j，計算結(jié)點Vi,j的完工時間，若存在CVi,j>TVi,j或CVi,j>Cmax，則根據(jù)性質(zhì)3和性質(zhì)2，放棄后續(xù)探測，刪除部分調(diào)度P中的最后一個結(jié)點Pnum，轉(zhuǎn)步驟5，否則，轉(zhuǎn)步驟6.

步驟5：令num=num-1，j=j-1，i=A(j)+1，判斷num≥0是否成立，成立則判斷i是否大于n，是則轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟6；否則說明num小于0，則轉(zhuǎn)步驟7.

步驟6：在第j列中，從第i行開始探測沒有在部分序列P中的結(jié)點，假如發(fā)現(xiàn)的第一個結(jié)點為Vi,j，則該結(jié)點進入部分調(diào)度序列P中，同時令A(j)=i，num=num+1，j=j+1，i=1，如果 num=num+1， 則令Pbest=Pi，Cmax=Cpinum，同時令 num=num-2，j=j-2，i=A(j)+1，轉(zhuǎn)步驟6，否則轉(zhuǎn)步驟4.如果沒有發(fā)現(xiàn)滿足條件的結(jié)點，則刪除P中的最后一個結(jié)點，轉(zhuǎn)步驟 5.

步驟7： 若Pbest不為空，則輸出結(jié)果Pbest和Cmax，否則無解.

2.4 基于精確搜索的分段迭代搜索算法(SISA-ESA)

考慮到大規(guī)模的F|nwt,Ti|Cmax問題，ESA的CPU運行時間將不可忍受，因此提出一種基于ESA的鄰域迭代搜索算法SISA-ESA.算法思想是，對工件按照其交貨日期由小到大排成隊列Line，隨機選擇分段長短L，其中8≤L≤11，對隊列Line按長度L依次分段，對每段工件依次采用ESA算法搜索滿足工期約束的最短路徑，若第一段出現(xiàn)不能滿足工期約束的最短路徑，則算法結(jié)束，輸出無解.否則，按照最短路徑調(diào)整該分段的工件排序.對其他后續(xù)分段，在其前一分段調(diào)度結(jié)果的基礎上分別執(zhí)行ESA并相應調(diào)整期排序順序.若出現(xiàn)某一工件在相應分段無法滿足其工期要求，則將其插入到前面分段的最后一個工件之前做判斷，若不滿足交貨期，繼續(xù)前移，直到滿足條件或最終輸出無解.迭代該算法，直到滿足迭代終止條件為止.

3 仿真實驗及分析

為了說明算法的有效性，本文算法使用VC++編寫，計算機內(nèi)存為2GB，處理器為Q8400M2.66GHz，操作系統(tǒng)采用WIN7.本文首先對文獻[3]的案例進行ESA算法實驗，即7個工件在5臺設備上的無等待流水車間調(diào)度問題，相應的工件的加工時間及交貨日期(交貨期轉(zhuǎn)換成了具體的單位加工工時)如表1所示.表2中，EF代表對已知交貨日期的放大倍數(shù)，共設置了6組不同的放大倍數(shù)，RT代表算法ESA的運行時間，P為對應的調(diào)度序列，Cmax為最小化的最大完工時間.實驗結(jié)果見表2所示.

表17個工件在5臺設備上的加工時間表

設備 J1J2J3J4J5J6J7M141532858287321M265402642537571M33988367203531M4123998898570M54245872579090T644759558644759558558

表2 帶有不同交貨期約束的

從結(jié)果可以看出，當已知的交貨日期縮小到0.8倍時，則問題不存在滿足交貨日期的可行解，實驗2、實驗3和實驗4的結(jié)果可看出隨著交貨日期約束的放松，ESA的尋優(yōu)結(jié)果越來越好.當放大到一定值后，ESA找到的是該問題的全局最優(yōu)解，如實驗4-6.對于該問題，當EF=1.2時，每個工件的交貨日期均大于全局最優(yōu)解，所以肯定能找到問題的全局最優(yōu)解了.

表3中的實驗數(shù)據(jù)取自國際benchmark案例，當m=5時，取REC01前n個工件的加工數(shù)據(jù)；m=10時，取REC07的前n個工件的加工數(shù)據(jù)；m=20時，取REC37的前n個工件的加工數(shù)據(jù).

表3 帶有交貨期約束的無等待流水調(diào)度問題調(diào)度結(jié)果

表4以國際benchmark的無等待流水調(diào)度問題為例，交貨日期生成方式和表3采用同一種算法.為了說明本文算法的有效性，又由于以嚴禁拖期為目標的算法還沒發(fā)現(xiàn)，因此采用PSO[4]算法和GA[12]算法的運行結(jié)果與本文算法進行比較，在此將PSO與GA算法的目標函數(shù)改為滿足交貨期約束工件個數(shù)最大為目標，算法參數(shù)采用文獻自身參數(shù)設置.同時設置SISA-ESA的最大迭代代數(shù)為100.從表4的實驗結(jié)果可看出，本文算法效率較高，并且尋優(yōu)結(jié)果相比文獻PSO和GA較好，而且16個算例全部獲得合法解.PSO算法對16個案例的尋優(yōu)結(jié)果中只有10個案例找到了完全滿足工期約束的調(diào)度結(jié)果，其余6個案例都存在有工件工期不能滿足的情況，并且當問題規(guī)模變大，工期約束較多時，算法相對不是很理想.GA算法中有9個調(diào)度結(jié)果出現(xiàn)超期現(xiàn)象，7個合格，同PSO效果相當，交貨期約束增多時算法結(jié)果均不理想.因此通過實驗，本文算法在解決具有嚴格工期約束的無等待調(diào)度問題具有很好的優(yōu)勢，值得推薦.

表4 基 于 SISA-ESA算法的帶有交貨期約束的大規(guī)模無等待流水調(diào)度問題實驗結(jié)果

4 結(jié)論

針對帶有交貨日期約束的無等待流水調(diào)度問題，本文提出一種基于圖形搜索的精確求解算法，但此算法在需調(diào)度工件≤14時能夠在有限的時間內(nèi)給出問題的精確解，當問題規(guī)模增加，搜索的解空間急劇增大，算法效率將不能容忍.針對此種情況，本文在原有算法基礎上又提出了基于精確搜索算法的分段迭代搜索算法(SISA-ESA)，并將實驗結(jié)果和其他算法實驗結(jié)果進行比較.結(jié)果證明本文算法性能較好，能在較短的時間內(nèi)搜索到滿足交貨期約束的較好解.未來需要進一步研究分段大小及分段策略對算法求解結(jié)果的影響，以便對大規(guī)模問題，也能在合理時間內(nèi)求出精確解.