帶多重加工前約束的單機MOPJ調度方法

周炳海， 王 科

(同濟大學 機械與能源工程學院， 上海 201804)

帶多重加工前約束的單機MOPJ調度方法

周炳海， 王 科

(同濟大學 機械與能源工程學院， 上海 201804)

為有效解決晶圓加工過程中帶換模時間、品種間晶舟分配的不確定性以及參數調整等多重加工前約束的單機單作業多訂單MOPJ(multi-order-per-job)調度問題,對問題域進行描述，以訂單總完成時間最小為優化目標，建立數學規劃模型. 給出求解較優調度解的定理，并提出具有雙層嵌套編碼機制的混合差分進化的入侵雜草調度算法，該算法引入具有學習機制的算子以改善解的質量. 為有效提高算法的收斂性，在變異及鄰域操作中考慮自適應過程. 仿真實驗結果表明，該算法是有效且可行的，優化晶舟分配的調度較未優化的調度可提高至少10%的性能.

單作業多訂單調度；差分進化；入侵雜草；自適應；晶舟分配

目前，已經有很多學者對單一產品、不考慮換模時間等因素的單機單作業多訂單(multi-order-per-job，MOPJ)問題提出了多種調度方法. 文獻[1]對單一產品且不考慮其他因素的理想化單機MOPJ調度模型采用禁忌搜索算法進行了簡單的研究. 文獻[2]對理想化單機MOPJ問題，提出了分組遺傳算法. 文獻[3]在理想化單機MOPJ調度模型的基礎上,增加了訂單準備時間因素，提出了列生成啟發式算法并對其進行有效求解. 文獻[4]針對理想化的單機MOPJ調度模型提出了啟發式算法,可以求解超大規模訂單的調度問題. 在單機MOPJ調度研究領域，文獻[5]和[6]在批調度(batch scheduling)模型中考慮了多個品種. 但批調度的研究重點是對批次的調度，與本文研究的調度問題有較大區別. 文獻[7]對多品種、考慮換模時間以及衰退效應約束的單機MOPJ調度問題進行了研究，但每個品種所使用的晶舟數量是確定的. 優化晶舟在每個品種間的分配可以明顯提高MOPJ調度的效率，具有實用性和研究價值，目前鮮有文獻對其進行研究.

參數調整是為保證某產品的加工質量，若設備連續加工其他產品超過一定閾值，則加工該產品前需要調整參數. 晶圓制造系統中，已不乏研究引入參數調整約束后的調度. 文獻[8]在多作業族的單機調度模型中考慮了參數調整約束，提出了簡單啟發式算法. 文獻[9]在多目標的并行機批調度問題中考慮了參數調整，并提出了蟻群優化算法. 在MOPJ調度問題中考慮參數調整以保證加工過程中的質量，具有實用性和普遍性，而目前鮮有文獻探討參數調整背景下的MOPJ調度問題.

本文研究的單機MOPJ調度問題以總加權完成時間最小為目標函數，同時考慮換模時間、參數調整、訂單品種多樣性等約束，優化訂單的分配，晶舟的加工順序以及晶舟在品種間的分配.

1 問題描述

以往研究單機MOPJ調度問題，主要包含訂單成組形成作業和作業排序兩個子問題. 如圖1所示，本文所研究的問題還需確定如何在每個品種間分配晶舟(為與調度術語一致，本文將用作業指代晶舟)，同時在作業排序時，考慮了參數調整.

圖1 單機MOPJ調度問題實例Fig.1 The instance of a single machine MOPJ scheduling problem

為有效地描述調度問題，在文獻[7]的基礎上，做如下假設：1)訂單需保持完整性； 2)每個訂單只含有一種產品，不同訂單的產品種類可以不同； 3)每個作業只含有同個品種的多個訂單； 4)每一個作業中載有的晶圓數不能超過其承載上限； 5)作業的數量能夠滿足調度要求； 6)不同品種的訂單形成的作業，屬于不同的作業族，即一個品種對應一個作業族； 7)設備連續加工不同作業族的兩個作業時考慮換模時間； 8)設備若超過一定次數未加工過某作業族，當加工該作業族的作業時需考慮參數調整時間； 9)設備一旦開始工作，除換模外，不會中斷工作；10)同一個作業中的所有訂單有相同的完工時間；11)訂單大小為0的訂單，稱為虛擬訂單，虛擬訂單在實際中不參與調度.

由假設1)和11)可知，一個客戶訂單只能分配到一個作業中，虛擬訂單不對應任何作業，即需滿足

由假設2)～4)可知，一個作業至少包含一個訂單，且作業的大小不得超出上限Q，即需同時滿足

j=1,2,…,J；

由假設2)、3)和6)可知，一個作業只能屬于一個作業族，訂單的品種與作業族相對應，即滿足

；

f=1,2,…,F， if=1,2,…,If.

由假設5)可知，所有的訂單都應該被分配到作業中，當作業總數為一定值時，各個品種的作業的數量需滿足調度要求，且參與調度的作業能被有效利用，即不同品種訂單形成的作業的數量需滿足

f=1,2,…,F；

在假設7)和文獻[8]的基礎上可知，設備前后連續加工不同作業族的兩個作業時需考慮換模，即需滿足

f=1,2,…,F.

在假設8)和文獻[8]的基礎上可知，設備若超過一定次數未加工過某作業族，當加工該作業族的作業時,需考慮參數調整時間，即需滿足

f=1,2,…,F.

由假設9)可知，只有當前一個作業完成加工后，后一個作業才能進行加工，即需滿足

由假設10)可知，每一個訂單的完成時間與其所分配作業的完成時間相等，即需滿足

if=1,2,…,If.

根據文獻[4]，調度目標為最小化每個訂單的完成時間之和，即最小化訂單的總完成時間

.

為了進一步深入分析問題，針對構建的模型，給出了相關的引理、定理.

證明 假設調度S1為將x訂單及其之前的訂單分配到作業j-1中，之后的訂單分配到作業j中; 調度S2為將x訂單之前的訂單分配到j-1中，x訂單及之后的訂單分配到j中; 調度S3為將x+1訂單及其之前的訂單分配到j-1中，之后的訂單分配到j中. 3種調度的總完成時間分別為TC(S1)、TC(S2)、TC(S3),且

TC(S1)=x(σ1+σ2+…+σx)+(m-x)(σ1+σ2+…+σm)，

TC(S2)=(x-1)(σ1+σ2+…+σx-1)+(m-x+1)(σ1+σ2+…+σm)，

TC(S3)=(x+1)(σ1+σ2+…+σx+1)+(m-x-1)(σ1+σ2+…+σm).

引理1 若一個作業安排在j位置進行加工，可獲得較優的解，不影響參數調整和換模的條件下，具有相同訂單的作業安排的位置應與其相鄰.

證明 如圖2所示，假設位置j之前的所有作業包含的訂單數為n1，時間為t1，完成時間為TC1， jn為j位置后任意一個位置，位置j及jn間所有作業包含的訂單數為n2，時間為t2，總完成時間為TC2，作業a及作業b包含的訂單數量都為n，作業的處理時間為p.

圖2 作業位置的確定

若作業a在j位置上獲得的解較優，則滿足關系 [n(t1+p)+(TC2+n2p)]-[TC2+n(t1+

t2+p)]=n2p-nt2<0.

同樣作業b在作業j+1位置上較其他位置亦滿足關系

[n(t1+p+p)+(TC2+2n2p)]-[TC2+

n2p+n(t1+t2+2p)]=n2p-nt2<0,

此時的解較優.

將作業a的位置安排在作業b的位置前，即ja

證明 令調度S1為作業a在作業b之前，調度S2為作業b在作業a之前. 假設作業a和作業b相鄰，且已經加工的時間為t, 令

則

TC(S1)=ka(t+pfla)+kb[t+pf(la+lb)]，

TC(S2)=kb(t+pflb)+ka[t+pf(la+lb)]，

那么,TC(S2)-TC(S1)=pf(kalb-kbla)，由條件可知,kalb>kbla，且pf為品種f單位晶圓的加工時間，pf>0，因此,TC(S2)-TC(S1)>0.

假設作業a和作業b不相鄰，上述條件相同，則將作業a及作業b分別拆分成la和lb個大小為1的作業，并結合引理1，可證得，作業a位置較作業b位置靠前的方案較優.

2 算法構建

文中將所要解決的問題分為3個層級，分別為1)作業在品種間的分配； 2)訂單成組形成作業； 3)作業的排序. 雖然不少文獻提供了解決包含2)、3)子問題的MOPJ調度問題的方法，但依然缺少解決3個層級結構問題的理論方法，原有的方法也很難擴展解決類似的問題. 同時由于考慮了參數調整，因此文中2)、3)子問題涉及了訂單、作業以及作業族3個層次的調度，與傳統的訂單、作業兩個層次的調度不同. 因此在上述模型和定理的基礎上，提出了訂單成組算法以及混合差分進化的入侵雜草算法.

2.1 訂單成組算法

訂單成組算法以定理1、2為基礎，可以在極短時間內解決子問題2). 假設品種f的訂單數量為m，大小分別為σ1,σ2,…,σm，分配的作業數量為n. 定義作業容量為作業中所包含的訂單的數量.

其具體步驟如下：

步驟1 將訂單按照從大到小的順序排列，即σ1≥σ2≥σ3…≥σm.

步驟2 計算a=?m/n」， b=m-an.

式中?m/n」表示不大于m/n的最大整數.

若b≥1，則作業1至作業b的作業容量為a+1，作業b+1至作業n的作業容量為a;

若b=0，則所有作業的作業容量為a.

步驟3 從最后一個作業開始將訂單按照順序分配到作業中，每一次分配先檢查當前訂單是否可以分配到已分配訂單的作業中，且保證作業容量不超過上述分配的容量，否則分配到最新的作業中. 越靠后的作業優先分配.

步驟4 若步驟3中沒有作業可以分配，且已無未分配訂單的作業. 根據剩余訂單的數量mr，將作業1至作業mr的作業容量加1.

步驟5 根據定理2，將所有作業進行排序.

2.2 混合差分進化的入侵雜草算法

混合差分進化的入侵雜草算法(hybridinvasiveweedoptimization-differentialevolution,HIWO-DE)以雙層嵌套的編碼機制為基礎，將差分進化及訂單成組算法融合到入侵雜草算法的每一次迭代中. 同時在變異操作中，提出了具有學習機制(learningmechanism)的算子，學習作業在前幾代中的排序，調節變異算子的大小，以使作業向理想的排序靠近. 在變異操作和鄰域操作算子中插入了自適應算子，使得算法在前期具有較大的搜索空間，后期具有較強的局部搜索能力.

步驟1 編碼. 采用雙層嵌套的編碼方式，如圖3所示. 第一層采用正整數編碼，表示為雜草個體，每一個正整數表示每一個品種分配的作業數量. 第二層采用的編碼中，每一個作業的第一個位置為作業族編號；第二個位置為隨機實數，所有作業的第二個位置的隨機實數組成目標向量，隨機實數從小到大排序，決定了作業的加工順序；其他位置表示該作業所包含的訂單. 第二層編碼中每一個作業族作業數對應第一層編碼中的正整數.

圖3 編碼方式

步驟2 初始化.

1)初始化雜草個體. 利用約束(6～8)為每一品種限定作業數量的范圍，采用隨機生成的方法，為每一品種產生正整數，即為一個雜草個體，正整數表示作業數量. λ個雜草個體構成一個分散性較好的初始群體.

2)初始化目標向量. 為每一個作業族中的作業產生一個隨機數，并從小到大排序. 所有作業族中的隨機數都從小到大進行排序，產生一個初始化目標向量. 每一個雜草個體產生μ個目標向量，組成次群體.

步驟3 每一個雜草個體進行訂單成組(2.1訂單成組算法). 將成組排序后的作業與步驟2.2產生的隨機數對應.

步驟4 變異. 以當前次種群中目標函數值最優的個體作為擾動向量，再從次種群中隨機選擇兩個不同個體作為差分向量，通過下面公式得到變異向量:

vp,rf,G+1=xp,rf,G+F1(xbest,rf,G-xp,rf,G)+F2|xp1,rf,G-xp2,rf,G|，

式中：p、p1、p2、best∈{1,2,…,μ}，且p1≠p2，best表示次群體中目標函數值最優的個體；xp,rf,G、xp1,rf,G、xp2,rf,G、xbest,rf,G分別表示為第G代的p、p1、p2、best個體中的f品種的第rf個作業的向量；F1為自適應縮放算子，F2為學習算子.

F1較大時，變異的隨機性較大，不利于找到精確的最優解；F1較小時，收斂速度較快，且易收斂于非最優解. 為避免早熟，F1值在算法初期應較大，保持個體的多樣性，易找到全局的最優解；在算法后期，F1的值應較小，易于最優解的搜索和穩定. F2則根據歷代的狀態調節數值大小，若向量有增大的趨勢，則取正值；若向量有減小的趨勢，則取負值. 根據文獻[10-13]的設計規則，得

式中：CR為交叉因子，rand(rf)為評價作業rf時產生均勻分布的隨機數，rnb(rf)為隨機選擇的整數.

每一作業族中，將交叉后得到的數從小到大重新對應到每個作業中.

步驟6 目標向量選擇. 選擇操作是在試驗向量up,G+1與原種群的個體xp,G之間進行，選擇的原則是目標函數值更優的個體進入到下一代，用公式表示為

式中f為目標函數.

步驟7 種子數量確定. 在文獻[14-15]的基礎上，采用基于個體目標函數值產生種子，種子數量計算方式為

φλ=?

式中：φmin和φmax分別為最小和最大的種子數量，fmin和fmax分別為最小和最大的目標函數值，φλ表示λ個體的種子數量，fλ表示λ個體的目標函數值.

步驟8 鄰域操作算子. 針對每個作業族的作業，設計兩種操作算子，±1變異和自適應隨機變異.

±1變異，隨機選擇兩個作業族，對其中一個作業族的作業數量+1，另一個作業族的作業數量-1.

自適應隨機變異采用如下公式確定變異的最大范圍值

c=(rangmax-rangmin)(gm-g)/gm+rangmin，

式中：rangmax和rangmin分別為最大和最小允許變異的值，gm為最大外層進化代數，g為當前外層代數.

在[1,c]中隨機確定一個值d，選擇兩個作業族，其中一個作業族加上d，另一個作業族減去d.

步驟9 產生種子. 隨機選擇一種鄰域操作算子，對雜草個體執行操作，新個體即為當前個體的種子.

步驟10 競爭排除. 將種群中的父代個體及子代個體按照目標函數值排序，選擇較好且互不相同的λ個個體作為下一代的種群.

2.3 算法流程圖

算法的總體流程圖如圖4所示.

圖4 算法總體流程

3 仿真實驗分析

為有效評價算法的性能，本文以求解時間和文獻[16]中提出的解的優度PR作為算法評價指標, PR=V(H,T,Y)/Best(Y)，其中V(H,T,Y)表示算法H在迭代次數為T時對實例Y的求解結果，Best(Y)表示對實例Y求解所能得到的最優值. 解的優度能夠較好地反映算法的收斂性能，其值越小，表明算法的收斂性能越好.

3.1 參數分析

實驗參數參照文獻[2，16]中的參數設計規則設定. 為確定較佳的內層迭代次數，根據約束(6～8)的作業分配約束，產生10個實例作為雜草個體進行實驗，并與未使用定理2(Theorem2)、未使用學習算子的差分進化進行對比，得到迭代次數對解的優度值和求解時間的影響,結果分別見圖5和圖6.

圖5 迭代次數對解的優度值的影響

圖6 迭代次數對計算時間的影響

由圖5可知，結合了學習算子和定理2的算法在對作業進行排序時明顯優于其他兩種算法的收斂性，且可以看出當迭代次數為300～2 000時，3種算法的解都趨于穩定. 同時可以看出結合了學習算子以及定理2后，算法的收斂速度更快，當迭代次數為60時已經找到了較穩定的解. 綜合考慮時間成本和解的優度，本文認為后續實驗中，HIWO-DETL(HIWO-DE-Theorem2-Learning)算法的內層迭代次數定為100，HIWO-DET(HIWO-DE-Theorem2)算法的內層迭代次數定為250，HIWO-DE算法的內層迭代次數定為300是合理的.

用類似的方法，按照不同的參數組合，進行大量實驗. 通過分析實驗結果得到:將算法的外層初始種群λ設為10，內層初始種群μ設為20，縮放因子F0設為0.6，交叉因子CR設為0.5，最大與最小允許變異的值rangmax、rangmin分別設為5和1，最大與最小種子數量φmax、φmin設為6和1，外層迭代次數gm定為10，可以以較高的效率對問題進行求解.

3.2 算例分析

利用2.1所提出的訂單成組算法(記H1)對單品種背景下的單機MOPJ調度問題進行訂單成組和作業排序，對比文獻[4]所提出的啟發式算法(記H2)，為說明H1優于H2，以解的比值及時間作為評價指標，如表1所示.

表1 H1與H2的對比

從表1可知,H1算法所求的解顯著優于H2所求的解，且時間較H2更短. 可見本文提出的方法在解決單品種問題上具有明顯的優勢. 由于本算法的優勢，也使得本文在解決多品種問題及品種間的晶舟分配問題具有良好的性能.

對比4種算法在不同的作業數量及訂單數量的情況下解的優度值，實驗結果如表2所示.

表2 相關解的優度值

從表2可以看出，HIWO-DETL算法的優度值明顯優于其他3種算法. 由于DE算法在對問題進行求解時，無法合理分配各個品種的作業數量，因此在求解開始隨機給定了每個品種的作業數量，只能求解在該作業分配的情況下較優的調度方案，而無法解決作業在各個品種間的分配問題. 因此其他幾個算法所求得的解要優于DE算法. 故本文所提的算法可以在解決單機MOPJ問題的同時，有效解決晶舟在品種間的分配，優化調度方案.

3.3 應用分析

對產品種類數為7、9、11、13、15、17,對應的訂單數為50、100、150的調度問題進行仿真實驗，實驗結果見圖7.

OS表示優化空間(optimizationspace)，且

式中：V(IWO-DE)表示優化了作業分配的求解結果，V(DE)表示未優化作業分配的求解結果.

圖7 產品種類數對解優度值的影響

Fig.7Impactontheperformanceratiobythenumberofproducttypes

由圖7易知，當訂單數相同時，隨著產品種類數的增加，解的優度值有下降的趨勢，這與當種類數增加時，訂單及作業分配的限制增加，調度組合減少，算法更容易求得較優調度結果相符. 從對不同種類與訂單下OS值測算的實驗中發現，優化作業在品種間分配的調度較未優化的調度的性能至少提高了10%，從而說明優化作業分配在MOPJ調度中的重要性.

4 結 論

1)采用雙層嵌套的編碼機制，以晶舟的數量為紐帶將上、下層間的編碼映射統一，為解決在傳統單機MOPJ問題上增加晶舟分配問題的調度提供了研究思路.

2)將差分進化融合到自適應入侵雜草算法的迭代中，同時構造具有學習機制的算子，根據歷代位置，調整參數大小，改善了算法的性能，豐富了解決此類調度問題的理論方法.

3)仿真實驗表明，HIWO-DETL具有較好的求解性能，在MOPJ調度問題中考慮晶舟的優化具有一定的意義.

[1] QU P, MASON S J.Using tabu search on the single machine multi-orders per job scheduling problem[C]//IIE Annual Conference and Exhibition 2004. Houston: Institute of Industrial Engineers, 2004: 1831-1835.

[2] SOBEYKO O, MONCH L. Grouping genetic algorithms for solving single machine multiple orders per job scheduling problems[J]. Annals of Operations Research, 2015, 235(1): 709-739.

[3] JAMPANI J, MASON S J. Column generation heuristics for multiple machine, multiple orders per job scheduling problems[J]. Annals of Operations Research, 2008, 159(1): 261-273.

[4] MASON S J, CHEN J S. Scheduling multiple orders per job in a single machine to minimize total completion time[J]. European Journal of Operational Research, 2010, 207(1): 70-77.

[5] ERRAMILLI V, MASON S J. Multiple orders per job compatible batch scheduling[J]. IEEE Transactions on Electronics Packaging Manufacturing, 2006, 29(4): 285-296.

[6] ERRAMILLI V, MASON S J. Multiple orders per job batch scheduling with incompatible jobs[J]. Annals of Operations Research, 2008, 159(1): 245-260.

[7] WANG Teng, ZHOU Binghai. Scheduling multiple orders per job with multiple constraints on identical parallel machines[J]. Journal of Donghua University (English Edition), 2013(6): 466-471.

[8] CAI Y W, KUTANOGLU E, HASENBEIN J, et al. Single-machine scheduling with advanced process control constraints[J]. Journal of Scheduling, 2012, 15(2): 165-179.

[9] LI L, QIAO F, WU Q D. ACO-based multi-objective scheduling of parallel batch processing machines with advanced process control constraints[J]. The International Journal of Advanced Manufacturing Technology, 2009, 44(9/10): 985-994.

[10]LIN Q, ZHU Q, HUANG P, et al. A novel hybrid multi-objective immune algorithm with adaptive differential evolution[J]. Computers & Operations Research, 2015, 62: 95-111.

[11] 陳華, 范宜仁, 鄧少貴. 基于 logistic 模型的自適應差分進化算法[J]. 控制與決策, 2011, 26(7): 1105-1108.

CHEN Hua, FAN Yiren, DENG Shaogui. Adaptive differential evolution algorithm based on logistic model[J]. Control and Decision, 2011, 26(7)： 1105-1108.

[12]LU C L, CHIU S Y, HSU C H, et al. Enhanced differential evolution based on adaptive mutation and wrapper local search strategies for global optimization problems[J]. Journal of Applied Research and Technology, 2014, 12(6): 1131-1143.

[13]PIOTROWSKI A P. Adaptive memetic differential evolution with global and local neighborhood-based mutation operators[J]. Information Sciences, 2013, 241: 164-194.

[14]RANI D S, SUBRAHMANYAM N, SYDULU M. Multi-objective invasive weed optimization: an application to optimal network reconfiguration in radial distribution systems[J]. International Journal of Electrical Power & Energy Systems, 2015, 73: 932-942.

[15]桑紅燕, 潘全科. 求解流水車間批量流集成調度的離散入侵雜草優化算法[J]. 控制理論與應用, 2015(2): 246-250.

SANG Hongyan, PAN Quanke. A discrete invasive weed optimization algorithm for the intergrated lot-streaming flow shop scheduling problem[J]. Control Theory & Applications, 2015(2): 246-250.

[16]QU P, MASON S J. Metaheuristic scheduling of 300 mm jobs containing multiple orders[J]. IEEE Transactions on Semiconductor Manufacturing, 2005, 18(4): 633-643.

(編輯 楊 波)

Scheduling method of multi-order-per-job for a single machine with multiple preprocess constraints

ZHOU Binghai，WANG Ke

(School of Mechanical Engineering, Tongji University, Shanghai 201804, China)

To efficiently address the multi-order-per-job (MOPJ) scheduling problem of a single machine with multiple preprocess constraints in wafer fabrications, including setup time, uncertain allocation of front opening unified pods(FOUPs), machine parameter adjustment, a scheduling problem domain was described and a mathematical programming model was set up with an objective of minimizing total completion time, and several theorems were established to obtain superior feasible solutions, in addition, a hybrid invasive weed optimization algorithm combined with differential evolution and adopted a two-level encoding mechanism was developed, in which the learning mechanism was introduced to enhance the quality of the solution. Moreover, adaptive process was applied to the mutation and neighborhood search to effectively improve the algorithm convergence. Finally, simulation results verify the validness and feasibility of the proposed algorithm and show that a 10% improvement is made on the performance by the scheduling approach.

MOPJ scheduling; differential evolution; invasive weed; adaptive strategy; allocation of FOUPs

10.11918/j.issn.0367-6234.201603051

2016-03-10

國家自然科學基金(71471135，61273035)

周炳海(1965—)，男，教授，博士生導師

周炳海，bhzhou@tongji.edu.cn

TP391

A

0367-6234(2017)07-0158-07