宋存利

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

0 引言

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

1 問(wèn)題描述及建模

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

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

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

Ji：代表第i個(gè)工件，i為工件序號(hào)

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

Ci：代表工件Ji的完工時(shí)間

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

Pi,j：代表工件Ji在設(shè)備Mj上的加工時(shí)間

Di,k：當(dāng)工件Ji的直接后繼加工工件是Jk時(shí)，工件Jk與工件Ji的最小完工時(shí)間距離差.

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

定義決策變量Xi,j：

(1)

問(wèn)題目標(biāo)：

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]

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

(12)

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

(13)

2 問(wèn)題的圖形化表示及搜索算法

2.1 圖形化表示

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

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

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

圖2 加工路徑實(shí)例

2.2 問(wèn)題性質(zhì)特點(diǎn)

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

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

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

2.3 搜索算法描述

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

步驟1：計(jì)算工件之間的最小完工時(shí)間距離矩陣D.

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

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

步驟4：從位置i探測(cè)第j列中還沒(méi)有進(jìn)入到部分調(diào)度P中的所有結(jié)點(diǎn)Vi,j，計(jì)算結(jié)點(diǎn)Vi,j的完工時(shí)間，若存在CVi,j>TVi,j或CVi,j>Cmax，則根據(jù)性質(zhì)3和性質(zhì)2，放棄后續(xù)探測(cè)，刪除部分調(diào)度P中的最后一個(gè)結(jié)點(diǎn)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；否則說(shuō)明num小于0，則轉(zhuǎn)步驟7.

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

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

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

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

3 仿真實(shí)驗(yàn)及分析

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

表17個(gè)工件在5臺(tái)設(shè)備上的加工時(shí)間表

設(shè)備 J1J2J3J4J5J6J7M141532858287321M265402642537571M33988367203531M4123998898570M54245872579090T644759558644759558558

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

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

表3中的實(shí)驗(yàn)數(shù)據(jù)取自國(guó)際benchmark案例，當(dāng)m=5時(shí)，取REC01前n個(gè)工件的加工數(shù)據(jù)；m=10時(shí)，取REC07的前n個(gè)工件的加工數(shù)據(jù)；m=20時(shí)，取REC37的前n個(gè)工件的加工數(shù)據(jù).

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

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

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

4 結(jié)論

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