并行多機(jī)開放車間調(diào)度問題的模型與算法

陳亞絨 黃佩鈺 李 沛 周富得 黃沈權(quán)

溫州大學(xué)機(jī)電工程學(xué)院，溫州，325035

0 引言

開放車間調(diào)度問題(open shop scheduling problem，OSSP)一般描述為將有限集合J={j1，j2，…，jn}中的n個(gè)工件安排在車間的s個(gè)階段(或道次)的機(jī)器上加工，k階段機(jī)器的數(shù)量為mk(k=1，2，…，s)。每個(gè)工件都包含s道工序，每道工序在每臺(tái)機(jī)器上的加工時(shí)間確定。在給定的時(shí)間內(nèi)，每臺(tái)機(jī)器只能加工一個(gè)工件，且每個(gè)工件只能由一臺(tái)機(jī)器加工。同一臺(tái)機(jī)器上工件的加工順序任意，每個(gè)工件的加工順序也無限制。若k階段機(jī)器的數(shù)量mk=1，則這類調(diào)度問題稱為傳統(tǒng)開放車間調(diào)度問題；若mk≥1且s≥2，同時(shí)每個(gè)階段的機(jī)器為同類等效機(jī)，則此類問題稱為并行多機(jī)OSSP[1-3]。

晶粒分類揀選工序是發(fā)光二極管(light emitting diode，LED)制造過程中的關(guān)鍵工序，該工序的生產(chǎn)調(diào)度問題是典型的并行多機(jī)OSSP，其調(diào)度算法是否有效直接影響LED制造工廠的生產(chǎn)[4]。

開放車間調(diào)度問題具有NP-hard屬性[5]，因此許多學(xué)者開發(fā)啟發(fā)式算法[6-7]以及智能優(yōu)化算法如遺傳算法[8-10]、蟻群算法[11]與粒子群算法[12-13]，以期在較短的時(shí)間內(nèi)得到近似最優(yōu)解?？紤]到現(xiàn)實(shí)生產(chǎn)的動(dòng)態(tài)與隨機(jī)性，采用仿真方法的研究日益受到關(guān)注。如文獻(xiàn)[14]研究了一種基于仿真的實(shí)時(shí)調(diào)度方法，來優(yōu)化釋放時(shí)間隨機(jī)的非搶占開放車間調(diào)度問題。研究的調(diào)度目標(biāo)主要是最小化Makespan或總完工時(shí)間[7-8，10-12]、最小化平均流程時(shí)間[6]、最小化總拖期[9]。比較而言，有關(guān)并行多機(jī)OSSP的研究相對較少，BAI等[15]研究了基于GDS求解大規(guī)模OSSP的啟發(fā)式算法，以及求解中等規(guī)模OSSP的差分進(jìn)化算法；針對實(shí)際問題中工件批量大于1的需求，WANG等[16]提出了分割求解工件批量的并行多機(jī)OSSP的差分進(jìn)化算法；MATTA[17]提出了一種求解并行多機(jī)OSSP的計(jì)算機(jī)搜索方法；CHEN等[18]研究了每個(gè)階段兩臺(tái)機(jī)器的OSSP，提出了求解該問題的多項(xiàng)式時(shí)間近似算法。文獻(xiàn)[19]提出了一種基于網(wǎng)絡(luò)流求解并行多機(jī)可中斷OSSP的調(diào)度算法。這些文獻(xiàn)的調(diào)度目標(biāo)均是完工時(shí)間最小化。以當(dāng)前的研究文獻(xiàn)為基礎(chǔ)，結(jié)合晶粒分類揀選工序的生產(chǎn)特性分析，本文以最小化總加權(quán)完工時(shí)間為目標(biāo)，構(gòu)建了并行多機(jī)OSSP的混合整數(shù)規(guī)劃模型，設(shè)計(jì)了可以快速有效獲得較佳解的啟發(fā)式算法及改進(jìn)粒子群優(yōu)化算法，并通過實(shí)驗(yàn)仿真比較了不同算法的績效。

1 晶粒分類揀選工序的調(diào)度問題描述

調(diào)研LED制造工廠得知，根據(jù)客戶標(biāo)準(zhǔn)，晶圓片上的每一顆晶粒都可以歸類到128種晶粒等級中的一種。每一臺(tái)晶粒分類揀選設(shè)備/機(jī)臺(tái)最多只能分類32種等級的晶粒。已設(shè)定分類某些等級晶粒的設(shè)備更改為其他等級時(shí)，需耗費(fèi)8h的程序設(shè)定時(shí)間。實(shí)際生產(chǎn)過程中，管理者一般依照經(jīng)驗(yàn)將128種晶粒等級歸類成4～8群，每個(gè)群最多包含32種特定的晶粒等級；然后將若干臺(tái)分類揀選設(shè)備設(shè)定成專門分類揀選“專屬群”的晶粒等級。每一片晶圓都要?dú)v經(jīng)4道以上不同“專屬群”的加工工序(沒有先后限制)，每道工序的加工設(shè)備是多臺(tái)同類平行設(shè)備(圖1)，因此該調(diào)度問題是典型的并行多機(jī)開放車間調(diào)度問題O(Pm1，Pm2，…，Pms)/rj/Σwjcj。

圖1 晶粒分類揀選工序加工示意圖Fig.1 Schematic diagram of grain sorting process

根據(jù)上述的生產(chǎn)作業(yè)環(huán)境，本文探討的晶粒分類揀選工序生產(chǎn)調(diào)度問題描述如下：①磊晶工序之后的每一片晶圓都是一個(gè)獨(dú)立的工件；②經(jīng)過電性與旋光性針測工序，晶圓j上的晶粒等級、位置與數(shù)量確定且已知；③晶圓j釋放(或抵達(dá))到晶粒分類揀選工序的時(shí)間為rj；④晶圓j要經(jīng)過s道晶粒分類揀選設(shè)備的加工(沒有先后限制)，工序k包含mk臺(tái)同型設(shè)備；⑤每臺(tái)設(shè)備從晶圓片上揀選1顆晶粒所需的時(shí)間確定且已知；⑥每片晶圓在工序k上的作業(yè)時(shí)間等于這道工序設(shè)備揀選的晶粒總數(shù)量與揀選1顆晶粒所需時(shí)間的乘積；⑦每臺(tái)晶粒分類揀選設(shè)備一次最多只能分揀1片晶圓，且不允許搶占；⑧調(diào)度期間內(nèi)，不考慮晶粒分類揀選設(shè)備發(fā)生故障停機(jī)的情形；⑨晶圓j的經(jīng)營管理績效重要程度即權(quán)重確定且已知；⑩生產(chǎn)績效是最小化總加權(quán)完工時(shí)間。

2 晶粒分類揀選調(diào)度問題的混合整數(shù)規(guī)劃模型

針對晶粒分類揀選工序的并行多機(jī)、加工工序沒有先后限制的生產(chǎn)特性，構(gòu)建了求解此類調(diào)度問題的混合整數(shù)規(guī)劃(mixed integer programming，MIP)模型。

晶粒分類揀選工序調(diào)度問題MIP模型的目標(biāo)是最小化所有工件的總加權(quán)完工時(shí)間。

最小化總加權(quán)完工時(shí)間為

(1)

式中，wj為工件j的權(quán)重系數(shù)；Fj為工件j的完工時(shí)間；n為晶圓或工件數(shù)量。

約束條件如下：

(1)每個(gè)工件在各個(gè)道次間執(zhí)行的先后順序關(guān)系為

(2)

(3)

(2)一個(gè)工件的一個(gè)道次中只允許在該道次的多臺(tái)并行機(jī)臺(tái)中的一臺(tái)機(jī)器上加工，即有

(4)

(5)

(3)每個(gè)工件在每個(gè)道次中的完工時(shí)間必須不小于此工件的釋放時(shí)間與此道次加工時(shí)間之和，即

(6)

式中，Cjk為工件j在道次k的完工時(shí)間；rj為工件j的釋放時(shí)間；pjk為工件j在道次k的加工時(shí)間。

(4)每個(gè)工件最終的完工時(shí)間必須不小于此工件在每個(gè)道次的完工時(shí)間，即

Fj≥Cjk

(7)

(5)每個(gè)工件在任意兩個(gè)道次間的完工時(shí)間必須滿足先后順序關(guān)系，該先后順序關(guān)系的數(shù)學(xué)表述為

(8)

式中，M為很大的正整數(shù)；Cjl為工件l的工序完工時(shí)間。

(6)任意兩個(gè)工件在同一道次的同一臺(tái)機(jī)器上加工時(shí)，必定有先后順序的關(guān)系；反之，則沒有先后順序的關(guān)系，該先后順序關(guān)系的數(shù)學(xué)表述為

(9)

(10)

(7)任意兩個(gè)工件在同一道次的同一臺(tái)機(jī)器上同時(shí)加工，兩個(gè)工件之間的完工時(shí)間必須滿足先后順序關(guān)系，該先后順序關(guān)系的數(shù)學(xué)表述為

(11)

晶粒分類揀選工序的生產(chǎn)調(diào)度問題屬于NP-hard問題，建立的MIP模型主要用于驗(yàn)證后續(xù)設(shè)計(jì)的啟發(fā)式算法與改進(jìn)粒子群優(yōu)化算法結(jié)果的正確性，并將MIP模型求得的解作為評估調(diào)度算法求解質(zhì)量的基準(zhǔn)。

3 晶粒分類揀選調(diào)度問題的啟發(fā)式算法

盡管MIP模型可以求解晶粒分類揀選工序的生產(chǎn)調(diào)度問題，但當(dāng)工件數(shù)量或晶粒分類揀選機(jī)器的數(shù)量急劇擴(kuò)大時(shí)，MIP模型無法在可接受的時(shí)間內(nèi)獲得最優(yōu)解，甚至無法獲得任何一組可行解?？紤]求解效率與現(xiàn)實(shí)運(yùn)作要求，有必要設(shè)計(jì)迅速且有效獲得滿意可行調(diào)度解的啟發(fā)式算法。

本文提出的啟發(fā)式算法將整個(gè)求解過程細(xì)分成多個(gè)階段，每個(gè)階段只針對一臺(tái)晶粒分類揀選機(jī)器與一個(gè)工件進(jìn)行指派。階段與階段之間相互關(guān)聯(lián)，即k+1階段的求解是在k階段獲得的可行解基礎(chǔ)上進(jìn)行的，具體執(zhí)行步驟如下：

(0)令時(shí)間初始值t←0。

(1)從所有晶粒分類揀選機(jī)器中找出還有工件需要加工的機(jī)器，將每臺(tái)滿足機(jī)器可用時(shí)間ma≤t的晶粒分類揀選機(jī)器放到候選晶粒分類揀選機(jī)器集合。

(2)若候選晶粒分類揀選機(jī)器集合為空集，則令t←t+1，執(zhí)行步驟(1)；否則，根據(jù)晶粒分類揀選機(jī)器的優(yōu)先處理規(guī)則，從此候選晶粒分類揀選機(jī)器集合中選擇晶粒分類揀選機(jī)器。

(3)篩選所有還需要在步驟(2)選擇的晶粒分類揀選機(jī)器上加工處理的工件，將每個(gè)滿足工件釋放時(shí)間wr≤t的工件納入到候選工件集合之中。

(4)若候選工件集合為空集，則令t←t+1，執(zhí)行步驟(1)；否則，根據(jù)工件的優(yōu)先處理規(guī)則，從此候選工件集合中選擇工件。

(5)更新此階段晶粒分類揀選機(jī)器的可用時(shí)間ma、工件的釋放時(shí)間wr。

(6)若尚有工件未指派處理完成，則返回執(zhí)行步驟(1)；否則計(jì)算目標(biāo)函數(shù)值，結(jié)束啟發(fā)式算法。

晶粒分類揀選機(jī)器的優(yōu)先處理規(guī)則是“未來剩余工件的平均負(fù)荷大者優(yōu)先指派”。若晶粒分類揀選機(jī)器的平均負(fù)荷相同，則機(jī)器序號小者優(yōu)先。工件的優(yōu)先處理規(guī)則是“pj/wj小者優(yōu)先指派”。若某道次工序當(dāng)中的pj/wj相同，則工件序號小者優(yōu)先指派。

4 晶粒分類揀選調(diào)度問題的改進(jìn)粒子群優(yōu)化算法

改進(jìn)粒子群優(yōu)化(modified particle swarm optimization，MPSO) 算法的基本概念與傳統(tǒng)PSO相同，只在運(yùn)行機(jī)制上進(jìn)行了改進(jìn)。

4.1 編碼

傳統(tǒng)PSO算法主要適用于求解連續(xù)空間域的優(yōu)化問題。針對晶粒分類揀選調(diào)度問題的離散空間域組合優(yōu)化問題特征，本文采用隨機(jī)數(shù)大小順序值排列(rank order value，ROV)編碼方式，將連續(xù)空間域的粒子位置映像轉(zhuǎn)換為離散空間域的調(diào)度解粒子[20]。

(1)對每個(gè)粒子使用ROV方法，將連續(xù)空間域的粒子位置映像轉(zhuǎn)換成離散空間域編碼。

(2)針對經(jīng)過ROV映像轉(zhuǎn)換后的每個(gè)粒子，利用Hash函數(shù)來計(jì)算此粒子的類似索引碼，通過此數(shù)值來判斷2個(gè)粒子的離散空間域編碼是否重復(fù)。

(3)若粒子的離散空間域編碼重復(fù)，則基于粒子多樣性的需求，運(yùn)用隨機(jī)數(shù)重新產(chǎn)生一個(gè)粒子來取代此粒子。

4.2 解碼

4.3 算法運(yùn)行機(jī)制

MPSO算法運(yùn)行機(jī)制的偽代碼如下。

Initialize parameters ofNp，δ，c1，c2，reduce_rate，andtime_limit

Generate initial positionXi(0) and velocityVi(0) for particlei，?i=1,2,…,Np

SetPi(0)=Xi(0)，Gb(0)=X1(0)，Gw(0)=X1(0)，timer=0，t=0

Do

Fori=1 toNp// 計(jì)算粒子群內(nèi)每一個(gè)粒子的位置Pi(t)

IfZ(Xi(t))≤Z(Pi(t)) then

Pi(t)=Xi(t)

End if

Nexti

best= 1，worst= 1 //找出當(dāng)前粒子群中最好與最差的位置Gb(t)，Gw(t)

Fori=1 toNp

IfZ(Xi(t))≤Z(Pbest(t)) then

best=i

End if

IfZ(Xi(t))≥Z(Pworst(t)) then

worst=i

End if

Nexti

IfZ(Pbest(t))

Gb(t)= Pbest(t)

Local_search(Gb(t)) //兩兩交換局部搜尋

End if

IfZ(Pworst(t))>Z(Gw(t)) then // 淘汰群內(nèi)最差的粒子

Gw(t)=Pworst(t)

If random number≤threshold then

Generate a new particle randomly

ReplacePworst(t)，Xworst(t)，Vworst(t)

End if

End if

Fori=1 toNp// 更新每一個(gè)粒子的速度與位置

Vi(t+1)=δ·Vi(t)+c1·r1·(Pi(t)-Xi(t))+c2·r2·(Gb(t)-Xi(t))，Vi(t+1)∈[Vmin，Vmax],

Xi(t+1)=Xi(t)+Vi(t+1)，Xi(t+1)∈[Xmin，Xmax]

Nexti

Similarity check for a couple of particles

If similarity check is true，then

Generate a new particle randomly and replace one of the particles by the new one

End if

t=t+1，δ=δ×reduce_rate，δ∈[δmin，δmax]，updatetimer

While (timer≤time_limit)

除編碼與解碼之外，MPSO算法與傳統(tǒng)PSO算法的不同之處如下：

(1)用慣性權(quán)重來控制粒子群優(yōu)化搜索過程中整體探索與局部探索的比重。初期著重于整體性探索，慣性權(quán)重比較大；隨著運(yùn)行時(shí)間的增加，搜索偏重于局部性探索，則慣性權(quán)重逐步減小。

(2)執(zhí)行一次迭代后，為了增加群體多樣性，將當(dāng)前目標(biāo)函數(shù)值最差的粒子淘汰，然后隨機(jī)產(chǎn)生一個(gè)新的粒子來替代。

(3)為了增加搜索的有效性，假使當(dāng)前目標(biāo)函數(shù)值最好的粒子改變時(shí)，借由兩兩對調(diào)局部搜索(pairwise interchange local search)機(jī)制來加以輔助運(yùn)行，改善搜索的有效性。

5 仿真實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)數(shù)據(jù)生成

5.2 實(shí)驗(yàn)結(jié)果分析

采用求解質(zhì)量偏差百分比PD=(A-O)/O來評估不同算法的求解質(zhì)量，其中，A為算法求得的解，O為評估基準(zhǔn)值。當(dāng)工件數(shù)量較小時(shí)，O為MIP獲得的最優(yōu)解。當(dāng)工件數(shù)量較大時(shí)，MIP無法在2 h內(nèi)獲得最優(yōu)解，O為2 h內(nèi)取得的上界值BU與下界值BL，實(shí)際的PD在根據(jù)BU與BL計(jì)算得到的PD之間。

5.2.1各種實(shí)驗(yàn)參數(shù)之下四種算法的績效比較

通過初步分析實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，當(dāng)工件數(shù)量n處于一定范圍時(shí)，算法的績效相似，因此將其分成3個(gè)區(qū)間進(jìn)行分析。MIP法、啟發(fā)式算法、MPSO算法與傳統(tǒng)PSO算法在各種實(shí)驗(yàn)參數(shù)之下的績效如表1所示?？冃в媒饽繕?biāo)值R與運(yùn)行時(shí)間T表示。工件數(shù)量n增大時(shí)，MIP法無法在最大可接受時(shí)間內(nèi)獲得最優(yōu)解，其解目標(biāo)值細(xì)分為BU與BL。

由表1可知，對于pjk、mk、rj的不同組合，當(dāng)求解問題的規(guī)模較小(n≤5)時(shí)，MIP法、MPSO算法、傳統(tǒng)PSO算法與啟發(fā)式算法均能獲得問題的最優(yōu)解或近優(yōu)解。問題規(guī)模較大(5

5.2.2求解質(zhì)量分析

不同加工處理作業(yè)時(shí)間pjk、k次工序所配備的機(jī)器數(shù)量mk、工件數(shù)量n以及工件的釋放時(shí)間rj等參數(shù)組合之下，啟發(fā)式算法、MPSO算法與傳統(tǒng)PSO算法的求解質(zhì)量偏差PD如表2所示。

表1 4種算法在不同參數(shù)組合下的績效匯總表

表2 不同參數(shù)組合下3種算法的求解質(zhì)量偏差PD

注：括號里面的值代表PD為負(fù)值，表示該算法的解比MIP法在2 h可接受時(shí)間內(nèi)獲得的最好解更接近最優(yōu)解。

由表2所示的結(jié)果可知，MPSO算法、傳統(tǒng)PSO算法與啟發(fā)式算法的求解質(zhì)量偏差PD不僅與工件數(shù)量有關(guān)，也受pjk、mk與rj的影響。對于pjk、mk、rj的不同組合，隨著求解問題規(guī)模的變大，3種算法BU的求解質(zhì)量偏差PD基本呈現(xiàn)由小(PD=0)到大再到更小(PD<0)的趨勢，BL的PD呈現(xiàn)由小到大的變化趨勢。這表明當(dāng)求解問題的規(guī)模足夠大(n≥11)時(shí)，3種算法獲得的解優(yōu)于或接近在可接受時(shí)間內(nèi)MIP法獲得的最優(yōu)解，且求解問題的規(guī)模越大，求解質(zhì)量偏差PD的優(yōu)勢越明顯。其中，MPSO算法的求解質(zhì)量優(yōu)于傳統(tǒng)PSO算法，傳統(tǒng)PSO算法的求解質(zhì)量優(yōu)于啟發(fā)式算法。原因在于，求解問題規(guī)模的變大導(dǎo)致可行解空間的增大，進(jìn)而造成MIP法在最大可接受時(shí)間獲得的最好解與最優(yōu)解的偏差變大。

5.2.3實(shí)驗(yàn)參數(shù)的影響分析

為比較實(shí)驗(yàn)參數(shù)對啟發(fā)式算法、MPSO算法與傳統(tǒng)PSO算法的影響，統(tǒng)一將加工處理作業(yè)時(shí)間pjk(U[1,10]與U[1,20])、k道次工序所配備的機(jī)器數(shù)量mk(U[1,3]與U[1,5])以及工件的釋放時(shí)間rj(U[0,25]與U[0,75])的兩個(gè)水平取值分別標(biāo)記為-1與-2。3種算法在pjk、mk與rj等參數(shù)不同取值之下的PD如圖2～圖4所示。

圖2 pjk對3種算法PD影響Fig.2 Influence of pjk on PD of three algorithms

圖3 mk對3種算法PD影響Fig.3 Influence of mk on PD of three algorithms

圖4 rj對3種算法PD影響Fig.4 Influence of rj on PD of three algorithms

由圖2～圖4可知，實(shí)驗(yàn)參數(shù)pjk、mk與rj對啟發(fā)式算法PD的影響大于MPSO算法和傳統(tǒng)PSO算法。問題的規(guī)模n=11時(shí)，實(shí)驗(yàn)參數(shù)的取值對MPSO算法和傳統(tǒng)PSO算法的PD幾乎沒影響，圖2～圖4中顯示為幾乎重合的數(shù)據(jù)點(diǎn)。根據(jù)PD的計(jì)算方法可知，若調(diào)度問題的復(fù)雜度或難度變高，MIP法很難在可接受的時(shí)間內(nèi)獲得最優(yōu)解，其他3種算法的BU的PD會(huì)變小，BL的PD會(huì)變大。因此，總體上實(shí)驗(yàn)參數(shù)對算法的影響如下：pjk=U[1,20]的BU的PD優(yōu)于pjk=U[1,10]的BU的PD，而pjk=U[1,20]的BL的PD劣于pjk=U[1,10]的BL的PD；mk=U[1,3]的BU的PD優(yōu)于mk=U[1,5]的BU的PD，而mk=U[1,3]的BL的PD劣于mk=U[1,5]的BL的PD；rj=U[0,25]的BU的PD優(yōu)于rj=U[0,75]的BU的PD，而rj=U[0,25]的BL的PD劣于rj=U[0,75]的BL的PD。需要注意的是，實(shí)驗(yàn)參數(shù)對啟發(fā)式算法BU的PD的影響與MPSO算法和傳統(tǒng)PSO算法有所不同，在問題規(guī)模變大(n≥15)時(shí)發(fā)生了轉(zhuǎn)變。原因是實(shí)驗(yàn)參數(shù)取值對啟發(fā)式算法求解質(zhì)量的影響大于問題規(guī)模的影響。總之，當(dāng)問題規(guī)模較大(n>11)時(shí)，3種實(shí)驗(yàn)參數(shù)變化之下：MPSO算法的PD變化范圍小于傳統(tǒng)PSO算法，傳統(tǒng)PSO算法的PD變化范圍小于啟發(fā)式算法，這表明MPSO算法的穩(wěn)健性最高。

6 結(jié)語

本文針對LED制造工廠的晶粒分類揀選調(diào)度問題的并行多機(jī)生產(chǎn)特性，建立了求解此類調(diào)度問題的混合整數(shù)規(guī)劃模型，兼顧求解效率與質(zhì)量，設(shè)計(jì)了一種簡單易行的啟發(fā)式算法和一種改進(jìn)粒子群優(yōu)化算法。根據(jù)企業(yè)的生產(chǎn)實(shí)踐設(shè)計(jì)了實(shí)驗(yàn)算例，通過比較4種算法的調(diào)度績效，發(fā)現(xiàn)啟發(fā)式算法雖能快速求解，但是求解的質(zhì)量仍然有改善的空間，改進(jìn)粒子群優(yōu)化算法在求解速度與質(zhì)量的要求下均能滿足企業(yè)晶粒分類揀選調(diào)度的實(shí)務(wù)要求。同時(shí)，對于加工處理時(shí)間、釋放時(shí)間以及每一道次工序所配備的機(jī)器數(shù)量等參數(shù)的變化，改進(jìn)粒子群優(yōu)化算法的變化范圍最小、最穩(wěn)健。未來研究方向?qū)?cè)重于考慮將改進(jìn)粒子群優(yōu)化算法用于其他的調(diào)度問題，以及探討晶粒分類揀選工序的生產(chǎn)調(diào)度問題的多目標(biāo)優(yōu)化求解方法。