考慮晶圓駐留時間約束的雙臂組合設(shè)備群調(diào)度*

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

（①河南工業(yè)大學(xué)漯河工學(xué)院，河南 漯河 462000；②湖北工業(yè)大學(xué)機(jī)械工程學(xué)院，湖北 武漢 430068；③湖北工業(yè)大學(xué)現(xiàn)代制造質(zhì)量工程湖北省重點實驗室，湖北 武漢 430068）

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

圖1 線性雙臂組合設(shè)備群

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

除了設(shè)備的拓?fù)浣Y(jié)構(gòu)外，BM 容量和機(jī)械手構(gòu)成形式亦對組合設(shè)備群的調(diào)度具有重要影響。 Yang F J 等[12]研究了BM 容量為2 的線性單臂組合設(shè)備群調(diào)度問題，提出了有效且易于實施的算法求解1-晶圓周期調(diào)度。李文濤等[13]修改Petri 網(wǎng)模型的初始標(biāo)識，促使系統(tǒng)加速進(jìn)入穩(wěn)態(tài)，提出了有效的調(diào)度策略。黃鵬等[14]研究了BM 容量為2 的樹形單臂組合設(shè)備群的優(yōu)化調(diào)度問題，提出了最優(yōu)1-晶圓周期調(diào)度求解算法。針對處于加工臨界的線性單臂組合設(shè)備群，Bai L P 等[15]深入分析了BM 配置方式對系統(tǒng)調(diào)度的影響機(jī)理，給出了周期時間下界可達(dá)的BM 最優(yōu)配置方法。Yang F J 等[16-18]證明線性混合組合設(shè)備群存在1-晶圓周期調(diào)度，并給出了不同約束條件下的最優(yōu)1-晶圓周期調(diào)度求解方法。對于樹形混合組合設(shè)備群，Yang F J 等[19-20]給出了最優(yōu)1-晶圓周期調(diào)度方法。

綜合前文所述，現(xiàn)有組合設(shè)備群調(diào)度控制的研究重點在于單臂組合設(shè)備群和混合組合設(shè)備群，而對于生產(chǎn)效率更高的雙臂組合設(shè)備群，鮮有研究給予關(guān)注。此外，現(xiàn)有工作局限于特定拓?fù)浣Y(jié)構(gòu)的組合設(shè)備群，尚未有研究統(tǒng)一考慮線性和樹形設(shè)備的調(diào)度問題。鑒于上述原因，本文對考慮晶圓駐留時間約束的雙臂組合設(shè)備群調(diào)度問題開展研究。首先引入特征雙臂組合設(shè)備并研究其穩(wěn)態(tài)調(diào)度問題，隨后采用特征轉(zhuǎn)換方法將線性或樹形雙臂組合設(shè)備群轉(zhuǎn)換為特征雙臂組合設(shè)備，然后根據(jù)轉(zhuǎn)換后的特征雙臂組合設(shè)備求解雙臂組合設(shè)備群的穩(wěn)態(tài)調(diào)度，最后通過算例驗證所提方法的可行性和有效性。

1 問題描述

1.1 基本假設(shè)

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

1.2 符號設(shè)定

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

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

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

2 特征雙臂組合設(shè)備及其調(diào)度

2.1 特征雙臂組合設(shè)備

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

圖2 傳統(tǒng)雙臂組合設(shè)備與特征雙臂組合設(shè)備的結(jié)構(gòu)

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

2.2 作業(yè)時間分析

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

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

在每個作業(yè)循環(huán)中，機(jī)械手執(zhí)行一系列相同序列的常規(guī)作業(yè)（即裝載、卸載、交換）和等待。因此，機(jī)械手的生產(chǎn)周期?r由常規(guī)作業(yè)和等待兩個部分構(gòu)成。用?t和?w分別表示機(jī)械手在一個作業(yè)循環(huán)內(nèi)執(zhí)行常規(guī)作業(yè)和等待耗費(fèi)的時間。為推導(dǎo)?r的計算方法，我們需要分析機(jī)械手在每個作業(yè)循環(huán)內(nèi)的調(diào)度機(jī)制?；诮粨Q策略，機(jī)械手在每個作業(yè)循環(huán)訪問的工序順序為：P0→P1→P2→···→Ph-1→Ph→Ph+1。因此，穩(wěn)態(tài)時機(jī)械手在每個作業(yè)循環(huán)執(zhí)行的作業(yè)序列為: 從工序P0卸載（耗時ρ0） 一枚待加工晶圓 → 運(yùn)送（耗時θ0）晶圓至工序P1→ 在工序P1處等待（耗時ω11） → 在工序P1執(zhí)行交換作業(yè)并等待（耗時γ1+ω12） → 移動（耗時θ1）至工序P2→ 在工序P2等待（耗時ω21）→ 在工序P2執(zhí)行交換作業(yè)并等待（耗時γ2+ω22） → ··· → 移動（θh-2）至工序Ph-1→ 在工序Ph-1等待（耗時ω（h-1）1） →在工序Ph-1執(zhí)行交換作業(yè)并等待（耗時γh-1+ω（h-1）2） →移動（耗時θh-1）至工序Ph→ 在工序Ph等待（耗時ωh1） → 在工序Ph執(zhí)行交換作業(yè)并等待（耗時γh+ωh2） → 移動（耗時θh）至工序Ph+1→ 裝載（耗時ρh+1）完成加工的晶圓進(jìn)入工序Ph+1。因此，可知采用交換策略的特征雙臂組合設(shè)備的機(jī)械手生產(chǎn)周期為

其中

2.3 可調(diào)度性分析與調(diào)度

穩(wěn)態(tài)時，機(jī)械手在每個作業(yè)循環(huán)中重復(fù)相同的任務(wù)序列。機(jī)械手完成一個作業(yè)循環(huán)時，一枚晶圓完成所有加工并返回真空鎖。在每個機(jī)械手作業(yè)循環(huán)中，每道工序完成一枚晶圓的加工，這意味著機(jī)械手的生產(chǎn)周期與系統(tǒng)的生產(chǎn)周期必然相同。為確保穩(wěn)定的晶圓加工，晶圓在每道工序內(nèi)的駐留時間必須保持一致。因此，在穩(wěn)態(tài)時，每道工序的生產(chǎn)周期與機(jī)械手和系統(tǒng)的生產(chǎn)周期必須保持一致。特征雙臂組合設(shè)備的生產(chǎn)周期記為?d，則在穩(wěn)態(tài)時有

由上式可知，當(dāng)設(shè)備運(yùn)行在穩(wěn)態(tài)時,必然有

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

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

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

證畢

證畢

綜合作業(yè)時間分析和可調(diào)度性判定，對于考慮晶圓駐留時間約束的特征雙臂組合設(shè)備，穩(wěn)態(tài)時的1-晶圓周期調(diào)度求解可歸結(jié)為如下算法：

?

3 雙臂組合設(shè)備群調(diào)度

3.1 特征轉(zhuǎn)換

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

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

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

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

步驟3 確定機(jī)械手運(yùn)送晶圓至不同規(guī)范工序所需時間θi。

3.2 調(diào)度算法

從上一節(jié)的分析可知，雙臂組合設(shè)備群可以通過特征轉(zhuǎn)換的方式轉(zhuǎn)換為特征雙臂組合設(shè)備。此時，雙臂組合設(shè)備群的調(diào)度問題即可轉(zhuǎn)變?yōu)樘卣麟p臂組合設(shè)備的調(diào)度問題。綜合前文的相關(guān)分析，雙臂組合設(shè)備群穩(wěn)態(tài)調(diào)度的求解過程可分為三個階段：① 將雙臂組合設(shè)備群轉(zhuǎn)化為特征雙臂組合設(shè)備；② 求解轉(zhuǎn)化后的特征雙臂組合設(shè)備可行穩(wěn)態(tài)調(diào)度；③ 通過特征轉(zhuǎn)換的逆變換操作設(shè)定雙臂組合設(shè)備群的機(jī)械手等待時間。求解過程可歸結(jié)為如下算法：

?

4 例子

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

例1 如圖3 所示線性雙臂組合設(shè)備群，其加工參數(shù)如下: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 線性組合設(shè)備群

對于本例，h= 2 + 2 +3 = 7。規(guī)范工序重編號為：P10→P0（P8），P11→P1，P21→P2，P31→P3，P32→P4，P33→P5，P23→P6，P13→P7。此時，設(shè)備加工參數(shù)可重置為：α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 可知，設(shè)備可以調(diào)度。根據(jù)算法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。進(jìn)而，可知設(shè)備的穩(wěn)態(tài)調(diào)度為：?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。調(diào)度甘特圖如圖4 所示。

圖4 算例1 調(diào)度甘特圖

例2 如圖5 所示樹形雙臂組合設(shè)備群，其加工參數(shù)如下: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 樹形組合設(shè)備群

對于本例，h=nc1+nc2+nc3+nc4= 2 + 1 + 2 + 2 = 7。規(guī)范工序重編號為：P10→P0（P8），P11→P1，P31→P2，P32→P2，P41→P4，P42→P5，P23→P6，P13→P7。此時，設(shè)備加工參數(shù)可重置為：α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 可知，設(shè)備可以調(diào)度。根據(jù)算法2 可求得?d=φLmax= 193 s，ω11=φLmax-?t=30 s，ω12=ω21=ω31=ω32=ω41=ω41=ω51=ω52=ω61=ω62=ω71=ω72= 0 s。進(jìn)而，可知設(shè)備的穩(wěn)態(tài)調(diào)度為：?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。調(diào)度甘特圖如圖6 所示。

圖6 算例2 調(diào)度甘特圖

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

表1 現(xiàn)有雙臂組合設(shè)備群研究工作比較

5 結(jié)語

本文研究了半導(dǎo)體芯片制造中考慮晶圓駐留時間約束的雙臂組合設(shè)備群調(diào)度控制問題，提出了一種基于特征轉(zhuǎn)換的調(diào)度控制方法。該方法建立了一個統(tǒng)一的控制框架，采用一種全新的視角調(diào)度雙臂組合設(shè)備群。突破了現(xiàn)有研究對于雙臂組合設(shè)備群拓?fù)浣Y(jié)構(gòu)的依賴，有效地降低了調(diào)度計算復(fù)雜度和機(jī)械手協(xié)調(diào)難度。本文僅考慮了晶圓駐留時間約束，下一步的工作將考慮PM 故障、時變加工、重入加工等更為復(fù)雜條件下的調(diào)度優(yōu)化問題。