并行多機開放車間調度問題的模型與算法

陳亞絨 黃佩鈺 李 沛 周富得 黃沈權

溫州大學機電工程學院，溫州，325035

0 引言

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

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

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

1 晶粒分類揀選工序的調度問題描述

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

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

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

2 晶粒分類揀選調度問題的混合整數規劃模型

針對晶粒分類揀選工序的并行多機、加工工序沒有先后限制的生產特性，構建了求解此類調度問題的混合整數規劃(mixed integer programming，MIP)模型。

晶粒分類揀選工序調度問題MIP模型的目標是最小化所有工件的總加權完工時間。

最小化總加權完工時間為

(1)

式中，wj為工件j的權重系數；Fj為工件j的完工時間；n為晶圓或工件數量。

約束條件如下：

(1)每個工件在各個道次間執行的先后順序關系為

(2)

(3)

(2)一個工件的一個道次中只允許在該道次的多臺并行機臺中的一臺機器上加工，即有

(4)

(5)

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

(6)

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

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

Fj≥Cjk

(7)

(5)每個工件在任意兩個道次間的完工時間必須滿足先后順序關系，該先后順序關系的數學表述為

(8)

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

(6)任意兩個工件在同一道次的同一臺機器上加工時，必定有先后順序的關系；反之，則沒有先后順序的關系，該先后順序關系的數學表述為

(9)

(10)

(7)任意兩個工件在同一道次的同一臺機器上同時加工，兩個工件之間的完工時間必須滿足先后順序關系，該先后順序關系的數學表述為

(11)

晶粒分類揀選工序的生產調度問題屬于NP-hard問題，建立的MIP模型主要用于驗證后續設計的啟發式算法與改進粒子群優化算法結果的正確性，并將MIP模型求得的解作為評估調度算法求解質量的基準。

3 晶粒分類揀選調度問題的啟發式算法

盡管MIP模型可以求解晶粒分類揀選工序的生產調度問題，但當工件數量或晶粒分類揀選機器的數量急劇擴大時，MIP模型無法在可接受的時間內獲得最優解，甚至無法獲得任何一組可行解。考慮求解效率與現實運作要求，有必要設計迅速且有效獲得滿意可行調度解的啟發式算法。

本文提出的啟發式算法將整個求解過程細分成多個階段，每個階段只針對一臺晶粒分類揀選機器與一個工件進行指派。階段與階段之間相互關聯，即k+1階段的求解是在k階段獲得的可行解基礎上進行的，具體執行步驟如下：

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

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

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

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

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

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

(6)若尚有工件未指派處理完成，則返回執行步驟(1)；否則計算目標函數值，結束啟發式算法。

晶粒分類揀選機器的優先處理規則是“未來剩余工件的平均負荷大者優先指派”。若晶粒分類揀選機器的平均負荷相同，則機器序號小者優先。工件的優先處理規則是“pj/wj小者優先指派”。若某道次工序當中的pj/wj相同，則工件序號小者優先指派。

4 晶粒分類揀選調度問題的改進粒子群優化算法

改進粒子群優化(modified particle swarm optimization，MPSO) 算法的基本概念與傳統PSO相同，只在運行機制上進行了改進。

4.1 編碼

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

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

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

(3)若粒子的離散空間域編碼重復，則基于粒子多樣性的需求，運用隨機數重新產生一個粒子來取代此粒子。

4.2 解碼

4.3 算法運行機制

MPSO算法運行機制的偽代碼如下。

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// 計算粒子群內每一個粒子的位置Pi(t)

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

Pi(t)=Xi(t)

End if

Nexti

best= 1，worst= 1 //找出當前粒子群中最好與最差的位置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 // 淘汰群內最差的粒子

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// 更新每一個粒子的速度與位置

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算法與傳統PSO算法的不同之處如下：

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

(2)執行一次迭代后，為了增加群體多樣性，將當前目標函數值最差的粒子淘汰，然后隨機產生一個新的粒子來替代。

(3)為了增加搜索的有效性，假使當前目標函數值最好的粒子改變時，借由兩兩對調局部搜索(pairwise interchange local search)機制來加以輔助運行，改善搜索的有效性。

5 仿真實驗與分析

5.1 實驗數據生成

5.2 實驗結果分析

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

5.2.1各種實驗參數之下四種算法的績效比較

通過初步分析實驗結果發現，當工件數量n處于一定范圍時，算法的績效相似，因此將其分成3個區間進行分析。MIP法、啟發式算法、MPSO算法與傳統PSO算法在各種實驗參數之下的績效如表1所示。績效用解目標值R與運行時間T表示。工件數量n增大時，MIP法無法在最大可接受時間內獲得最優解，其解目標值細分為BU與BL。

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

5.2.2求解質量分析

不同加工處理作業時間pjk、k次工序所配備的機器數量mk、工件數量n以及工件的釋放時間rj等參數組合之下，啟發式算法、MPSO算法與傳統PSO算法的求解質量偏差PD如表2所示。

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

表2 不同參數組合下3種算法的求解質量偏差PD

注：括號里面的值代表PD為負值，表示該算法的解比MIP法在2 h可接受時間內獲得的最好解更接近最優解。

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

5.2.3實驗參數的影響分析

為比較實驗參數對啟發式算法、MPSO算法與傳統PSO算法的影響，統一將加工處理作業時間pjk(U[1,10]與U[1,20])、k道次工序所配備的機器數量mk(U[1,3]與U[1,5])以及工件的釋放時間rj(U[0,25]與U[0,75])的兩個水平取值分別標記為-1與-2。3種算法在pjk、mk與rj等參數不同取值之下的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可知，實驗參數pjk、mk與rj對啟發式算法PD的影響大于MPSO算法和傳統PSO算法。問題的規模n=11時，實驗參數的取值對MPSO算法和傳統PSO算法的PD幾乎沒影響，圖2～圖4中顯示為幾乎重合的數據點。根據PD的計算方法可知，若調度問題的復雜度或難度變高，MIP法很難在可接受的時間內獲得最優解，其他3種算法的BU的PD會變小，BL的PD會變大。因此，總體上實驗參數對算法的影響如下：pjk=U[1,20]的BU的PD優于pjk=U[1,10]的BU的PD，而pjk=U[1,20]的BL的PD劣于pjk=U[1,10]的BL的PD；mk=U[1,3]的BU的PD優于mk=U[1,5]的BU的PD，而mk=U[1,3]的BL的PD劣于mk=U[1,5]的BL的PD；rj=U[0,25]的BU的PD優于rj=U[0,75]的BU的PD，而rj=U[0,25]的BL的PD劣于rj=U[0,75]的BL的PD。需要注意的是，實驗參數對啟發式算法BU的PD的影響與MPSO算法和傳統PSO算法有所不同，在問題規模變大(n≥15)時發生了轉變。原因是實驗參數取值對啟發式算法求解質量的影響大于問題規模的影響。總之，當問題規模較大(n>11)時，3種實驗參數變化之下：MPSO算法的PD變化范圍小于傳統PSO算法，傳統PSO算法的PD變化范圍小于啟發式算法，這表明MPSO算法的穩健性最高。

6 結語

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