基于earliest調度策略對帶駐留時間約束單臂組合設備的暫態分析

胡 勛，伍乃騏，喬 巖

（廣東工業大學機電工程學院，廣東廣州 510006）

0 引言

在半導體制造中，由于晶圓直徑越來越大，加工工藝復雜，組合設備被廣泛的用來加工晶圓。組合設備是一類集成制造設備。在這樣的一臺設備中，有幾個加工模塊（Processing Module，PM），一個機械手以及真空鎖（Loadlock）。機械手分為單臂機械手和雙臂機械手，如圖1所示為單臂機械手，因此叫單臂組合設備。此系統的工作過程大致如下：一批裝在一個卡盒中待加工的晶圓首先放入真空鎖中，然后由機械手從卡盒中抓取一枚晶圓放到AL中，經AL的視覺系統進行校準后，由機械手按照工藝要求將該枚晶圓依次放入相應的PM中加工，晶圓在每一個加工模塊內完成一道工序，當完成最后一道工序后，晶圓被送入CL中冷卻，避免熱的晶圓影響到真空鎖內其他的晶圓，最后晶圓被送回到真空鎖。整個過程由程序自動控制，當該批晶圓加工完成后，真空鎖中卸載，并裝入下一批晶圓。兩個真空鎖通過輪流使用實現對晶圓的裝卸作業，以保證組合裝置加工的連續性，使得系統絕大部分時間都是處在穩定運行的狀態。這樣的組合設備可以為半導體制造提供一個靈活的、可重置的和有效的環境，減小生產節拍，提高空間的利用率，降低成本。一個晶圓通過真空所進入系統，然后按照已知的加工路徑在加工模塊中加工，當所有的加工工序完成后，由機械手送回真空所。

圖1 單臂組合設備

為了調度組合設備，許多學者在建模和對系統執行評估做了很多工作[1-2]。基于這些研究發現，在穩態下，當機械手有空閑時間時，加工模塊的加工時間決定系統的生產周期，當機械手一直忙的時候，系統的生產節拍由機械手的活動時間決定。在一臺組合設備中，僅僅當一個晶圓載入到加工模塊中，加工模塊才開始加工晶圓。因此，加工模塊的活動跟隨著機械手的任務[3]。這樣，調度組合設備的關鍵在于調度機械手的任務。眾所周知，組合設備中機械手從一個加工模塊移動到另一個加工模塊的時間可以看作為常數，并且比晶圓的加工時間短很多[4]。這樣，對于單臂組合設備拉式調度是最優的[5-6]。然而，以上的研究結果都是基于假設晶圓加工完成后可以在加工模塊中停留無限長的時間。

對于一些晶圓加工工藝，例如低壓化學沉積工藝，它對晶圓在加工模塊中的滯留時間有嚴格的約束。這種約束叫晶圓駐留時間約束（residen?cy time constraint，RTC）[4]。RTC指一個晶圓在加工模塊中加工完成后，必須在規定的有限的時間內卸載出來，否則此晶圓將成為廢品。由于在加工模塊之間沒有緩沖區，使得很難調度組合設備去滿足晶圓在每個加工模塊中的駐留時間約束。這樣，為了能夠調度帶駐留時間約束的組合設備，文獻[4]提出了一些方法為雙臂組合設備找到最優的周期性調度。之后，為了提高計算有效性，伍乃騏等人分別對于單臂和雙臂組合設備提出了充分必要的可行性調度條件[2，7]。如果可調度，可通過由解析表達式組成的調度算法找到最優的周期性調度。然而在以上的研究中，并沒有給出怎么樣進入穩態調度更好。也就是說，不同文獻給出進入穩態的調度方法不一樣。這就意味著，不同進入穩態的調度方法導致不同的穩態調度方案。這樣，本文基于earliest調度策略，通過對系統暫態過程的分析，給出了系統進入穩態后，機械手的等待時間分布。

接下來文章主要介紹Petri網建模。基于此Petri網模型，第二部分分析了系統進入穩態后機械手的等待時間分布。第三部分給出了實例驗證了本文得出的結論。第四部分對文章進行了總結。

1 Petri網建模

本文用Petri網（Petri net，PN）對系統進行建模。Petri網的概念來自于文獻[8-9]，對于沒有重入加工工藝的組合設備，晶圓的加工模式可以定義為(m1，m2，…，mn)，其中n是晶圓加工步驟數目，mi是晶圓加工步驟i中所包含的加工模塊數目。

本文展示的Petri網模型中，用庫所pi表示步驟i的加工模塊并有K（pi）=mi，i ?{1，2，…，n}。將真空鎖看作一個加工步驟并稱之為步驟0，用p0表示。由于真空鎖可以容納設備中的所有晶圓，因而有K（p0）=∞。這樣，整個系統就有n+1步加工步驟。讓Ω={0，1，…，n}表示包含步驟0的步驟集，讓Nn={1，…，n}表示可加工晶圓的步驟集。機械手由庫所r表示，K(r)=1意味著機械手只有一只手臂。當庫所r中有令牌時表示機械手是空閑狀態。

圖2 有n個加工模塊的單臂組合設備Petri網模型

對于帶駐留時間約束的單臂組合設備，機械手的等待時間用來平衡加工步驟之間的工作負載。用庫所qi2和qi1表示機械手在缷載或安裝晶圓到加工步驟i之前的等待時間。模型中變遷，si1，i ? Nn，和s01分別表示機械手安裝一個晶圓到加工模塊pi和真空鎖p0中。變遷si2，i ? Nn-1，表示機械手從加工模塊pi卸載一個晶圓然后移動到加工模塊pi+1。變遷s02表示機械手從真空鎖p0下載一個晶圓然后移動到加工模塊p1。變遷sn2表示機械手從加工模塊pn中下載一個晶圓然后移動到真空鎖。yi表示機械手從第（i+2）道工序旋轉至第i道工序，yn-1表示機械手從真空所旋轉至第（n-1）道工序，yn表示機械手從第1道工序旋轉至第n道工序，y0表示機械手從第2道工序旋轉至第0道工序。圖2展示了單臂組合設備具有n個加工步驟的Petri網模型。

假設組合設備按照給定的晶圓加工流模式（m1，m2，…，mn）對晶圓進行加工，穩態時系統達到最大產能時有個晶圓同時在系統中加工。所以，讓初始狀態M0為M0（pi）=mi，i ? Nn，M0（r）=1來表示機械手為空，讓M0（p0）=n表示系統中總有晶圓可被載入到系統中。為了避免圖2中的Petri網模型死鎖，給出讓Petri網避免死鎖的控制策略。

定義1[2]：在標識M下，如果M（pi+1）=mi+1-1 ，則變遷yi，i ? Nn-1∪{0}，是可觸發的；如果M（pi）=mi，i ? Nn，則變遷yn是可觸發的。

通過定義1，強迫Petri基于拉式策略運行。下面我們展示采用拉式策略的單臂組合設備的運行過程。穩態時一定有狀態為M（pi）=mi，i ? Nn，M（r）=1，接著系統的運行過程如：yn→qn2→sn2→q01→s01→yn-1→q(n-1)2→s(n-1)2→qn1→sn1→yn-2→q(n-2)2→s(n-2)2→q(n-1)1→s(n-1)1→yn-3→…→q12→s12→q21→s21→y0→q02→s02→q11→s11→yn，這樣系統走完一個周期。基于拉式策略，系統不斷的周期性重復以上的運行過程。

為了解決該系統的調度問題，需將系統的活動時間與系統的Petri網模型聯系起來。令機械手每次的運動時間為μ，機械手從ρ0卸載一枚晶圓的時間為λ0，而在其他步驟中卸載或安裝晶圓的時間均為λ。這樣，有激活變遷yi，i ?Ω，需要μ個單位時間，激活變遷si1，i ?Ω，需要λ個單位時間，激活si2，i ? Nn，需要λ+μ個單位時間，激活s02需要λ0+μ個單位時間。用ai表示晶圓在加工模塊中的加工時間。由于考慮駐留時間約束，這樣用δi表示這樣的約束，即：晶圓在第i步加工完后，需要在δi個單位時間內移走，否則將變為廢品。用ωi1和ωi2分別表示機械手在庫所qi1和qi2中的等待時間。這樣就完成了對單臂組合設備的Petri網建模。

2 基于Earliest調度策略，機械手等待時間的分布規律

Earliest調度策略是指：（1）機械手到達加工模塊卸載晶圓時，如果加工模塊中的晶圓已經加工好，那么機械手立即將其卸載下來；（2）機械手到達加工模塊卸載晶圓時，如果加工模塊中的晶圓還沒加工好，那么機械手在此等待，一旦晶圓加工好，機械手立即將其卸載下來；（3）機械手拿著待加工的晶圓來到加工模塊時，如果該加工模塊是空的，立即將其載入加工模塊中。暫態是指組合設備所有加工模塊中從沒有加工晶圓開始，機械手將晶圓一個個的載入到組合設備中，到所有的加工模塊都有加工晶圓并最終組合設備進入穩態運行的過程。

根據文獻[7]，設τi表示第i道工序的晶圓在加工模塊中的停留時間，如果晶圓在第i道工序滿足駐留時間約束，那么τi?[ai，ai，+δi]。根據圖2中的Petri網模型，第i步完成一個晶圓需要經過以下過程：觸發si2（λ+μ）→觸發si+1（λ）→觸發yi-1（μ）→機械手在第i-1步等待（ω（i-1）2）→觸發s(i-1)2（λ+μ）→觸發sil（λ）→晶圓在第i步加工（τi）→觸發si2（λ+μ）。則該過程所需時間為

ρi=τi+4λ+3μ+ω（i-1）2。這樣，考慮并行模塊，第i道工序完成一個晶圓允許的最短的時間為：

第i道工序完成一個晶圓允許的最長時間為：

第一道工序完成一個晶圓允許的最短時間為：

第一道工序完成一個晶圓允許的最長時間為：

在圖2的Petri網模型中，分析機械手走過一個周期的活動路徑及時間：觸發yn（μ）→機械手在qn步等待（ωn）→觸發sn2（λ+μ）→觸發s01（λ）→觸發yn-1（μ）→機械手在qn-1步等待（ωn-1）→觸發s（n-1）2（λ+μ）→觸發sn1（λ）→…→觸發yi（μ）→機械手在qi步等待ωi→觸發Si2（λ+μ）→觸發s(i+1)1（λ）→觸發yi-1（μ）→機械手在q(i-1)2步等待(ω(i-1)2）觸發s(i-1)2（λ+μ）→觸發si1（λ）→…→觸發y1（μ）→機械手在q12步等待（ω1）→觸發s12（λ+μ）→觸發s21（λ）→觸發y0（μ）→機械手在q02步等待（ω02）→觸發s02（λ0+μ）→觸發s11（λ）→再次觸發yn（μ），這樣一個周期完成，若令機械手的節拍為ψ，可得到：

式（5）中可以發現2（n+1）μ+（2n+1）λ+λ0是一個常數，可令其為ψ1，而是不確定的，可令其為ψ2，所以

根據文獻[7]，晶圓在加工模塊的停留時間如下式：

引理1：對于帶駐留時間約束的單臂組合設備，當所有的加工模塊都有晶圓在加工時，有θi=ψ，i ? Nn。

讓ΠiL和ΠiU分別表示第i道工序允許生產節拍的上限和下限，那么有:

文獻[7]針對帶駐留時間約束的單臂組合設備的調度問題，提出了使系統可調度的充分必要條件。在此基礎上，給出穩態下機械手的等待時間分布規律。假設第k道工序為瓶頸工序，1≤k≤n。那么有下面的定理。

定理1：對于帶駐留時間約束的單臂組合設備，基于earliest調度策略，當系統到達穩態后，等待時間ωi1=0，i?Ω和ωi=0，i=0，1，……，k-1，成立。

證明：根據拉式調度策略，當機械手拿著待加工的晶圓來到第i步時，第i步一定為空。這樣根據earliest調度策略定義，機械手可以立即將此晶圓載入第i步中，即ωi1=0。因為真空鎖總有待加工的晶圓，這樣當機械手來到真空鎖可立即將其中的晶圓卸載出一個，所以有ω02=0。根據拉式調度策略，當機械手來到第一步時，其一定已經在瓶頸工序第k步完成一系列的機械手活動，這樣此時該系統的周期由瓶頸工序決定，即為ΠkL。這樣由引理1和式子（8）可得τ1=m1×ΠkL-（3λ+λ0+3μ+ω0）=m1×ΠkL-（3λ+λ0+3μ)≥m1×Π1L-（3λ+λ0+3μ）=a1，所以當機械手來到第1步卸載晶圓時，第1步中的晶圓已經加工好了。因此機械手可以立刻將其中的晶圓卸載出來，同時不需要等待，即ω1=0。當機械手來到第2步時，同理由引理1和式子（7）τ2=m2×ΠkL-（4λ+3μ+ω1）=m2×ΠkL-（4λ+3μ≥

m2×Π2L-（4λ+3μ）=a2，所以當機械手來到第2步卸載晶圓時，第2步中的晶圓已經加工好了。因此機械手可以立刻將其中的晶圓卸載出來，同時不需要等待，即ω2=0。相似的，可推出ω3=ω4=…=ωk-1=0。因此定理1成立。

根據文獻[10]，可知機械手在qi2中的等待時間是有上界的，否則此等待時間將會影響系統的最優性。讓γi表示可分配到庫所qi2最大的等待時間，這樣有γi-1=mi×ΠkL-（ai+4λ+3μ），1≤i≤n和ωn?[0，∞]成立[10]。

定理2：對于帶駐留時間約束的單臂組合設備，基于earliest調度策略，當系統到達穩態后，有結論：如果那么和ωi=0，d+1≤i≤n成立；如果，那么ωi=γi，i

證明：根據定理1可知，ωi1=0，i ?Ω 和ωi2=0，i=0，1，…，k-1，成立。假設機械手在第k步的等待時間ωk2>γk2，根據引理1和式子（7）有τk+1=mk+1×ΠkL-（4λ+3μ+ωk）ak+1，根據earliest調度策略，這就暗示著不斷減小同時 ωk2不斷增加并且。直到當ωk2=γk2時，有τk+1=mk+1×ΠkL-（4λ+3μ+ωk2）=ak+1，這時根據earliest調度策略，ωk2此時不再增加。同理可以得到，如果那么ωk2=γk2，k≤i

到現在為止，分析了基于earliest調度策略，穩態時機械手等待時間的分布情況。同時，機械手的等待時間分布可通過解析表達式計算出來，因此非常有效。

3 實例驗證

一臺組合設備有四道加工工序，其中第三道工序有兩個并行加工模塊，而其他工序只有一個加工模塊。每道工序的加工時間分別為：a1=92 s，a2=98 s，a3=210 s，a4=95 s。機械手的活動時間分別為：λ=10 s，λ0=15 s，μ=2 s。

基于工藝參數可以求得：ψ1=125 s，Π1L=143 s，Π2L=144 s，Π3L=128 s和 Π4L=141 s，其中第二道工序為瓶頸工序。基于定理1和定理2得出，穩態時，機械手的等待時間分布為：ω02=ω12=0，ω22=19和ω32=ω42=0。通過基于eM-plant仿真，采用earliest調度策略，系統穩態時機械手等待時間的分布為ω02=ω12=0，ω22=19和ω32=ω42=0。此仿真結果與基于定理1和定理2得出的結果一致，因此驗證了本文的結論。

4 結束語

半導體加工是極復雜的制造系統，它的調度問題非常復雜。本文對基于earliest調度策略的帶駐留時間約束的單臂組合設備的暫態過程進行了分析，運用Petri網模型得出了系統達到穩態后機械手的等待時間分布情況，并且此分布可通過解析表達式計算得出，因此非常有效。基于以上成果，今后將著重研究基于earliest調度策略多組合設備到達穩態時機械手的等待時間分布情況。

［1］J.Yi，S.Ding，M.Zhang.Steady-state throughput and scheduling analysis of multi-cluster tools：A decomposi?tion approach［J］.IEEE Trans.Automation Sci.Eng.，Apr，2008，5（2）：321-336.

［2］N.Q.Wu，M.C.Zhou.A closed-form solution for schedu?lability and optimal scheduling of dual-arm cluster tools with wafer residency time constraint based on steady schedule analysis［J］.IEEE Transactions on Automa?tion Science and Engineering，2010，7（2）：303-315.

［3］Y.-H.Shin，T.-E.Lee，J.-H.Kim，et al.Modeling and implementing a real-time scheduler for dual-armed cluster tools［J］.Computers In Industry，2001，45（1）：13-27.

［4］J.-H.Kim，T.-E.Lee，H.-Y.Lee，et al.Scheduling analysis of timed-constrained dual-armed cluster tools［J］.IEEE Transactions on Semiconductor Manufactur?ing，2003，16（3）：521-534.

［5］T.-E.Lee，H.-Y.Lee，Y.-H.Shin.Workload balanc?ing and scheduling of a single-armed cluster tool［A］.Proceedings of the 5th APIEMS Conference［C］，Gold Coast，Australia.2004：1-15.

［6］M.-J.Lopez，S.-C.Wood.Systems of multiple cluster tools- configuration， reliability， and performance［J］.IEEE Transactions on Semiconductor Manufactur?ing，2003，16（2）：170-178.

［7］N.Q.Wu，C.B.Chu，F.Chu，et al.A Petri net method for schedulability and scheduling problems in single-arm cluster tools with wafer residency time constraints［J］.IEEE Transactions on Semiconductor Manufacturing，2008，21（2）：224-237.

［8］M.C.Zhou，K.Venkatesh.Modeling，simulation and control of flexible manufacturing systems［A］.Petri net approach，World Scientific，Singapore，1998.

［9］T.Murata.Petri nets：Properties，analysis and applica?tions［A］.Proceedings of the IEEE［C］.1989，77（4）：541-580.

［10］Y.Qiao，N.Q.Wu，M.C.Zhou.Real-time scheduling of single-arm cluster tools subject to residency time con?straints and bounded activity time variation［J］.IEEE Transactions on Automation Science and Engineering，2012，9（3）：564-577.