潘春榮 龍志強

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

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

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

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

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

由k(k≥ 2)臺組合設(shè)備通過BM連接而成的設(shè)備稱為k-組合設(shè)備，設(shè)Nk= {1, 2,…,k}，符號Ci(i∈Nk)表示第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)的最后工序為n[i]，則Ci共有n[i]+1道工序。令Ωk= Nk∪{0}，設(shè)PSij(i∈Nk,j∈Ωn[i])表示設(shè)備Ci的工序j，工序PSij中包含mij個并行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中加工、機械手卸載晶圓前等待、機械手卸載晶圓、機械手移動等活動，各活動的符號表示及耗費時間如表1所示。

表1 設(shè)備Ci中各活動時間

2 調(diào)度分析

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

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

(2)

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

(3)

(4)

由機械手活動序列可獲得機械手的活動周期ψi為：

(i∈Nk)

(5)

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

(6)

(i∈Nk)

(7)

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

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

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

ρ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)周期下，增大機械手等待時間，能有效地降低時間延遲。特別地，由于晶圓在工序0與BM中不進行加工，將時間延遲更多的分配在工序0與BM中，能夠顯著降低工序PSij(j∈Nn[i])的有效時間延遲。因此，時間延遲優(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)為時間延遲優(yōu)化的3個子目標，式(10)表示PM中時間延遲總和最小，式(11)表示最小化PM中的最大時間延遲，式(12)表示LL與BM中時間延遲最大，由此，具有并行加工模塊的多組合設(shè)備時間延遲優(yōu)化問題的調(diào)度目標為min(F) =min(f1,f2,f3)。式(13)保證了組合設(shè)備最優(yōu)周期調(diào)度的條件，式(14)、(15)分別為時間延遲、機械手等待時間的非負約束。

3 調(diào)度算法

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

3.1 MOEA/D-GWO算法改進

(1)目標分解

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

(16)

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

(2)種群迭代更新

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

(3)灰狼變異

為增加種群多樣性，避免局部最優(yōu)，對非“精英”狼進行高斯變異，若變異產(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之間均勻分布的隨機整數(shù)，Gaussian(0,σ2)為服從均值為0，方差為σ2的高斯分布的隨機數(shù)，σ2從σmax到σmin線性減少，計算方式如式(19)所示。

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

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

Xnew=rand·(xmaxv-xminv)+xminv

(20)

3.2 改進后MOEA/D-GWO算法流程

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

4 應(yīng)用實例

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

表2 各PM加工時間

表3 機械手移動及裝卸時間

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

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

為獲得最終解，設(shè)置各目標權(quán)重為(0.2, 0.4, 0.4)，對PF進行計算排序，得到最終解為ω= (ω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，各工序時間延遲為ρ= (ρ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中不會對晶圓質(zhì)量造成損傷，有效時間延遲為在PM中停留時間，則總有效時間延遲為91.92 s。 若采用傳統(tǒng)拉式策略，機械手等待時間ω'= (0, 0, 0, 18, 0, 0, 0, 0, 0, 14, 0, 0, 0, 0, 18)，各工序時間延遲為ρ' = (42, 18, 0, 60, 58, 16, 22, 72, 12, 17, 51, 16, 17, 9, 14)，總有效時間延遲為141 s，改進后時間延遲縮短了34.81%，改進有效。

5 結(jié)語

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

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

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

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