考慮晶圓駐留時間約束的雙臂組合設備群調度*

馬利平 劉玉敏 趙艷平 王際鵬 承姿辛

（①河南工業大學漯河工學院，河南 漯河 462000；②湖北工業大學機械工程學院，湖北 武漢 430068；③湖北工業大學現代制造質量工程湖北省重點實驗室，湖北 武漢 430068）

組合設備（cluster tool）是半導體制造中一類極為昂貴的高端裝備，廣泛用于半導體芯片制造的前端工藝[1]。多臺單一組合設備（single-cluster tool，SCT）經緩沖模塊（buffer module，BM）連接而成的設備集群，即組合設備群 （multi-cluster tool，MCT），代表了組合設備發展的新趨勢，近年已在行業領先的芯片制造企業得到快速應用[2]。由多臺單/雙臂組合設備構成的設備集群稱為單/雙臂組合設備群，而混合組合設備群由單、雙臂兩種設備組合而成。按設備拓撲結構劃分，組合設備群可分為線性和樹形兩種，如圖1 所示為一臺線性雙臂組合設備群。

圖1 線性雙臂組合設備群

作為一種多設備集群系統，組合設備群調度是一類極為復雜的組合優化問題。對于組合設備群而言，k-晶圓周期調度難以控制和實現，且極易造成系統阻塞。1-晶圓周期調度可形成穩定的加工過程，操作簡單且易于實施。Zhu Q H 等[3]證明了處于加工臨界的單臂線性組合設備群必定存在1-晶圓周期調度。進一步，引入晶圓駐留時間約束并給出了相應的最優1-晶圓周期調度方法[4]。而后，利用剪枝策略將樹形組合設備群轉換為線性組合設備鏈，從而獲得最優1-晶圓周期調度[5]；對于處于傳輸臨界的單臂線性組合設備群，Yang F J 等[6]給出了最優1-晶圓周期調度求解方法。針對線性組合設備群，Bao T P 等[7]采用混合整數規劃模型求解周期調度，Yan Y Y 等[8]通過帕累托優化方法求解非周期調度。而對于線性雙臂組合設備群，Zhu Q H 等[9]運用集成調度方法優化暫態和穩態產能，Yang F J 等[10]采用實時調度策略計算設備在作業時間波動情形下的駐留時間延遲累積，Zhu Q H 等[11]研究了兩種晶圓產品混合加工的調度優化問題。

除了設備的拓撲結構外，BM 容量和機械手構成形式亦對組合設備群的調度具有重要影響。 Yang F J 等[12]研究了BM 容量為2 的線性單臂組合設備群調度問題，提出了有效且易于實施的算法求解1-晶圓周期調度。李文濤等[13]修改Petri 網模型的初始標識，促使系統加速進入穩態，提出了有效的調度策略。黃鵬等[14]研究了BM 容量為2 的樹形單臂組合設備群的優化調度問題，提出了最優1-晶圓周期調度求解算法。針對處于加工臨界的線性單臂組合設備群，Bai L P 等[15]深入分析了BM 配置方式對系統調度的影響機理，給出了周期時間下界可達的BM 最優配置方法。Yang F J 等[16-18]證明線性混合組合設備群存在1-晶圓周期調度，并給出了不同約束條件下的最優1-晶圓周期調度求解方法。對于樹形混合組合設備群，Yang F J 等[19-20]給出了最優1-晶圓周期調度方法。

綜合前文所述，現有組合設備群調度控制的研究重點在于單臂組合設備群和混合組合設備群，而對于生產效率更高的雙臂組合設備群，鮮有研究給予關注。此外，現有工作局限于特定拓撲結構的組合設備群，尚未有研究統一考慮線性和樹形設備的調度問題。鑒于上述原因，本文對考慮晶圓駐留時間約束的雙臂組合設備群調度問題開展研究。首先引入特征雙臂組合設備并研究其穩態調度問題，隨后采用特征轉換方法將線性或樹形雙臂組合設備群轉換為特征雙臂組合設備，然后根據轉換后的特征雙臂組合設備求解雙臂組合設備群的穩態調度，最后通過算例驗證所提方法的可行性和有效性。

1 問題描述

1.1 基本假設

與文獻[3-9, 16-20]一致，不失一般性，針對雙臂組合設備群穩態調度問題做出如下約定：① 不考慮并行加工模塊（process module，PM），即每個PM 僅執行一道工序的加工；② 每個BM 被兩個鄰接單臺組合設備共享，容量為1, 且不具備晶圓加工功能；③晶圓加工時間和機械手作業時間為常量；④ 所有晶圓擁有相同的配方，訪問每個PM 不超過一次（BM 除外）。此外，考慮晶圓駐留時間約束，即晶圓在PM 完成加工后必須在限定的時間之內卸載。

1.2 符號設定

晶圓在組合設備群中的加工路徑用 R表示, 沿路徑 R 的第i臺SCT 用Ci表示，i∈ NK= {1, 2,···,K}。線性組合設備群中的C1/CK與樹形組合設備群中的“葉設備”（leaf SCT），均只有一臺鄰接SCT，其余任意SCT 至少有兩臺鄰接SCT。當Ci至少有3 臺鄰接SCT 時，稱之為“叉設備”（fork SCT）。令和分別表示組合設備群的“葉設備”和“叉設備”符號下標的集合，則有= {i|i∈,Ci是“葉設備”}，= {i|i∈,Ci是“叉設備”}。沿路徑 R，若Ci的排序相對Cj靠前，則稱Ci為Cj的上游設備，或稱Cj為Ci的下游設備。

在組合設備群中，兩臺鄰接的SCT 通過BM 相連，該BM 可視作下游SCT 的輸入模塊或上游SCT 的輸出模塊。另外，C1的真空鎖可視作輸入模塊?！叭~設備”沒有輸出模塊，而其余SCT 擁有一個輸入模塊和至少一個輸出模塊。具體來說，線性組合設備群中的Ci只有一個輸出模塊（符號標記為b[i]）, 而樹形組合設備群中的Ci至少擁有一個輸出模塊（符號標記分別為b[i]_1,b[i]_2,···,b[i]_ci, 其中i∈）。令 Sb為輸出模塊符號標記的集合,即 Sb= {b[i]_1,b[i]_2,···,b[i]_ci, 其中i∈}。需要注意的是，輸入模塊可視作沒有加工功能的第0 道工序，則Ci總計可執行n[i] + 1 道工序。

用Pij（i∈，j∈Ωn[i]={0}）表示Ci的第j道工序，其中Pi0表示輸入模塊對應的工序。晶圓在工序Pij（i∈，j∈）的加工時間用αij表示，加工完成后允許停留的最長時間為βij。與文獻[3-9, 16-20]中的設定相同，對于一臺組合設備群，Ci中機械手在任意工序裝/卸載一枚晶圓耗費的時間相同，用ρci表示。同樣地，Ci中機械手運送一枚晶圓至任意模塊所耗費的時間相同，用θci表示。設機械手在工序Pij執行交換操作需要的時間為γci，執行交換操作前后的等待時間分別表示為ωij1和ωij2。此外，組合設備群的生產周期時間用?m表示。

2 特征雙臂組合設備及其調度

2.1 特征雙臂組合設備

傳統雙臂組合設備與特征雙臂組合設備的結構如圖2 所示，二者不同之處在于傳統設備至多有6個PM，特征設備配置h（h∈）個PM。為克服工序瓶頸，傳統設備會考慮配置并行PM，而特征設備不考慮并行PM，每道工序僅配置一個PM。在傳統設備中，機械手運送晶圓到各個PM 所耗費的時間一般相同；而在特征設備中，約定機械手運送晶圓到各個PM 所耗費的時間不一定相同。由于特征設備與傳統設備差別巨大，現有傳統雙臂組合設備的調度方法已經不再適用，需探索新的調度方法。

圖2 傳統雙臂組合設備與特征雙臂組合設備的結構

為便于分析，機械手的常規作業時間（即裝載、卸載、交換）和晶圓在PM 內的加工時間可認為是常量。第i道工序記為Pi，i∈ Ωh+1。真空鎖可認為是第0 或h+ 1 道工序，因此用P0表示釋放待加工晶圓的初始工序，而Ph+1表示存儲已完成加工晶圓的終止工序。機械手在任意工序Pi裝/卸載晶圓耗費的時間用ρi（i∈ Ωh+1）表示，在工序Pi執行交換操作耗費的時間用γi（i∈）表示，將晶圓從工序Pi運送至工序Pi+1耗費的時間用θi（i∈ Ωh）表示。晶圓在工序Pi的加工時間和駐留時間（即自載入PM 開始至卸載時，晶圓在PM 內停留的時間）分別記為αi、τi，i∈。加工完畢后，晶圓在PMi內允許停留的最長時間記為βi，則有τi∈ [αi,αi+βi]，i∈。

2.2 作業時間分析

當機械手抵達工序Pi執行交換操作時，PMi中的晶圓有可能仍舊處在加工狀態。此時，機械手須等待一段時間（記為ωi1），直至晶圓完成加工。為獲得可行的調度，機械手在Pi執行交換操作后可能仍舊需要等待若干時間（記為ωi2）。在工序Pi，晶圓加工和停留（耗時τi）和機械手交換作業及等待（耗時γi+ωi2）重復執行。分別用?i、?iL、?iU表示工序Pi（i∈）的生產周期及其下界和上界, 則有

移除式（1）～（3）中的機械手等待時間ωi2,可得工序Pi（i∈）的自然負載（用φi表示）及其上、下界（分別用φiU、φiL表示）, 則有

在每個作業循環中，機械手執行一系列相同序列的常規作業（即裝載、卸載、交換）和等待。因此，機械手的生產周期?r由常規作業和等待兩個部分構成。用?t和?w分別表示機械手在一個作業循環內執行常規作業和等待耗費的時間。為推導?r的計算方法，我們需要分析機械手在每個作業循環內的調度機制。基于交換策略，機械手在每個作業循環訪問的工序順序為：P0→P1→P2→···→Ph-1→Ph→Ph+1。因此，穩態時機械手在每個作業循環執行的作業序列為: 從工序P0卸載（耗時ρ0） 一枚待加工晶圓 → 運送（耗時θ0）晶圓至工序P1→ 在工序P1處等待（耗時ω11） → 在工序P1執行交換作業并等待（耗時γ1+ω12） → 移動（耗時θ1）至工序P2→ 在工序P2等待（耗時ω21）→ 在工序P2執行交換作業并等待（耗時γ2+ω22） → ··· → 移動（θh-2）至工序Ph-1→ 在工序Ph-1等待（耗時ω（h-1）1） →在工序Ph-1執行交換作業并等待（耗時γh-1+ω（h-1）2） →移動（耗時θh-1）至工序Ph→ 在工序Ph等待（耗時ωh1） → 在工序Ph執行交換作業并等待（耗時γh+ωh2） → 移動（耗時θh）至工序Ph+1→ 裝載（耗時ρh+1）完成加工的晶圓進入工序Ph+1。因此，可知采用交換策略的特征雙臂組合設備的機械手生產周期為

其中

2.3 可調度性分析與調度

穩態時，機械手在每個作業循環中重復相同的任務序列。機械手完成一個作業循環時，一枚晶圓完成所有加工并返回真空鎖。在每個機械手作業循環中，每道工序完成一枚晶圓的加工，這意味著機械手的生產周期與系統的生產周期必然相同。為確保穩定的晶圓加工，晶圓在每道工序內的駐留時間必須保持一致。因此，在穩態時，每道工序的生產周期與機械手和系統的生產周期必須保持一致。特征雙臂組合設備的生產周期記為?d，則在穩態時有

由上式可知，當設備運行在穩態時,必然有

但是，我們無法通過系統設定參數直接獲知這一結果。然而，我們可以通過工序自然負載和機械手常規任務時間的參數分布特點（即[φiL,φiU],i∈ Nh,?t）來予以分析。為保證調度的可行性，晶圓在PM 內的駐留時間（即τi,i∈ Nh）必須落于區間[αi,αi+βi]，使得?iL≤?i≤?iU成立。因此，設備調度可行性判定的關鍵在于τi的分布特點及計算, 而由式（1）和式（10）可知：

通過式（4）～式（7），可以分析[φiL,φiU]和?t的變動機制，進而推測設備在運行在穩態時是否滿足晶圓駐留時間約束。因此，由已知系統參數可推知[?iL,?iU]和?r的參數分布特點。令φUmin= min{φiU,i∈}，φLmax= max{φiL,i∈},= {i|i∈,φiU＜φLmax},，則有如下定理。

定理1 對于具有晶圓駐留時間約束的特征雙臂組合設備，若[φiL,φiU] ≠ ?，且?t≤φUmin，則設備可以調度；否則，設備不可調度。

證畢

證畢

綜合作業時間分析和可調度性判定，對于考慮晶圓駐留時間約束的特征雙臂組合設備，穩態時的1-晶圓周期調度求解可歸結為如下算法：

?

3 雙臂組合設備群調度

3.1 特征轉換

第2 節引入了特征雙臂組合設備，相比傳統雙臂組合設備，前者PM 的數量可能大于6，并且機械手在各工序的任務時間不一定相同。一臺雙臂組合設備群由多個SCT 組成，故雙臂組合設備群中配置的PM 數量也可能大于6。另外，雙臂組合設備群中各SCT 的機械手任務時間明顯不一定相同。從一個整體的視角來看，雙臂組合設備群的上述兩種特征，與特征雙臂組合設備具備相當程度的相似性?？梢圆扇∧撤N方法將雙臂組合設備群轉化為特征雙臂組合設備。將雙臂組合設備群中的工序分為規范工序和協調工序，前者為執行晶圓加工的工序，后者指執行晶圓輸入、輸出和存儲的工序。 Sn和Sr分別表示雙臂組合設備群中規范工序和協調工序的集合,則有令Ci的規范工序數量為nci，則有。

首先將雙臂組合設備群的規范工序沿晶圓加工路徑 R重新編號。然后，將雙臂組合設備群對應工序的晶圓加工參數傳遞給轉換后的特征雙臂組合設備。最后，確定機械手在雙臂組合設備群任意模塊間傳遞晶圓的運動機制，即所需時間。當機械手在任意兩個不同模塊間傳遞晶圓時，有兩種情形需要考慮。當兩模塊間不含有協調工序時，則僅需傳遞雙臂組合設備群的源參數給特征雙臂組合設備即可。若兩模塊間含有協調工序，則機械手運送晶圓所需時間必須考慮在協調工序的轉運時間（包括運送、裝載、卸載時間）。綜上，具體轉換過程如下：

步驟1 沿路徑 R 重置雙臂組合設備群的工序編號：Pij→Pi；

步驟2 傳遞設備群工序的晶圓加工參數至重編號后的特征設備工序: {αij,βij,ρci,γci} → {αi,βi,ρi,γi}；

步驟3 確定機械手運送晶圓至不同規范工序所需時間θi。

3.2 調度算法

從上一節的分析可知，雙臂組合設備群可以通過特征轉換的方式轉換為特征雙臂組合設備。此時，雙臂組合設備群的調度問題即可轉變為特征雙臂組合設備的調度問題。綜合前文的相關分析，雙臂組合設備群穩態調度的求解過程可分為三個階段：① 將雙臂組合設備群轉化為特征雙臂組合設備；② 求解轉化后的特征雙臂組合設備可行穩態調度；③ 通過特征轉換的逆變換操作設定雙臂組合設備群的機械手等待時間。求解過程可歸結為如下算法：

?

4 例子

為說明本文所提方法的有效性，本節給出兩個算例。其中，晶圓加工參數的單位為s。

例1 如圖3 所示線性雙臂組合設備群，其加工參數如下:C1=（α11，β11;α12，β12;α13，β13;ρc1，θc1，γc1）=（144 s，18 s; 0 s，+∞; 154 s，15 s; 4 s，2 s，12s）；C2=（α21，β21;α22，β22;α23，β23;ρc2，θc2，γc2）=（130 s，21 s; 0 s，+∞; 148 s，16 s; 5 s，2 s，14 s）；C3=（α31，β31;α32，β32;α33，β33;ρc3，θc3，γc3）=（156 s，14 s; 140 s，20 s; 162 s，12 s; 4 s，1 s，10 s）。

圖3 線性組合設備群

對于本例，h= 2 + 2 +3 = 7。規范工序重編號為：P10→P0（P8），P11→P1，P21→P2，P31→P3，P32→P4，P33→P5，P23→P6，P13→P7。此時，設備加工參數可重置為：α1=α11= 144 s，α2=α21=130 s，α3=α31= 156 s，α4=α32= 140 s，α5=α33=162 s，α6=α23= 148 s，α7=α13= 154 s；β1=β11= 18 s，β2=β21= 21 s，β3=β31= 14 s，β4=β32= 20 s，β5=β33=12 s，β6=β23= 16 s，β7=β13= 15 s；γ1=γc1= 12 s，γ2=γc2= 14 s，γ3=γ4=γ5=γc3= 10 s，γ6=γc2= 14 s，γ7=γc1= 12 s；ρ0=ρ8=ρc1= 4 s；θ0=θ7=θc1= 2 s，θ1=θc1+ρc1+ρc2+θc2= 13 s，θ2=θc2+ρc2+ρc3+θc3= 12 s，θ3=θ4= 1s，θ5=θc3+ρc3+ρc2+θc2= 12s，θ6=θc2+ρc2+ρc1+θc1= 13 s。

隨后，則有φ1L= 156 s，φ1U= 174 s，φ2L= 144 s，φ2U= 165 s，φ3L= 156 s，φ3U= 180 s，φ4L= 150 s，φ4U= 170 s，φ5L= 172 s，φ5U= 184 s，φ6L= 164 s，φ6U=180 s，φ7L= 162 s，φ7U= 177 s，φLmax= 172 s，φUmin=165 s，因此，?t＜φUmin＜φLmax，由定理2 可知，設備可以調度。根據算法2 可求得?d=φLmax= 172 s，ω12=ω21=ω31=ω32=ω41=ω51=ω52=ω61=ω62=ω71=ω72= 0 s，ω22=φLmax-φ2U= 7 s，ω42=φLmax-φ4U= 2 s，ω11=φLmax-?t-ω22-ω42= 7 s。進而，可知設備的穩態調度為：?m=?d= 172 s,ω111=ω11= 17 s，ω112=ω12= 0 s，ω131=ω71= 0 s，ω132=ω72= 0 s，ω211=ω21=0 s，ω212=ω22= 7 s，ω231=ω61= 0 s，ω232=ω62= 0 s，ω311=ω31= 0 s，ω312=ω32= 0 s，ω321=ω41= 0 s，ω322=ω42= 2 s，ω331=ω51= 0 s，ω332=ω52= 0 s。調度甘特圖如圖4 所示。

圖4 算例1 調度甘特圖

例2 如圖5 所示樹形雙臂組合設備群，其加工參數如下:C1=（α11，β11;α12，β12;α13，β13;ρc1，θc1，γc1）=（172 s，15 s; 0 s，+∞; 185 s，10 s; 3 s，1 s，8 s）；C2=（α21，β21;α22，β22;α23，β23;ρc2，θc2，γc2）=（0 s，+∞ s; 0 s，+∞; 156 s，23 s; 5 s，3 s，15 s）；C3=（α31，β31;α32，β32;ρc3，θc3，γc3）=（179 s，19 s;168 s，20 s; 5 s，2 s，12 s），C4=（α41，β41;α42，β42;ρc4，θc4，γc4）=（163 s，25 s; 180 s，16 s; 4 s，2 s，10 s）。

圖5 樹形組合設備群

對于本例，h=nc1+nc2+nc3+nc4= 2 + 1 + 2 + 2 = 7。規范工序重編號為：P10→P0（P8），P11→P1，P31→P2，P32→P2，P41→P4，P42→P5，P23→P6，P13→P7。此時，設備加工參數可重置為：α1=α11= 172 s，α2=α31= 179 s，α3=α32= 168 s，α4=α41= 163 s，α5=α42= 180 s，α6=α23= 156 s，α7=α13= 185 s；β1=β11=15 s，β2=β31= 19 s，β3=β32= 20 s，β4=β41= 15 s，β5=β42= 16 s，β6=β23= 23 s，β7=β13= 10 s；γ1=γc1=8 s，γ2=γ3=γc3= 12 s，γ4=γ5=γc4= 10 s，γ6=γc2=15 s，γ7=γc1= 8 s；ρ0=ρ8=ρc1= 3 s；θ0=θ7=θc1= 1 s，θ1=θc1+ρc1+ρc2+θc2+ρc3+θc3= 24 s，θ2=θc3= 2 s，θ3=θc3+ρc3+ρc2+θc2+ρc2+ρc4+θc4= 26 s，θ4=θc4=2 s，θ5=θc4+ρc4+ρc2+θc2= 14 s，θ6=θc2+ρc2+ρc1+θc1= 12 s。

隨后有φ1L= 180 s，φ1U= 195 s，φ2L= 191 s，φ2U=210 s，φ3L= 180 s，φ3U= 200s，φ4L= 173 s，φ4U= 188 s，φ5L= 190 s，φ5U= 206 s，φ6L= 171 s，φ6U= 194 s，φ7L=193 s，φ7U= 203 s，φLmax= 193 s，φUmin= 194 s，?t=因此，?，?t＜φLmax＜φUmin，由定理1 可知，設備可以調度。根據算法2 可求得?d=φLmax= 193 s，ω11=φLmax-?t=30 s，ω12=ω21=ω31=ω32=ω41=ω41=ω51=ω52=ω61=ω62=ω71=ω72= 0 s。進而，可知設備的穩態調度為：?m=?d= 193 s,ω111=ω11= 30 s，ω112=ω12= 0 s，ω131=ω71= 0 s，ω132=ω72= 0 s，ω231=ω61= 0 s，ω232=ω62=0 s，ω311=ω21= 0 s，ω312=ω22= 0 s，ω321=ω31= 0 s，ω322=ω32= 0 s，ω411=ω41= 0 s，ω411=ω41= 0 s，ω412=ω42= 0 s，ω421=ω51= 0 s，ω422=ω52= 0 s。調度甘特圖如圖6 所示。

圖6 算例2 調度甘特圖

通過上述兩個實例不難發現，本文提出的雙臂組合設備群的穩態周期調度求解方法為多項式方法。一旦判定系統可以調度，算法可以高效地求得可行的穩態周期調度?，F有針對雙臂組合設備群調度問題的研究[7-11]，重點關注線性設備群的調度優化問題，而本文提出的方法可以在一個統一的框架下處理線性和樹形設備群的調度問題。從計算開銷來看，文獻[7-9]只適合求解中小規模問題。文獻[10-11]雖然給出了對應的多項式求解算法，但算法涉及迭代過程，略顯復雜。表1 總結了現有雙臂組合設備群的研究工作，不論是從可處理的設備類型還是調度求解的復雜性上看，本文所提方法均有良好的表現。

表1 現有雙臂組合設備群研究工作比較

5 結語

本文研究了半導體芯片制造中考慮晶圓駐留時間約束的雙臂組合設備群調度控制問題，提出了一種基于特征轉換的調度控制方法。該方法建立了一個統一的控制框架，采用一種全新的視角調度雙臂組合設備群。突破了現有研究對于雙臂組合設備群拓撲結構的依賴，有效地降低了調度計算復雜度和機械手協調難度。本文僅考慮了晶圓駐留時間約束，下一步的工作將考慮PM 故障、時變加工、重入加工等更為復雜條件下的調度優化問題。