多組合設(shè)備的時(shí)間延遲優(yōu)化研究 *

潘春榮 龍志強(qiáng)

(江西理工大學(xué)機(jī)電工程學(xué)院，江西 贛州 341000)

時(shí)間延遲過長(zhǎng)會(huì)對(duì)晶圓質(zhì)量造成損失。Wang J、Yang F J等[1-2]將駐留時(shí)間延遲作為約束，建立了生產(chǎn)系統(tǒng)的Petri網(wǎng)模型，對(duì)單臂組合設(shè)備進(jìn)行穩(wěn)態(tài)調(diào)度優(yōu)化。潘春榮等[3]將時(shí)間延遲優(yōu)化作為目標(biāo)，提出了一種等待時(shí)間分配策略，對(duì)單臂組合設(shè)備進(jìn)行調(diào)度。在此基礎(chǔ)上，Xiong W Q等[4]開發(fā)了3種啟發(fā)式算法對(duì)機(jī)械手等待時(shí)間進(jìn)行進(jìn)一步分配，從而有效降低了單臂組合設(shè)備的時(shí)間延遲。

上述學(xué)者對(duì)單臺(tái)組合設(shè)備進(jìn)行了調(diào)度，對(duì)于多組合設(shè)備，由于各組合設(shè)備間耦合依賴性強(qiáng)，多組合設(shè)備的調(diào)度更加復(fù)雜。Hu J等[5]考慮機(jī)械手、加工模塊(process module, PM)約束，構(gòu)建了相應(yīng)數(shù)學(xué)模型，并提出基于分解的啟發(fā)式算法對(duì)模型進(jìn)行求解。Sakai M等[6]構(gòu)建了高效的多組合設(shè)備Petri網(wǎng)模型，基于此，Bai L等[7]通過配置不同BM的容量，達(dá)到了系統(tǒng)的調(diào)度周期下限。對(duì)于多組合設(shè)備的時(shí)間延遲約束問題，Bao T等[8]從混合整數(shù)規(guī)劃的角度，提出了生產(chǎn)系統(tǒng)的周期調(diào)度策略。Yan Y等[9]考慮時(shí)間延遲約束，提出了同時(shí)適用于單臂、雙臂多組合設(shè)備的非周期調(diào)度模型，并改進(jìn)了一種動(dòng)態(tài)規(guī)劃算法對(duì)模型進(jìn)行求解。

上述研究大多對(duì)時(shí)間延遲進(jìn)行分析，僅有少量文獻(xiàn)將時(shí)間延遲作為目標(biāo)進(jìn)行優(yōu)化，特別地，在多組合設(shè)備中，時(shí)間延遲的優(yōu)化更是鮮有涉及。為平衡各工序的作業(yè)負(fù)載，組合設(shè)備常引入并行加工模塊。本文對(duì)具有并行加工模塊的單臂線形多組合設(shè)備進(jìn)行研究，將時(shí)間優(yōu)化問題轉(zhuǎn)化為以降低時(shí)間延遲為目標(biāo)的機(jī)械手等待時(shí)間分配模型，并提出一種改進(jìn)多目標(biāo)灰狼算法對(duì)問題進(jìn)行求解。

1 穩(wěn)態(tài)生產(chǎn)過程描述

由k(k≥ 2)臺(tái)組合設(shè)備通過BM連接而成的設(shè)備稱為k-組合設(shè)備，設(shè)Nk= {1, 2,…,k}，符號(hào)Ci(i∈Nk)表示第i臺(tái)單組合設(shè)備。將LL(Load Lock, LL)視為工序0，連接設(shè)備Ci與Ci+1(i∈Nk-1)的BM視為設(shè)備Ci的b[i]工序或設(shè)備Ci+1的工序0，晶圓在設(shè)備Ci(i∈Nk)的最后工序?yàn)閚[i]，則Ci共有n[i]+1道工序。令Ωk= Nk∪{0}，設(shè)PSij(i∈Nk,j∈Ωn[i])表示設(shè)備Ci的工序j，工序PSij中包含mij個(gè)并行PM，則晶圓在k-組合設(shè)備中的生產(chǎn)過程可以描述為：PS10→PS11→PS12→… →PS1(b[1])→PS21→… →PS(k-1)(b[k-1])→PSk1→… →PSk(n[k])→PSk0→PS(k-1)(b[k-1]+1)→… →PS(k-1)0→PS(k-2)(b[k-2]+1)→… →PS20→PS1(b[1]+1)→… →PS1(n[1])→PS10。

穩(wěn)態(tài)下工序PSij的生產(chǎn)過程包括晶圓載入PM、晶圓在PM中加工、機(jī)械手卸載晶圓前等待、機(jī)械手卸載晶圓、機(jī)械手移動(dòng)等活動(dòng)，各活動(dòng)的符號(hào)表示及耗費(fèi)時(shí)間如表1所示。

表1 設(shè)備Ci中各活動(dòng)時(shí)間

2 調(diào)度分析

2.1 單組合設(shè)備調(diào)度分析

對(duì)于工序PSij(i∈Nk,j∈Nn[i]-1)，穩(wěn)態(tài)單位周期內(nèi)，機(jī)械手活動(dòng)序列為：dij→xij→si(j+1)→yi(j-1)→qi(j-1)→di(j-1)→xi(j-1)→sij。在PSij(i∈Nk,j∈Nn[i]-1)的機(jī)械手活動(dòng)序列基礎(chǔ)上，將si(j+1)更換為si0，即可獲得PSi(n[i])的機(jī)械手活動(dòng)序列。對(duì)于工序PSi0，機(jī)械手活動(dòng)序列為：di0→xi0→si1→yi(n[i])→qi(n[i])→di(n[i])→xi(n[i])→si0。工序PSij包含mij個(gè)并行PM，穩(wěn)態(tài)下mij片晶圓同時(shí)進(jìn)行加工，則工序PSij的生產(chǎn)周期πij為：

(2)

將生產(chǎn)周期中的時(shí)間延遲及機(jī)械手等待時(shí)間去除，可獲得工序PSij的作業(yè)負(fù)荷θij：

(3)

(4)

由機(jī)械手活動(dòng)序列可獲得機(jī)械手的活動(dòng)周期ψi為：

(i∈Nk)

(5)

(i∈Nk,j∈Nn[i])

(6)

(i∈Nk)

(7)

令設(shè)備Ci(i∈Nk)的生產(chǎn)周期為πi，由文獻(xiàn)[3]可知，穩(wěn)態(tài)下對(duì)設(shè)備Ci進(jìn)行周期調(diào)度，需滿足各工序加工時(shí)間均與機(jī)械手活動(dòng)周期相等的條件，即πi=πi0=πi1=…=πi(n[i])=ψi。為達(dá)成該條件，可調(diào)節(jié)機(jī)械手等待時(shí)間，使得各工序生產(chǎn)周期相等。

2.2 k-組合設(shè)備調(diào)度分析

設(shè)k-組合設(shè)備的系統(tǒng)生產(chǎn)周期為π，Πi為設(shè)備Ci(i∈Nk)的基本生產(chǎn)周期，用于衡量各設(shè)備的作業(yè)負(fù)荷，其中Πi=max{θi0,θi1,…,θin[i],ψi1}，當(dāng)Πp=max{Πi|i∈Nk}時(shí)，稱設(shè)備Cp為瓶頸設(shè)備。通過調(diào)整機(jī)械手等待時(shí)間，使得π=Πp，系統(tǒng)達(dá)到最優(yōu)生產(chǎn)周期，此時(shí)工序PSij的時(shí)間延遲ρij計(jì)算如下：

ρij=ij-λij=mij·Πp-(λij+4ci+3ai+ωi(j-1)),

(i∈Nk,j∈Nn[i])

(8)

ρi0=i0-λi0=mi0·Πp-(4ci+3ai+ωi(n[i])),

(i∈Nk)

(9)

結(jié)合式(1)～(2)、(8)～(9)可知，在某系統(tǒng)周期下，增大機(jī)械手等待時(shí)間，能有效地降低時(shí)間延遲。特別地，由于晶圓在工序0與BM中不進(jìn)行加工，將時(shí)間延遲更多的分配在工序0與BM中，能夠顯著降低工序PSij(j∈Nn[i])的有效時(shí)間延遲。因此，時(shí)間延遲優(yōu)化問題可以表示為：

(10)

min(f2)=min(max{ρij|i∈Nk,j∈Nn[i]}),

j≠b[i]

(11)

(12)

(13)

ωi(j-1)≤mij·Πp-(λij+4ci+3ai)，

(i∈Nk,j∈Ωn[i])

(14)

(15)

式(10)～(12)為時(shí)間延遲優(yōu)化的3個(gè)子目標(biāo)，式(10)表示PM中時(shí)間延遲總和最小，式(11)表示最小化PM中的最大時(shí)間延遲，式(12)表示LL與BM中時(shí)間延遲最大，由此，具有并行加工模塊的多組合設(shè)備時(shí)間延遲優(yōu)化問題的調(diào)度目標(biāo)為min(F) =min(f1,f2,f3)。式(13)保證了組合設(shè)備最優(yōu)周期調(diào)度的條件，式(14)、(15)分別為時(shí)間延遲、機(jī)械手等待時(shí)間的非負(fù)約束。

3 調(diào)度算法

本文模型為多目標(biāo)優(yōu)化模型，采用啟發(fā)式算法更易于尋找全局最優(yōu)解?；依莾?yōu)化算法(grey wolf optimizer, GWO)[10]參數(shù)少、對(duì)參數(shù)依賴性弱、易實(shí)現(xiàn)，并且能夠在全局搜索與局部尋優(yōu)間實(shí)現(xiàn)平衡，在問題求解精度與收斂速度方面均有良好性能[11]。因此，采用GWO算法對(duì)模型進(jìn)行求解。鑒于本文模型為多目標(biāo)優(yōu)化模型，故引入MOEA/D算法[12]并對(duì)其進(jìn)行改進(jìn)。

3.1 MOEA/D-GWO算法改進(jìn)

(1)目標(biāo)分解

采用切比雪夫聚合方法將多目標(biāo)優(yōu)化轉(zhuǎn)化為多個(gè)單目標(biāo)優(yōu)化問題：設(shè)各目標(biāo)的理想點(diǎn)為zi*(i∈{1, 2, 3})，在可行解空間Γ中均勻分布一組權(quán)重向量εi，如式(16)所示，其中pop為種群數(shù)量，并由切比雪夫策略將min(F) =min (f1,f2,f3)分解成3個(gè)單目標(biāo)優(yōu)化問題的最優(yōu)解，如式(17)所示。

(16)

minF(x|εi,z*)=mingte(x|εi,zi*)=

(2)種群迭代更新

根據(jù)歐幾里得距離最短，將εi進(jìn)行聚類分析，形成鄰域；隨機(jī)選取兩個(gè)鄰域的εi，對(duì)解集合進(jìn)行GWO算法迭代更新。

(3)灰狼變異

為增加種群多樣性，避免局部最優(yōu)，對(duì)非“精英”狼進(jìn)行高斯變異，若變異產(chǎn)生的新解優(yōu)于原解，則采用新解，變異方式如下：

(18)

σ=σmax-t·(σmax-σmin)/Gmax(19)

式(18)中xmaxv、xminv為第v維決策空間的上下界，Xnew為經(jīng)過變異后產(chǎn)生的灰狼新位置，U[1,2,3]表示1到3之間均勻分布的隨機(jī)整數(shù)，Gaussian(0,σ2)為服從均值為0，方差為σ2的高斯分布的隨機(jī)數(shù)，σ2從σmax到σmin線性減少，計(jì)算方式如式(19)所示。

(4)修復(fù)不可行解

對(duì)不可行解進(jìn)行修復(fù)，修復(fù)方式如式(20)，其中rand為(0, 1)均勻分布的隨機(jī)數(shù)，Xnew為修復(fù)后灰狼的位置。

Xnew=rand·(xmaxv-xminv)+xminv

(20)

3.2 改進(jìn)后MOEA/D-GWO算法流程

基于上述MOEA/D-GWO算法的改進(jìn)操作，改進(jìn)后算法的流程如圖1所示。

4 應(yīng)用實(shí)例

有一單臂線形3-組合設(shè)備對(duì)晶圓進(jìn)行加工，設(shè)備C1包含2個(gè)LL，3個(gè)PM，1個(gè)BM；設(shè)備C2包含4個(gè)PM，2個(gè)BM；設(shè)備C3包含5個(gè)PM，1個(gè)BM。晶圓從設(shè)備C1的LL出發(fā)，經(jīng)過各PM、BM，最終加工完成返回LL。設(shè)定各PM加工時(shí)間、機(jī)械手移動(dòng)、晶圓裝載與卸載時(shí)間見表2、表3。

表2 各PM加工時(shí)間

表3 機(jī)械手移動(dòng)及裝卸時(shí)間

該3-組合設(shè)備各工序可以表示為PS10、PS11、PS12、PS1(b[1])、PS20、PS21、PS22、PS2(b[2])、PS23、PS24、PS30、PS31、PS32、PS33、PS34，其中PS11表示PM11、PM12兩個(gè)并行PM，PS32表示PM32、PM33兩個(gè)并行PM。經(jīng)計(jì)算，該3-組合設(shè)備為加工臨界，且π=98 s。

采用改進(jìn)的MOEA/D-GWO算法對(duì)該案例進(jìn)行求解，參數(shù)設(shè)置如下：種群數(shù)量pop=100，鄰域大小為6，更新因子dmax=2、dmin=0，迭代4 000次，得到帕累托前沿(pareto front, PF)如圖2所示。為評(píng)估算法收斂性，繼續(xù)采用MOEA/D、NAGAII算法[13]對(duì)案例進(jìn)行求解，并引入GD(generational distance, GD)指標(biāo)[14]對(duì)算法性能進(jìn)行評(píng)價(jià)。GD指標(biāo)對(duì)比如圖3所示，隨著迭代次數(shù)的增加，MOEA/D-GWO算法、MOEA/D算法以及NSGAII算法均能較好的逼近PF，但MOEA/D-GWO算法的GD值更小，求解質(zhì)量更優(yōu)。

為獲得最終解，設(shè)置各目標(biāo)權(quán)重為(0.2, 0.4, 0.4)，對(duì)PF進(jìn)行計(jì)算排序，得到最終解為ω= (ω10,ω11,ω12,ω1(b[1]),ω20,ω21,ω22,ω2(b[2]),ω23,ω24,ω30,ω31,ω32,ω33,ω34) = (17.50, 0.00, 0.25, 0.25, 2.05, 8.05, 0.13, 0.60, 3.04, 0.13, 4.88, 4.99, 3.40, 4.57, 0.16)，F(xiàn)= -108.87，各工序時(shí)間延遲為ρ= (ρ10,ρ11,ρ12,ρ1(b[1]),ρ20,ρ21,ρ22,ρ2(b[2]),ρ23,ρ24,ρ30,ρ31,ρ32,ρ33,ρ34) = (59.75, 0.50, 0.00, 59.75, 71.87, 13.95, 13.95, 71.87, 11.40, 13.96, 68.84, 11.12, 12.01, 5.60, 9.43)，晶圓在LL、BM中不會(huì)對(duì)晶圓質(zhì)量造成損傷，有效時(shí)間延遲為在PM中停留時(shí)間，則總有效時(shí)間延遲為91.92 s。 若采用傳統(tǒng)拉式策略，機(jī)械手等待時(shí)間ω'= (0, 0, 0, 18, 0, 0, 0, 0, 0, 14, 0, 0, 0, 0, 18)，各工序時(shí)間延遲為ρ' = (42, 18, 0, 60, 58, 16, 22, 72, 12, 17, 51, 16, 17, 9, 14)，總有效時(shí)間延遲為141 s，改進(jìn)后時(shí)間延遲縮短了34.81%，改進(jìn)有效。

5 結(jié)語

本文對(duì)帶有并行加工模塊的單臂線形多組合設(shè)備進(jìn)行研究，探究了機(jī)械手等待時(shí)間對(duì)時(shí)間延遲的影響機(jī)制，以機(jī)械手等待時(shí)間為變量，建立了時(shí)間延遲的多目標(biāo)優(yōu)化模型，提出改進(jìn)的多目標(biāo)啟發(fā)式算法對(duì)模型求解，并用案例驗(yàn)證了模型與算法的有效性。主要貢獻(xiàn)為：

(1)構(gòu)建了單臂線形多組合設(shè)備的時(shí)間延遲優(yōu)化模型，為多組合設(shè)備時(shí)間延遲優(yōu)化問題提供了一個(gè)解決思路。

(2)以多組合設(shè)備加工晶圓為案例進(jìn)行應(yīng)用，對(duì)模型及算法的有效性進(jìn)行了驗(yàn)證，同時(shí)為具有并行加工模塊的單臂線形多組合設(shè)備提供了高效可行的時(shí)間延遲優(yōu)化方案。

多組合設(shè)備的時(shí)間延遲優(yōu)化是個(gè)復(fù)雜的問題，本文將晶圓加工時(shí)間視為固定值，但在實(shí)際加工過程中，晶圓加工時(shí)間并非是固定不變的，而是在中心值上下波動(dòng)。因此，下一步將考慮時(shí)間波動(dòng)因素，對(duì)多組合設(shè)備的時(shí)間延遲優(yōu)化進(jìn)行更深入的研究。