禁止拖期交付的無等待流水車間調(diào)度問題算法研究

宋存利

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

0 引言

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

1 問題描述及建模

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

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

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

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

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

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

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

Pi,j：代表工件Ji在設(shè)備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)，由于兩工件的最小完工時間距離和兩對應(yīng)工件的加工時間有關(guān)，因此可事先計算出來，形成最小完工時間距離矩陣D.

(13)

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

2.1 圖形化表示

定義NWFS的有向無環(huán)圖G={V,E}，其中V代表結(jié)點，在圖G中共有n×n+1個結(jié)點，每個結(jié)點對應(yīng)一個工件，圖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)度任務(wù)無解.證明略.

性質(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(yù)(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é)果的基礎(chǔ)上分別執(zhí)行ESA并相應(yīng)調(diào)整期排序順序.若出現(xiàn)某一工件在相應(yīng)分段無法滿足其工期要求，則將其插入到前面分段的最后一個工件之前做判斷，若不滿足交貨期，繼續(xù)前移，直到滿足條件或最終輸出無解.迭代該算法，直到滿足迭代終止條件為止.

3 仿真實驗及分析

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

表17個工件在5臺設(shè)備上的加工時間表

設(shè)備 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ù)設(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ī)模增加，搜索的解空間急劇增大，算法效率將不能容忍.針對此種情況，本文在原有算法基礎(chǔ)上又提出了基于精確搜索算法的分段迭代搜索算法(SISA-ESA)，并將實驗結(jié)果和其他算法實驗結(jié)果進行比較.結(jié)果證明本文算法性能較好，能在較短的時間內(nèi)搜索到滿足交貨期約束的較好解.未來需要進一步研究分段大小及分段策略對算法求解結(jié)果的影響，以便對大規(guī)模問題，也能在合理時間內(nèi)求出精確解.