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

周炳海， 王 科

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

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

周炳海， 王 科

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

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

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

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

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

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

1 問(wèn)題描述

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

圖1 單機(jī)MOPJ調(diào)度問(wèn)題實(shí)例Fig.1 The instance of a single machine MOPJ scheduling problem

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

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

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

j=1,2,…,J；

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

；

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

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

f=1,2,…,F；

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

f=1,2,…,F.

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

f=1,2,…,F.

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

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

if=1,2,…,If.

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

.

為了進(jìn)一步深入分析問(wèn)題，針對(duì)構(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)度的總完成時(shí)間分別為T(mén)C(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 若一個(gè)作業(yè)安排在j位置進(jìn)行加工，可獲得較優(yōu)的解，不影響參數(shù)調(diào)整和換模的條件下，具有相同訂單的作業(yè)安排的位置應(yīng)與其相鄰.

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

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

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

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

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

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

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

此時(shí)的解較優(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)加工的時(shí)間為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單位晶圓的加工時(shí)間，pf>0，因此,TC(S2)-TC(S1)>0.

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

2 算法構(gòu)建

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

2.1 訂單成組算法

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

其具體步驟如下：

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

步驟2 計(jì)算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 從最后一個(gè)作業(yè)開(kāi)始將訂單按照順序分配到作業(yè)中，每一次分配先檢查當(dāng)前訂單是否可以分配到已分配訂單的作業(yè)中，且保證作業(yè)容量不超過(guò)上述分配的容量，否則分配到最新的作業(yè)中. 越靠后的作業(yè)優(yōu)先分配.

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

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

2.2 混合差分進(jìn)化的入侵雜草算法

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

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

圖3 編碼方式

步驟2 初始化.

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

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

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

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

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)的個(gè)體；xp,rf,G、xp1,rf,G、xp2,rf,G、xbest,rf,G分別表示為第G代的p、p1、p2、best個(gè)體中的f品種的第rf個(gè)作業(yè)的向量；F1為自適應(yīng)縮放算子，F(xiàn)2為學(xué)習(xí)算子.

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

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

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

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

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

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

φλ=?

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

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

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

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

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

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

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

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

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

2.3 算法流程圖

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

圖4 算法總體流程

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

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

3.1 參數(shù)分析

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

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

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

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

用類(lèi)似的方法，按照不同的參數(shù)組合，進(jìn)行大量實(shí)驗(yàn). 通過(guò)分析實(shí)驗(yàn)結(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，可以以較高的效率對(duì)問(wèn)題進(jìn)行求解.

3.2 算例分析

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

表1 H1與H2的對(duì)比

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

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

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

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

3.3 應(yīng)用分析

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

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

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

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

Fig.7Impactontheperformanceratiobythenumberofproducttypes

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

4 結(jié) 論

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

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

3)仿真實(shí)驗(yàn)表明，HIWO-DETL具有較好的求解性能，在MOPJ調(diào)度問(wèn)題中考慮晶舟的優(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ìn)化算法[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]桑紅燕, 潘全科. 求解流水車(chē)間批量流集成調(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

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

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

周炳海，bhzhou@#edu.cn

TP391

A

0367-6234(2017)07-0158-07