基于earliest調(diào)度策略對帶駐留時(shí)間約束單臂組合設(shè)備的暫態(tài)分析

胡 勛，伍乃騏，喬 巖

（廣東工業(yè)大學(xué)機(jī)電工程學(xué)院，廣東廣州 510006）

0 引言

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

圖1 單臂組合設(shè)備

為了調(diào)度組合設(shè)備，許多學(xué)者在建模和對系統(tǒng)執(zhí)行評估做了很多工作[1-2]?；谶@些研究發(fā)現(xiàn)，在穩(wěn)態(tài)下，當(dāng)機(jī)械手有空閑時(shí)間時(shí)，加工模塊的加工時(shí)間決定系統(tǒng)的生產(chǎn)周期，當(dāng)機(jī)械手一直忙的時(shí)候，系統(tǒng)的生產(chǎn)節(jié)拍由機(jī)械手的活動時(shí)間決定。在一臺組合設(shè)備中，僅僅當(dāng)一個(gè)晶圓載入到加工模塊中，加工模塊才開始加工晶圓。因此，加工模塊的活動跟隨著機(jī)械手的任務(wù)[3]。這樣，調(diào)度組合設(shè)備的關(guān)鍵在于調(diào)度機(jī)械手的任務(wù)。眾所周知，組合設(shè)備中機(jī)械手從一個(gè)加工模塊移動到另一個(gè)加工模塊的時(shí)間可以看作為常數(shù)，并且比晶圓的加工時(shí)間短很多[4]。這樣，對于單臂組合設(shè)備拉式調(diào)度是最優(yōu)的[5-6]。然而，以上的研究結(jié)果都是基于假設(shè)晶圓加工完成后可以在加工模塊中停留無限長的時(shí)間。

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

接下來文章主要介紹Petri網(wǎng)建模?；诖薖etri網(wǎng)模型，第二部分分析了系統(tǒng)進(jìn)入穩(wěn)態(tài)后機(jī)械手的等待時(shí)間分布。第三部分給出了實(shí)例驗(yàn)證了本文得出的結(jié)論。第四部分對文章進(jìn)行了總結(jié)。

1 Petri網(wǎng)建模

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

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

圖2 有n個(gè)加工模塊的單臂組合設(shè)備Petri網(wǎng)模型

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

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

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

通過定義1，強(qiáng)迫Petri基于拉式策略運(yùn)行。下面我們展示采用拉式策略的單臂組合設(shè)備的運(yùn)行過程。穩(wěn)態(tài)時(shí)一定有狀態(tài)為M（pi）=mi，i ? Nn，M（r）=1，接著系統(tǒng)的運(yùn)行過程如：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，這樣系統(tǒng)走完一個(gè)周期?；诶讲呗裕到y(tǒng)不斷的周期性重復(fù)以上的運(yùn)行過程。

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

2 基于Earliest調(diào)度策略，機(jī)械手等待時(shí)間的分布規(guī)律

Earliest調(diào)度策略是指：（1）機(jī)械手到達(dá)加工模塊卸載晶圓時(shí)，如果加工模塊中的晶圓已經(jīng)加工好，那么機(jī)械手立即將其卸載下來；（2）機(jī)械手到達(dá)加工模塊卸載晶圓時(shí)，如果加工模塊中的晶圓還沒加工好，那么機(jī)械手在此等待，一旦晶圓加工好，機(jī)械手立即將其卸載下來；（3）機(jī)械手拿著待加工的晶圓來到加工模塊時(shí)，如果該加工模塊是空的，立即將其載入加工模塊中。暫態(tài)是指組合設(shè)備所有加工模塊中從沒有加工晶圓開始，機(jī)械手將晶圓一個(gè)個(gè)的載入到組合設(shè)備中，到所有的加工模塊都有加工晶圓并最終組合設(shè)備進(jìn)入穩(wěn)態(tài)運(yùn)行的過程。

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

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

第i道工序完成一個(gè)晶圓允許的最長時(shí)間為：

第一道工序完成一個(gè)晶圓允許的最短時(shí)間為：

第一道工序完成一個(gè)晶圓允許的最長時(shí)間為：

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

式（5）中可以發(fā)現(xiàn)2（n+1）μ+（2n+1）λ+λ0是一個(gè)常數(shù)，可令其為ψ1，而是不確定的，可令其為ψ2，所以

根據(jù)文獻(xiàn)[7]，晶圓在加工模塊的停留時(shí)間如下式：

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

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

文獻(xiàn)[7]針對帶駐留時(shí)間約束的單臂組合設(shè)備的調(diào)度問題，提出了使系統(tǒng)可調(diào)度的充分必要條件。在此基礎(chǔ)上，給出穩(wěn)態(tài)下機(jī)械手的等待時(shí)間分布規(guī)律。假設(shè)第k道工序?yàn)槠款i工序，1≤k≤n。那么有下面的定理。

定理1：對于帶駐留時(shí)間約束的單臂組合設(shè)備，基于earliest調(diào)度策略，當(dāng)系統(tǒng)到達(dá)穩(wěn)態(tài)后，等待時(shí)間ωi1=0，i?Ω和ωi=0，i=0，1，……，k-1，成立。

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

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

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

定理2：對于帶駐留時(shí)間約束的單臂組合設(shè)備，基于earliest調(diào)度策略，當(dāng)系統(tǒng)到達(dá)穩(wěn)態(tài)后，有結(jié)論：如果那么和ωi=0，d+1≤i≤n成立；如果，那么ωi=γi，i

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

到現(xiàn)在為止，分析了基于earliest調(diào)度策略，穩(wěn)態(tài)時(shí)機(jī)械手等待時(shí)間的分布情況。同時(shí)，機(jī)械手的等待時(shí)間分布可通過解析表達(dá)式計(jì)算出來，因此非常有效。

3 實(shí)例驗(yàn)證

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

基于工藝參數(shù)可以求得：ψ1=125 s，Π1L=143 s，Π2L=144 s，Π3L=128 s和 Π4L=141 s，其中第二道工序?yàn)槠款i工序?；诙ɡ?和定理2得出，穩(wěn)態(tài)時(shí)，機(jī)械手的等待時(shí)間分布為：ω02=ω12=0，ω22=19和ω32=ω42=0。通過基于eM-plant仿真，采用earliest調(diào)度策略，系統(tǒng)穩(wěn)態(tài)時(shí)機(jī)械手等待時(shí)間的分布為ω02=ω12=0，ω22=19和ω32=ω42=0。此仿真結(jié)果與基于定理1和定理2得出的結(jié)果一致，因此驗(yàn)證了本文的結(jié)論。

4 結(jié)束語

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

［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(xiàn).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.