周炳海，劉明祥，周淑美

（同濟(jì)大學(xué)機(jī)械與能源工程學(xué)院，201804上海）

隨著300 mm晶圓制造技術(shù)的問世，集束型設(shè)備群正在被越來越廣泛地應(yīng)用于半導(dǎo)體制造過程中.目前，如何優(yōu)化半導(dǎo)體集束型設(shè)備群的調(diào)度問題，已成為提升半導(dǎo)體制造系統(tǒng)整體效率的關(guān)鍵途徑.對單個(gè)集束型設(shè)備調(diào)度的研究已比較成熟.例如 Perkinson 等［1］和 Venkatesh 等［2］對單個(gè)單臂和雙臂集束型設(shè)備穩(wěn)態(tài)下的產(chǎn)能進(jìn)行了分析，建立了單臂、雙臂集束型設(shè)備的分析模型，提出了基礎(chǔ)調(diào)度周期（fundamental period，F(xiàn)P）的計(jì)算方法，并建立了單臂機(jī)械手調(diào)度的拉動(dòng)（pull）策略和雙臂機(jī)械手的交換（SWAP）策略.

研究集束型設(shè)備群調(diào)度問題的文獻(xiàn)報(bào)道較少，已有文獻(xiàn)主要關(guān)注同種晶圓產(chǎn)品在穩(wěn)態(tài)下的調(diào)度方法.例如 Yi［3］等在不考慮機(jī)械手搬運(yùn)時(shí)間，僅僅考慮集束型設(shè)備群加工同種晶圓產(chǎn)品的情況下，對其進(jìn)行了產(chǎn)能和FP分析，給出了一種分解方法來構(gòu)建集束型設(shè)備群的FP下界，并給出了相應(yīng)的優(yōu)化調(diào)度方法.Chan［4-5］等在考慮機(jī)械手搬運(yùn)時(shí)間為非零情況下，對集束型設(shè)備群調(diào)度問題進(jìn)行了研究，構(gòu)造了一種基于資源約束的分析模型，并給出了相應(yīng)的調(diào)度方法.上述文獻(xiàn)主要關(guān)注集束型設(shè)備群在穩(wěn)態(tài)下的產(chǎn)能分析，且均沒有考慮晶圓加工過程中的晶圓在處理腔中的駐留約束現(xiàn)象.文獻(xiàn)［6-12］對帶駐留約束的單個(gè)集束型設(shè)備調(diào)度問題進(jìn)行了研究.然而Chan［4-5］等已經(jīng)指出，集束型設(shè)備群調(diào)度問題的復(fù)雜性使得現(xiàn)有的方法均不能直接推廣應(yīng)用于集束型設(shè)備群的調(diào)度問題中.文獻(xiàn)［13］對帶駐留約束的單臂集束型設(shè)備群進(jìn)行了研究，提出了一種基于時(shí)間約束集的建模與調(diào)度方法.

本文在提出虛擬緩沖模塊（virtual buffer module，VBM）概念的基礎(chǔ)上，結(jié)合時(shí)間區(qū)間集概念［14］，進(jìn)行了帶駐留約束的雙臂集束型設(shè)備群的調(diào)度問題研究.

1 問題描述

根據(jù)SEMI標(biāo)準(zhǔn)E21-96定義，一個(gè)集束型設(shè)備一般由卡匣模塊（load lock，LL）、單臂或雙臂機(jī)械手搬運(yùn)模塊（robot module，RM）以及若干個(gè)晶圓加工模塊（process module，PM）組成．LL的功能是存儲(chǔ)晶圓，RM負(fù)責(zé)完成晶圓的搬運(yùn)、裝載或卸載任務(wù)，PM負(fù)責(zé)晶圓的加工.一個(gè)集束型晶圓制造設(shè)備群通常包含多個(gè)由緩沖模塊（buffer module，BM）相互連接的集束型設(shè)備，如圖1所示，其中Ch表示第h臺(tái)單個(gè)集束型設(shè)備．

圖1 雙臂集束型設(shè)備群示意圖

為有效地描述集束型設(shè)備群調(diào)度問題，假設(shè)：①每一個(gè)集束型設(shè)備最多和兩個(gè)集束型設(shè)備連接；②兩個(gè)相鄰的集束型設(shè)備由兩個(gè)BM連接，其中一個(gè)BM用于暫存進(jìn)入集束型設(shè)備的晶圓，一個(gè)BM用于暫存離開集束型設(shè)備的晶圓，BM最多只能儲(chǔ)存一片晶圓，晶圓在BM的處理時(shí)間為0，駐留約束時(shí)間沒有限制；③所有的RM采用雙臂機(jī)械手，機(jī)械手的兩臂呈180°角放置，每次允許搬運(yùn)一片晶圓，在不同模塊間的晶圓移動(dòng)時(shí)間固定；④每個(gè)PM一次只能加工一片晶圓；⑤晶圓在PM中有駐留時(shí)間約束，即加工完成后，晶圓在PM內(nèi)駐留時(shí)間有限制，超過該時(shí)間上限，晶圓的產(chǎn)品質(zhì)量會(huì)下降，甚至?xí)兂纱纹?；⑥要調(diào)度的晶圓具有不同的晶圓流模式，也即是有不同的晶圓種類，并且晶圓允許跳過在同一個(gè)集束型設(shè)備中的某一個(gè)或幾個(gè)PM．

符號定義如下：

CTm為一個(gè)集束型設(shè)備群，其中下標(biāo)m表示這個(gè)集束型設(shè)備群中包含的單集束型設(shè)備的數(shù)目；

Ji為當(dāng)前調(diào)度的晶圓；

Ch為在該集束型設(shè)備群中的第h個(gè)集束型設(shè)備；

Rh1、Rh2分別表示第h個(gè)集束型設(shè)備的機(jī)械手的兩只手臂；

BMhj為用于連接Ch和Ch+1的緩沖模塊；

VBMhj為假設(shè)的存在于PMh（j-1）PMhj之間的虛擬的緩沖模塊；

MHL為晶圓進(jìn)入BM（h-1）2之前在Ch的實(shí)際上的最后一道工序的序號；

Mh為Ch與Ch+1連接前Ch中處理模塊的數(shù)目；

MH為Ch中的處理模塊的數(shù)目；

aihj為跳過的工序數(shù)，若晶圓沒有跳過任何工序，則aihj=0；若晶圓在PMhj或BMhj之后跳過了k個(gè)工序，則aihj=k；

tP，i，hj為Ji在工序PMhj上所需的加工時(shí)間；

tp為晶圓Ji在晶圓流模式上的各個(gè)處理模塊PMhj的加工時(shí)間的集合；

tU，i，hj為Ji在工序PMhj上最大允許駐留時(shí)間；

tu為晶圓在晶圓Ji流模式上的各個(gè)處理模塊PMhj的最大允許駐留時(shí)間的集合；

tPVB，hj為虛擬的連接存儲(chǔ)模塊VBMhj所需要的加工時(shí)間tPVB，hj=0；

tUVB，hj為用于連接的存儲(chǔ)模塊VBMhj最大允許駐留時(shí)間tUVB，hj=∞；

Ti為Ji各工序需要加工時(shí)間集合，即Ti=｛tP，i，11，tP，i，12，…，tP，i，mj，…，tP，i，14｝；

TP，i，hj為Ji在PMhj上允許停留的時(shí)間區(qū)間TP，i，hj=［tP，i，hj，tP，i，hj+tU，i，hj］；

tF，i，hj為Ji在PMhj中的實(shí)際停留時(shí)間；

tS，i，hj為Ji在PMhj中的開始時(shí)間；

tL，i，hj為Ji在PMhj中的離開時(shí)間；

t為J從Ch進(jìn)入B后的實(shí)際停留

FB，i，hjiMhj時(shí)間；

t為J從Ch進(jìn)入B中的時(shí)間；

SB，i，hjiMhj

t為J從Ch進(jìn)入B后的離開時(shí)間；

LB，i，hjiMhj

tUD為機(jī)械手卸載Ji的時(shí)間，為常數(shù)；

tLD為機(jī)械手裝載Ji的時(shí)間，為常數(shù)；

tM，i，hj為把Ji從PMh（j-1）搬運(yùn)到PMhj需要的時(shí)間，含裝卸時(shí)間，為常數(shù)tM；

tFVB，i，hj為Ji從CTm（m=1，2，…，n） 進(jìn)入虛擬的存儲(chǔ)模塊VBMhj后實(shí)際停留時(shí)間；

tSVB，i，hj為Ji從CTm（m=1，2，…，n） 進(jìn)入虛擬的存儲(chǔ)模塊VBMhj中的時(shí)間；

tLVB，i，hj為Ji從CTm（m=1，2，…，n） 進(jìn)入虛擬的存儲(chǔ)模塊VBMhj后的離開時(shí)間；

tMV，i，hj為把Ji從工序j-1 搬運(yùn)到虛擬的存儲(chǔ)模塊VBMhj需要的時(shí)間，含裝載和卸載的時(shí)間；

tTMRES，i，hj為Ji從PMhj卸載后到被裝載到下一個(gè)處理模塊之間在機(jī)械手的手臂上駐留的時(shí)間；

TTW，i，hk為K等于1 或2，表示第h個(gè)集束型設(shè)備的機(jī)械手的兩只手臂Rh2或Rh2對的可用時(shí)間區(qū)間；

TFL，i，hj為在當(dāng)前調(diào)度下，Ji在PMhj可行的結(jié)束時(shí)間區(qū)間集， 包含有?l（i，h，j） 個(gè)區(qū)間， 即有TFL，i，hj=｛TFL，i，hj，1，TFL，i，hj，2，…，TFL，i，hj，?l（i，h，j）｝ ；

TFSB，i，hj為在當(dāng)前調(diào)度下，Ji在BMhj可行的開始時(shí)間區(qū)間集，包含有?bs（i，h，j） 個(gè)區(qū)間，即有TFSB，i，hj=｛TFSB，i，hj，1，TFSB，i，hj，2，…，TFSB，i，hj，?bs（i，h，j）｝．

TPWVB，i，hj為虛擬的模塊緩沖模塊中VBMhj可用的時(shí)間區(qū)間集；

TFSVB，i，hj為在當(dāng)前調(diào)度下，用時(shí)間區(qū)間集來表示VBMhj的可行的開始存儲(chǔ)時(shí)間（tSVB，i，hj）．

由假設(shè)③可知，晶圓在任意一個(gè)PM或BM的開始時(shí)間或結(jié)束時(shí)間的差值至少大于或等于RM完成一次晶圓裝載的時(shí)間，于是可得

由假設(shè)④可知，任意一個(gè)PM或BM都不可能同時(shí)擁有兩個(gè)或兩個(gè)以上的晶圓，于是有

由于雙臂機(jī)械手采用SWAP策略，其對晶圓的移動(dòng)不是一個(gè)連續(xù)的動(dòng)作，由假設(shè)⑥可知，晶圓在晶圓流模式上相鄰的PM之間的開始時(shí)間和結(jié)束時(shí)間的關(guān)系必須滿足如下關(guān)系：

由于集束型設(shè)備群的特殊的結(jié)構(gòu)，晶圓在不同集束型設(shè)備之間的移動(dòng)必須通過BM進(jìn)行中轉(zhuǎn)，所以在約束條件（1）～（5）中應(yīng)滿足如下約束：

由假設(shè)條件⑤可知，晶圓在PM中的時(shí)間應(yīng)該大于其處理時(shí)間，于是可得

tF，i，hj≥tP，i，hj，j=1，2，…，MH，h=1，2，…，n；tF，i，hj≤tP，i，hj+tU，i，hj，j=1，2，…，MH，h=1，2，…，n；

對晶圓的搬運(yùn)必須發(fā)生在機(jī)械手的兩只機(jī)械臂中的某一個(gè)機(jī)械臂的可用的時(shí)間區(qū)間內(nèi)，于是有

晶圓在PM中的實(shí)際停留的時(shí)間區(qū)間必須在PM的某個(gè)可用時(shí)間區(qū)間內(nèi)，于是有

同理，對BM也是如此：

調(diào)度目標(biāo)是最小化晶圓加工的makespan，即

至此，在對調(diào)度問題進(jìn)行分析的基礎(chǔ)上，關(guān)于在多晶圓流模式條件下，帶有駐留約束的雙臂集束型設(shè)備群調(diào)度問題的數(shù)學(xué)模型已經(jīng)建立.

2 計(jì)算方法

首先，引入文獻(xiàn)［14］中有關(guān)時(shí)間區(qū)間集運(yùn)算的定義，具體描述如下：

定義1假設(shè)有時(shí)間區(qū)間集T=｛T1，T2，…，Tn｝ 和時(shí)間區(qū)間集S=｛S1，S2，…，Sn｝，T1，…Tn，S1，…，Sn為時(shí)間區(qū)間：1）T和S的交集，用T∩S表示；2）T和S的并集，用T∪S表示．

定義2假設(shè)有時(shí)間區(qū)間集T=｛［L1，H1］，［L2，H2］，…，［Ln，Hn］｝ 和區(qū)間Q=［a，b］：1）T和Q的和用符號T⊕Q來表示，T⊕Q=｛［L1+a，H1+b］，［L2+a，H2+b］，…，［Ln+a，Hn+b］｝；2）min和max函數(shù)分別用minT=L1和maxT=Hn來表述．

2.1 算法流程

算法的核心思想是引入VBM概念，將雙臂集束型設(shè)備群的調(diào)度問題轉(zhuǎn)化為帶有VBM的單臂集束型設(shè)備群的調(diào)度問題進(jìn)行研究．VBM的依據(jù)是基于雙臂的搬運(yùn)機(jī)械手實(shí)際上相當(dāng)于在每兩個(gè)相鄰的PM（BM）之間增加了一個(gè)BM，當(dāng)晶圓產(chǎn)生駐留約束時(shí)，機(jī)械手可以暫時(shí)存儲(chǔ)晶圓，相當(dāng)于為晶圓提供了一個(gè)BM．雙臂的機(jī)械手轉(zhuǎn)化為單臂的機(jī)械手，同時(shí)在集束型設(shè)備里的每兩個(gè)模塊之間增加了一個(gè)VBM，虛擬化處理如圖2所示．PM之間的圓圈表示為VBM．

圖2 虛擬化示意圖

基于上述核心思想，算法的流程見圖3．首先，將雙臂機(jī)械手的一個(gè)手臂虛擬為存在于相鄰的PM（BM）的VBM．這樣，帶駐留約束的雙臂集束型設(shè)備群的調(diào)度問題就轉(zhuǎn)化為相應(yīng)的帶駐留約束帶VBM的單臂集束型設(shè)備群的調(diào)度問題．最后，利用VBM上的開始和結(jié)束的時(shí)間就是晶圓在RM的其中一個(gè)機(jī)械手的開始和結(jié)束時(shí)間，結(jié)合SWAP策略，并以此為依據(jù)對此進(jìn)行修正，得到修正的SWAP調(diào)度策略，進(jìn)而完成調(diào)度.

圖3 基于SWAP策略的算法流程

2.2 各模塊的調(diào)度時(shí)間節(jié)點(diǎn)確定

針對已經(jīng)轉(zhuǎn)化后的帶有駐留約束和VBM的單臂集束型設(shè)備群調(diào)度問題，需要計(jì)算調(diào)度的時(shí)間節(jié)點(diǎn)，即晶圓在轉(zhuǎn)化后的晶圓流模式上的各個(gè)模塊（包括PM、BM、VBM和RM） 的開始和結(jié)束時(shí)間．各模塊的調(diào)度時(shí)間節(jié)點(diǎn)確定步驟如圖4所示．逆序策略為計(jì)算PM的開時(shí)間取可行時(shí)間區(qū)間的最大值；計(jì)算BM的開始時(shí)間取可行區(qū)間最小值．

圖4 各模塊的調(diào)度時(shí)間節(jié)點(diǎn)確定

具體的計(jì)算方法如下：

首先，在計(jì)算可行時(shí)間區(qū)間集部分，關(guān)于VBM的可行的開始和結(jié)束時(shí)間區(qū)間集TFSVB，i，hj和TFLVB，i，hj的計(jì)算，根據(jù)計(jì)算基于的模塊的不同，可以分為以下3種情況：

1）上一模塊是LL，即計(jì)算是基于LL的，那么計(jì)算的方法如下：

2）上一個(gè)模塊是PMhk，即計(jì)算是基于上一個(gè)PM的調(diào)度結(jié)果，那么計(jì)算方法如下：

（3） 如果上一個(gè)處理模塊是BMh′k＇，即計(jì)算是基于BM計(jì)算結(jié)果的，那么計(jì)算的方法如下：

其次，晶圓在進(jìn)入PM之前必須先“進(jìn)入”VBM，所有處理模塊的計(jì)算都是基于VBMh”k”計(jì)算結(jié)果的，其計(jì)算方法如下：

最后，關(guān)于BM的可行開始和結(jié)束時(shí)間區(qū)間的計(jì)算．與PM類似，BM的計(jì)算也都是基于相應(yīng)的VBMh”k”計(jì)算結(jié)果的，其相應(yīng)的計(jì)算公式如下：

通過上述公式，按照晶圓流模式上各模塊的順序，可以一次計(jì)算出相應(yīng)的可行和結(jié)束時(shí)間區(qū)間集．在此基礎(chǔ)上進(jìn)行調(diào)度時(shí)間點(diǎn)的計(jì)算．

首先是關(guān)于晶圓在各個(gè)VBM的開始和結(jié)束時(shí)間點(diǎn)計(jì)算，下面對幾種不同的情況進(jìn)行分析．

1）上一個(gè)模塊是用于存儲(chǔ)已加工完成的晶圓的L，則

那么晶圓的最早完工時(shí)間顯然是tLVB，i，hn+tM/2．

2）如果上一個(gè)模塊是PMhk，即計(jì)算是和上一個(gè)PM相關(guān)聯(lián)的，則

3） 如果上一個(gè)模塊是BMh′k′，即計(jì)算是和上一個(gè)BM相關(guān)聯(lián)的，則

其次是關(guān)于晶圓在BM的開始和結(jié)束時(shí)間的計(jì)算，其計(jì)算肯定是基于VBMh”k”的，相應(yīng)的計(jì)算公式如下：

最后是晶圓在各個(gè)PM上的開始和結(jié)束時(shí)間的計(jì)算．由于PM的計(jì)算也必定是基于VBMh”k”的，所以其計(jì)算的方法可歸納如下：

2.3 基于修正的SWAP策略調(diào)度

對于集束型設(shè)備群的調(diào)度就是要在滿足各種要求的情況下，確定各個(gè)機(jī)械手的動(dòng)作順序和時(shí)間，以實(shí)現(xiàn)預(yù)定的調(diào)度目標(biāo)．對于不帶駐留約束限制的雙臂集束型設(shè)備來說，SWAP策略是其基本的調(diào)度策略，并且是已經(jīng)被證明了的優(yōu)化的調(diào)度策略［2］．對于帶有駐留約束的雙臂集束型設(shè)備群來說，雙臂機(jī)械手在調(diào)度上最大的功能就是提供了一個(gè)臨時(shí)的“緩沖”模塊．雙臂機(jī)械手的這一作用也正為帶駐留約束的集束型設(shè)備群的調(diào)度提供了新的調(diào)度空間．在本文的算法中，將雙臂虛擬為單臂，晶圓在VBM上的開始和結(jié)束的時(shí)間就是晶圓在雙臂PM的其中一個(gè)模塊的開始和結(jié)束時(shí)間，結(jié)合修正的SWAP策略，可得到對集束型設(shè)備群的調(diào)度．對于不帶駐留約束限制的集束型設(shè)備群來說，SWAP策略就是完全根據(jù)晶圓的加工時(shí)間來確定機(jī)械手各個(gè)動(dòng)作的時(shí)間和順序．在考慮駐留約束限制的情況下，根據(jù)2.2節(jié)的調(diào)度，首先可以確定的一個(gè)機(jī)械手的各個(gè)動(dòng)作的時(shí)間，再根據(jù)晶圓在虛擬處理模塊上的開始和結(jié)束時(shí)間確定另一只機(jī)械手的相應(yīng)的開始和結(jié)束時(shí)間，從而可以確定雙臂機(jī)械手對晶圓的搬運(yùn)的動(dòng)作順序和時(shí)間，從而完成調(diào)度．

3 仿真實(shí)驗(yàn)與分析

為了有效地評價(jià)本文提出的調(diào)度算法，選取文獻(xiàn)［3］構(gòu)造的基礎(chǔ)調(diào)度周期（fundamental period，F(xiàn)P） 下界作為 benchmark，并且與文獻(xiàn)［3］提出的下界的非VBM調(diào)度方法進(jìn)行對比，期望通過對下界的綜合使用來更加有效地評價(jià)本文的算法.周期延長率［13］

表示因?yàn)轳v留約束而相對于FPB的延時(shí)率，R越小，越接近FPB，即本文提出的算法性能越好．

表示集束型設(shè)備群中RM的繁忙程度，CF越大，晶圓的最大處理時(shí)間和RM完成一次搬運(yùn)所需時(shí)間的比例越大，說明RM越空閑，反之表明RM越繁忙．

相關(guān)符號定義如下：FPZ表示處理一批晶圓所需的平均周期時(shí)間；FPB表示文獻(xiàn)［3］中的下界周期時(shí)間；tpmax表示晶圓在某個(gè)集束型設(shè)備中各個(gè)PM的最大處理時(shí)間；tM表示完成一次搬運(yùn)的時(shí)間；N表示每個(gè)集束型設(shè)備中的PM的數(shù)目；N?表示文獻(xiàn)［3］中提出的VBM塊的數(shù)目．

為了方便仿真，在不失一般性的前提下，本文假設(shè)晶圓在晶圓流模式上的各個(gè)加工時(shí)間tp和駐留約束時(shí)間tu服從相應(yīng)的正態(tài)分布．此外，根據(jù)對集束型設(shè)備群調(diào)度研究的通行做法，本文假設(shè)機(jī)械手在不同模塊間的搬運(yùn)時(shí)間tM，i，hj、tMV，i，hj等相同，并用T表示．最后，假設(shè)集束型設(shè)備群中每個(gè)集束型設(shè)備含有的處理腔的數(shù)目相等，并用Np表示．

3.1 運(yùn)算時(shí)間分析

為了確定算法是否能夠快速響應(yīng)調(diào)度，對算法運(yùn)行時(shí)間進(jìn)行了仿真分析，實(shí)驗(yàn)設(shè)計(jì)如下：令m=8；Np=6；T=2；tp～N（40，10）；tu～N（30，5）；依次令晶圓的數(shù)目為：5、10、15、20、25、30、35、40、45、50，分別計(jì)算算法求得調(diào)度結(jié)果的時(shí)間.程序運(yùn)行的硬件環(huán)境為320 G硬盤、2 GB內(nèi)存和2.13 GHz主頻英特爾處理器的ACER個(gè)人筆記本電腦.運(yùn)行的結(jié)果如圖5所示.

圖5 算法運(yùn)行時(shí)間

由圖5可以看出，當(dāng)一次處理的晶圓數(shù)量為25片（1個(gè)Lot）時(shí)，算法的運(yùn)行時(shí)間為0.5 s，也就是說算法可以在0.5 s以內(nèi)完成對1個(gè)Lot的優(yōu)化調(diào)度.隨晶圓數(shù)量的增加其算法的求解時(shí)間呈單調(diào)遞增.完成兩個(gè)Lot的調(diào)度僅用了3.4 s左右，可知算法產(chǎn)生調(diào)度解的時(shí)間是比較短的，響應(yīng)時(shí)間較快.

3.2 設(shè)備因子對算法的影響

設(shè)備因子CF是反映在集束型設(shè)備群內(nèi)機(jī)械手的裝載、卸載的時(shí)間和晶圓在各個(gè)PM上加工時(shí)間的關(guān)系的指標(biāo)．設(shè)備因子實(shí)際上反映的是在集束型設(shè)備群內(nèi)機(jī)械手繁忙程度的函數(shù)．

實(shí)驗(yàn)的設(shè)計(jì)如下：令Np=4，T=2；tp～N（40，10），tu～N（30，5）；分別令m=2、3、4、5，求出在CF=1、2、3、4、5、6 時(shí)的R值，分析在各種情況下CF對R影響．仿真結(jié)果如圖6所示．

圖6 CF對算法的影響

由圖6可以看出，周期延長率R基本上是隨著CF的逐漸增大而不斷下降，且不同m值的仿真曲線的走向基本相同．當(dāng)CF＞5時(shí)，R＜0.05，表明在不同m值的集束型設(shè)備群均取得了較好的調(diào)度效果．而且，在實(shí)際中機(jī)械手的搬運(yùn)時(shí)間通常相對于晶圓的最大加工時(shí)間要小，從而CF較大，所以本文提出的算法具有較好的實(shí)際意義．

3.3 集束型設(shè)備群結(jié)構(gòu)對算法的影響

本節(jié)仿真的主要目的是要測試算法對不同的集束型設(shè)備群結(jié)構(gòu)的適應(yīng)性和優(yōu)化性.

首先分析的是集束型設(shè)備群的m值對算法的影響.實(shí)驗(yàn)設(shè)計(jì)如下：令Np=4，T=2；tp～N（40，10），tu～N（30，5）；分別令m=2、3、4、5、6、7，計(jì)算出相應(yīng)的R值，分析m的變化對算法的性能影響，結(jié)果如圖7所示．

圖7 m對算法性能影響

下面分析每個(gè)單集束型設(shè)備里的PM的數(shù)量對算法性能的影響．實(shí)驗(yàn)設(shè)計(jì)如下：令m=3，T=2；tp～N（40，10），tu～N（30，5）；分別令Np=2、4、6、8，計(jì)算其相應(yīng)的R值，并分析Np變化對算法的性能影響，結(jié)果如圖8所示．

由圖7所示，周期延長率R隨著m的變化，雖然有波動(dòng)，但總的來說，上下波動(dòng)的范圍在正負(fù)0.01以內(nèi)，相對來說比較?。纱丝梢娝惴▽τ趍變化具有較好的穩(wěn)定性．從圖8也可以看出類似的規(guī)律，即周期延長率R基本上比較平穩(wěn)，沒有發(fā)生太大的波動(dòng)，算法對于Np變化也具有較好的適應(yīng)性．綜上可知，本文構(gòu)造的算法對不同配置的集束型設(shè)備群具有良好的適應(yīng)性．

圖8 Np值對算法的影響

4 結(jié) 論

1）在提出虛擬緩沖模塊概念的基礎(chǔ)上，構(gòu)造了基于修正SWAP策略的帶駐留約束限制的可調(diào)度多種晶圓種類的雙臂集束型設(shè)備群的調(diào)度算法，為研究此類問題提供了一種調(diào)度方法.

2）所構(gòu)建的算法運(yùn)行時(shí)間短，在調(diào)度1個(gè)Lot數(shù)量的晶圓，僅需0.5 s左右，響應(yīng)時(shí)間較短.

3）由集束型設(shè)備群的配置對算法影響的分析可知：當(dāng)設(shè)備因子＞5時(shí)，周期延長率R已經(jīng)全部＜0.05，表明算法取得了較好的調(diào)度效果；另外，隨著m和Np的變化，周期延長率R雖然有些波動(dòng)，但總體波動(dòng)相對較小，算法對不同的集束型設(shè)備群的配置具有較好的適應(yīng)性．

［1］PERKINSON T L， MCLARTY P K， GYURCSIK R S，et al.Single-wafer cluster tool performance：an analysis of throughput［J］.IEEE Transactions on Semiconductor Manufacturing， 1994， 7（3）： 369-373.

［2］VENKATESH S， DAVENPORT S， FOXHOVEN P， et al.A steady-state throughput analysis of cluster tools：dual-blade versus single-blade robots ［J］.IEEE Transactions on Semiconductor Manufacturing， 1997， 10（4）： 418-424.

［3］YI J， DING S， SONG D， et al.Steady-state throughput and scheduling analysis of multi-cluster tools： a decomposition approach ［J］.IEEE Transactions on Automation Science and Engineering，2008，5（2）： 321-336.

［4］CHAN W，YI J， DING D.On the Optimality of one-unit cycle scheduling of multi-clustertools with singleblade robots［C］／／Proceedings of the 3rd Annual IEEE Conference on Automation Science and Engineering.Piscataway， New York， USA：IEEE， 2007： 392-397.

［5］CHAN WKV， YI J， DING D.Optimal scheduling ofk-unit production of cluster tools with single-blade robots［C］／／IEEE International Conference on Automation Science and Engineering.Piscataway， New York， USA：IEEE，2008：335-340.

［6］ZHOU B H， LI X.Try and error-based scheduling algorithm for cluster tools of wafer fabrications with residency time constraints［J］.Journal of Central South University of Technology， 2012， 19（1）： 187-192.

［7］陳佳，周炳海.帶駐留與重入約束的集束型設(shè)備調(diào)度算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2012，18（12）： 2667-2673.

［8］WU N Q，ZHOU M.Schedulability analysis and optimal scheduling of dual-arm cluster tools with residency time constraintand activity time variation ［J］.IEEE Transactions on Automation Science and Engineering，2012， 9（1）： 203-209.

［9］WU N Q， ZHOU M.A closed-form solution for schedulability and optimal scheduling of dual-arm cluster tools with wafer residency time constraint based on steady schedule analysis［J］.IEEE Transactions on Automation Science and Engineering，2010，7（2）： 303-315.

［10］YAN Q，WU N Q，ZHOU M.Petri net modeling and wafer sojourn time analysis of single-arm cluster tools with residency time constraints and activity time variation［J］.IEEE Transactions on Automation Science and Engineering， 2012， 25（3）：432-446.

［11］LEE H T， LEE H Y， PARK D B.Schedulability analysis of time-constrained cluster tools with bounded time variation by an extended Petri Net［ J］.IEEE Transactions on Automation Science and Engineering，2008， 5（3）： 490-503

［12］ROSTAMI S， HAMIDZADEH B， CAMPORESE D.An optimal periodic scheduler for dual-arm robots in cluster tools with residency constraints［J］.IEEE Transactions on Robotics and Automation， 2001， 17（5）， 609-618.

［13］劉明祥，周炳海.基于時(shí)間約束集的集束型設(shè)備群調(diào)度方法［J］.自動(dòng)化學(xué)報(bào)， 2012， 38（3）： 479-485.

［14］DECHTER R， MEIRI I， PEARL J.Temporal constraint networks［J］.Artificial Intelligence， 1991， 49（1）：61-95.