多組合設備的時間延遲優化研究 *

潘春榮 龍志強

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

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

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

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

1 穩態生產過程描述

由k(k≥ 2)臺組合設備通過BM連接而成的設備稱為k-組合設備，設Nk= {1, 2,…,k}，符號Ci(i∈Nk)表示第i臺單組合設備。將LL(Load Lock, LL)視為工序0，連接設備Ci與Ci+1(i∈Nk-1)的BM視為設備Ci的b[i]工序或設備Ci+1的工序0，晶圓在設備Ci(i∈Nk)的最后工序為n[i]，則Ci共有n[i]+1道工序。令Ωk= Nk∪{0}，設PSij(i∈Nk,j∈Ωn[i])表示設備Ci的工序j，工序PSij中包含mij個并行PM，則晶圓在k-組合設備中的生產過程可以描述為：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。

穩態下工序PSij的生產過程包括晶圓載入PM、晶圓在PM中加工、機械手卸載晶圓前等待、機械手卸載晶圓、機械手移動等活動，各活動的符號表示及耗費時間如表1所示。

表1 設備Ci中各活動時間

2 調度分析

2.1 單組合設備調度分析

對于工序PSij(i∈Nk,j∈Nn[i]-1)，穩態單位周期內，機械手活動序列為：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)的機械手活動序列基礎上，將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，穩態下mij片晶圓同時進行加工，則工序PSij的生產周期πij為：

(2)

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

(3)

(4)

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

(i∈Nk)

(5)

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

(6)

(i∈Nk)

(7)

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

2.2 k-組合設備調度分析

設k-組合設備的系統生產周期為π，Πi為設備Ci(i∈Nk)的基本生產周期，用于衡量各設備的作業負荷，其中Πi=max{θi0,θi1,…,θin[i],ψi1}，當Πp=max{Πi|i∈Nk}時，稱設備Cp為瓶頸設備。通過調整機械手等待時間，使得π=Πp，系統達到最優生產周期，此時工序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)

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

(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)為時間延遲優化的3個子目標，式(10)表示PM中時間延遲總和最小，式(11)表示最小化PM中的最大時間延遲，式(12)表示LL與BM中時間延遲最大，由此，具有并行加工模塊的多組合設備時間延遲優化問題的調度目標為min(F) =min(f1,f2,f3)。式(13)保證了組合設備最優周期調度的條件，式(14)、(15)分別為時間延遲、機械手等待時間的非負約束。

3 調度算法

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

3.1 MOEA/D-GWO算法改進

(1)目標分解

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

(16)

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

(2)種群迭代更新

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

(3)灰狼變異

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

(18)

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

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

(4)修復不可行解

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

Xnew=rand·(xmaxv-xminv)+xminv

(20)

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

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

4 應用實例

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

表2 各PM加工時間

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

該3-組合設備各工序可以表示為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。經計算，該3-組合設備為加工臨界，且π=98 s。

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

為獲得最終解，設置各目標權重為(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= -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中不會對晶圓質量造成損傷，有效時間延遲為在PM中停留時間，則總有效時間延遲為91.92 s。 若采用傳統拉式策略，機械手等待時間ω'= (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 結語

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

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

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

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