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

宋存利

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

0 引言

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

1 問題描述及建模

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

n：待加工工件的個數

m：加工設備的數量

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

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

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

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

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

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

為了討論問題方便，在調度序列π之前插入了一個虛擬工件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)的取值確定了一個調度序列，式(2)為本問題的目標函數；式(3)提供了每個工件的完工時間計算方式；式(4)約定了每個工件的后一道工序必須在其前一道工序完工后立即加工，即實現無等待；式(5)約定了在一個調度序列中，每個工件只能有一個直接前驅工件；式(6)～(8)約定一個給定調度工件的直接前驅關系；式(9)說明每個工件的最早開工時間為0；式(10)約定每個工件的完工時間必須小于交貨期；式(11)描述兩相鄰工件的最小完工時間距離[3]，即工件Jk在工件Ji緊后加工，則工件Jk最快在工件Ji完工之后過Di,k時間完工.目標函數的計算如式(12)所示：

(12)

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

(13)

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

2.1 圖形化表示

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

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

圖1 由4個工件形成的有向無環圖

圖2 加工路徑實例

2.2 問題性質特點

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

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

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

2.3 搜索算法描述

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

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

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

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

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

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

步驟6：在第j列中，從第i行開始探測沒有在部分序列P中的結點，假如發現的第一個結點為Vi,j，則該結點進入部分調度序列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，轉步驟6，否則轉步驟4.如果沒有發現滿足條件的結點，則刪除P中的最后一個結點，轉步驟 5.

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

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

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

3 仿真實驗及分析

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

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

設備 J1J2J3J4J5J6J7M141532858287321M265402642537571M33988367203531M4123998898570M54245872579090T644759558644759558558

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

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

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

表3 帶有交貨期約束的無等待流水調度問題調度結果

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

表4 基 于 SISA-ESA算法的帶有交貨期約束的大規模無等待流水調度問題實驗結果

4 結論

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