周炳海， 王 科

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

帶多重加工前約束的單機MOPJ調(diào)度方法

周炳海， 王 科

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

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

單作業(yè)多訂單調(diào)度；差分進化；入侵雜草；自適應(yīng)；晶舟分配

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

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

本文研究的單機MOPJ調(diào)度問題以總加權(quán)完成時間最小為目標(biāo)函數(shù)，同時考慮換模時間、參數(shù)調(diào)整、訂單品種多樣性等約束，優(yōu)化訂單的分配，晶舟的加工順序以及晶舟在品種間的分配.

1 問題描述

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

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

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

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

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

j=1,2,…,J；

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

；

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

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

f=1,2,…,F；

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

f=1,2,…,F.

在假設(shè)8)和文獻[8]的基礎(chǔ)上可知，設(shè)備若超過一定次數(shù)未加工過某作業(yè)族，當(dāng)加工該作業(yè)族的作業(yè)時,需考慮參數(shù)調(diào)整時間，即需滿足

f=1,2,…,F.

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

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

if=1,2,…,If.

根據(jù)文獻[4]，調(diào)度目標(biāo)為最小化每個訂單的完成時間之和，即最小化訂單的總完成時間

.

為了進一步深入分析問題，針對構(gòu)建的模型，給出了相關(guān)的引理、定理.

證明 假設(shè)調(diào)度S1為將x訂單及其之前的訂單分配到作業(yè)j-1中，之后的訂單分配到作業(yè)j中; 調(diào)度S2為將x訂單之前的訂單分配到j(luò)-1中，x訂單及之后的訂單分配到j(luò)中; 調(diào)度S3為將x+1訂單及其之前的訂單分配到j(luò)-1中，之后的訂單分配到j(luò)中. 3種調(diào)度的總完成時間分別為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 若一個作業(yè)安排在j位置進行加工，可獲得較優(yōu)的解，不影響參數(shù)調(diào)整和換模的條件下，具有相同訂單的作業(yè)安排的位置應(yīng)與其相鄰.

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

圖2 作業(yè)位置的確定

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

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

同樣作業(yè)b在作業(yè)j+1位置上較其他位置亦滿足關(guān)系

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

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

此時的解較優(yōu).

將作業(yè)a的位置安排在作業(yè)b的位置前，即ja

證明 令調(diào)度S1為作業(yè)a在作業(yè)b之前，調(diào)度S2為作業(yè)b在作業(yè)a之前. 假設(shè)作業(yè)a和作業(yè)b相鄰，且已經(jīng)加工的時間為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.

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

2 算法構(gòu)建

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

2.1 訂單成組算法

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

其具體步驟如下：

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

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

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

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

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

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

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

步驟5 根據(jù)定理2，將所有作業(yè)進行排序.

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

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

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

圖3 編碼方式

步驟2 初始化.

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

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

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

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

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表示次群體中目標(biāo)函數(shù)值最優(yōu)的個體；xp,rf,G、xp1,rf,G、xp2,rf,G、xbest,rf,G分別表示為第G代的p、p1、p2、best個體中的f品種的第rf個作業(yè)的向量；F1為自適應(yīng)縮放算子，F(xiàn)2為學(xué)習(xí)算子.

F1較大時，變異的隨機性較大，不利于找到精確的最優(yōu)解；F1較小時，收斂速度較快，且易收斂于非最優(yōu)解. 為避免早熟，F(xiàn)1值在算法初期應(yīng)較大，保持個體的多樣性，易找到全局的最優(yōu)解；在算法后期，F(xiàn)1的值應(yīng)較小，易于最優(yōu)解的搜索和穩(wěn)定. F2則根據(jù)歷代的狀態(tài)調(diào)節(jié)數(shù)值大小，若向量有增大的趨勢，則取正值；若向量有減小的趨勢，則取負值. 根據(jù)文獻[10-13]的設(shè)計規(guī)則，得

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

每一作業(yè)族中，將交叉后得到的數(shù)從小到大重新對應(yīng)到每個作業(yè)中.

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

式中f為目標(biāo)函數(shù).

步驟7 種子數(shù)量確定. 在文獻[14-15]的基礎(chǔ)上，采用基于個體目標(biāo)函數(shù)值產(chǎn)生種子，種子數(shù)量計算方式為

φλ=?

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

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

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

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

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

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

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

步驟9 產(chǎn)生種子. 隨機選擇一種鄰域操作算子，對雜草個體執(zhí)行操作，新個體即為當(dāng)前個體的種子.

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

2.3 算法流程圖

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

圖4 算法總體流程

3 仿真實驗分析

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

3.1 參數(shù)分析

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

圖5 迭代次數(shù)對解的優(yōu)度值的影響

圖6 迭代次數(shù)對計算時間的影響

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

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

3.2 算例分析

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

表1 H1與H2的對比

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

對比4種算法在不同的作業(yè)數(shù)量及訂單數(shù)量的情況下解的優(yōu)度值，實驗結(jié)果如表2所示.

表2 相關(guān)解的優(yōu)度值

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

3.3 應(yīng)用分析

對產(chǎn)品種類數(shù)為7、9、11、13、15、17,對應(yīng)的訂單數(shù)為50、100、150的調(diào)度問題進行仿真實驗，實驗結(jié)果見圖7.

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

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

圖7 產(chǎn)品種類數(shù)對解優(yōu)度值的影響

Fig.7Impactontheperformanceratiobythenumberofproducttypes

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

4 結(jié) 論

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

2)將差分進化融合到自適應(yīng)入侵雜草算法的迭代中，同時構(gòu)造具有學(xué)習(xí)機制的算子，根據(jù)歷代位置，調(diào)整參數(shù)大小，改善了算法的性能，豐富了解決此類調(diào)度問題的理論方法.

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

[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 模型的自適應(yīng)差分進化算法[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]桑紅燕, 潘全科. 求解流水車間批量流集成調(diào)度的離散入侵雜草優(yōu)化算法[J]. 控制理論與應(yīng)用, 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

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

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

周炳海，bhzhou@#edu.cn

TP391

A

0367-6234(2017)07-0158-07