黃國新,林文文,章天吉
(1.奧克斯空調(diào)股份有限公司,浙江 寧波 315100;2.奧克斯集團有限公司,浙江 寧波 315100;3.寧波大學(xué) 機械工程與力學(xué)學(xué)院,浙江 寧波 315211)
半導(dǎo)體設(shè)備作為半導(dǎo)體芯片加工廠的微小單元,承擔了芯片制造過程中的多個重要環(huán)節(jié)。半導(dǎo)體設(shè)備產(chǎn)能的高低直接影響芯片加工廠的效益,而高效穩(wěn)定的調(diào)度系統(tǒng)是保證最優(yōu)產(chǎn)能的前提。由于設(shè)備內(nèi)的加工存在諸多步驟和約束,從而導(dǎo)致了設(shè)備調(diào)度系統(tǒng)的設(shè)計十分復(fù)雜。與此同時,由于設(shè)備內(nèi)對晶圓的調(diào)度要求實時進行,因此對系統(tǒng)的計算速度有著較高要求。
在眾多半導(dǎo)體設(shè)備中,集束型設(shè)備(Cluster Tool)是具有代表性的一類設(shè)備。該類設(shè)備由加工模塊(Processing Module,PM)、校準模塊(Aligner,AL)、冷卻模塊(Cool,CL)、真空鎖(load lock,LL)和搬運模塊(Transfer Module,TM)構(gòu)成,晶圓經(jīng)過設(shè)備內(nèi)各個模塊以完成指定工藝。
目前為止,有關(guān)晶圓生產(chǎn)的單臂束集束型設(shè)備的調(diào)度研究已有不少工作,研究方法上主要有數(shù)學(xué)規(guī)劃法、事件圖、Petri網(wǎng)和分支定界法[1]。文獻[2,3]中借助時間圖工具,對單臂和雙臂的集束型設(shè)備建立了考慮搬運機械手資源約束及處理腔資源約束時的調(diào)度基礎(chǔ)周期(Fundamental Period,F(xiàn)P)模型,在此基礎(chǔ)上分析了FP對設(shè)備產(chǎn)能的影響,但其僅僅考慮了單種晶圓的No-wait調(diào)度問題。文獻[4]采用事件圖描述加工模塊和機械手的活動,提出了隱枚舉思想的搜索算法。文獻[5]提出了一種構(gòu)造晶圓周期序列的策略和實現(xiàn)該策略的構(gòu)造算法。Chauvet等[6]提出了基于時間窗的含加工時間約束的調(diào)度算法,但未考慮晶圓的搬運時間。周炳海等[7]研究了考慮晶圓多次重入的集束型設(shè)備調(diào)度,并提出了一種啟發(fā)式算法使系統(tǒng)總完工時間最小化。劉明祥[8]等對帶有駐留約束且具有多種晶圓類型的集束型設(shè)備群的調(diào)度問題進行了研究,在引入時間約束集概念的基礎(chǔ)上建立了調(diào)度模型,同時,提出了一種逐級回溯的調(diào)度方法。然而,這些研究都忽略了真空鎖狀態(tài)轉(zhuǎn)換對于內(nèi)外機器手搬運晶圓的影響。
本研究的真空鎖狀態(tài)轉(zhuǎn)換對機械手搬運晶圓的影響,真空鎖存在大氣狀態(tài)和真空狀態(tài)。真空鎖可以在大氣狀態(tài)與真空狀態(tài)間轉(zhuǎn)換,外部的機器手需要真空鎖在大氣狀態(tài)下,才能將晶圓搬入或搬出真空鎖,設(shè)備內(nèi)部的機器手需要真空鎖在真空狀態(tài)下,才能將晶圓搬入或搬出真空鎖,這極大地影響了機械手搬運晶圓的效率,如何盡可能地避免或減少機械手在真空鎖處等待真空鎖狀態(tài)轉(zhuǎn)換的時間成為難題,針對這一問題建立了帶真空鎖狀態(tài)轉(zhuǎn)換約束的數(shù)學(xué)模型,并且采用遺傳算法來解決該調(diào)度問題,又針對傳統(tǒng)遺傳算法容易陷入局部最優(yōu),遺傳參數(shù)難以確定的問題,采用了自適應(yīng)改變交叉和變異概率的算子調(diào)整概率值,從而避免早熟問題的出現(xiàn),并解決了遺傳參數(shù)難以確定的問題。
本研究的集束型設(shè)備由真空鎖模塊(load lock,LL)、校準模塊(Aligner,AL)機械手搬運模塊(robot module,RM)、若干加工模塊(process module,PM)以及冷卻模塊(Cool,CL)構(gòu)成,每個PM有一個槽位,可放置一片晶圓加工。晶圓在集束型設(shè)備的生產(chǎn)過程如圖1所示。
圖1 集束型設(shè)備生產(chǎn)過程
生產(chǎn)過程描述如下:
LP為晶圓盒,用于存放晶圓。首先,晶圓加工前須放置在AL處做校準,晶圓完成校準后才能被取走。接著,取走的晶圓從真空鎖LLA進入系統(tǒng),按事先設(shè)定的順序依次經(jīng)過一個或多個PM加工后,返回到真空鎖LLB中進行冷卻。最后,冷卻完成的晶圓直接從真空鎖中取出。
為了有效地描述集束型設(shè)備的調(diào)度問題,做出如下基本假設(shè)和定義:(1)研究對象是單集束型設(shè)備。(2)晶圓搬運模塊采用單臂機械手,每個機械手每次只能搬運一片晶圓。(3)每個加工模塊每次只能放置一片晶圓進行加工。(4)晶圓的加工路線相同。(5)晶圓加工前須放置在AL處做校準,晶圓完成校準后才能被取走。(6)真空鎖LLA與LLB可在大氣狀態(tài)與真空狀態(tài)間轉(zhuǎn)換,當LLA或LLB狀態(tài)轉(zhuǎn)換為大氣狀態(tài),機械手TM1才能將晶圓送入或取走,當LLA或LLB狀態(tài)轉(zhuǎn)換為真空狀態(tài),機械手TM2才能將晶圓送入或取走。LLA與LLB從狀態(tài)的轉(zhuǎn)換需要時間。(7)晶圓的加工時間遠大于機械手的操作時間,但并不忽略機械手的操作時間[7]。(8)晶圓加工完成后需放在真空鎖中進行冷卻,冷卻完后才能被取走。(9)晶圓的加工路徑為:
LLA→PM3/PM4→PM1/PM2/PM5/PM6→LLB
為清晰描述調(diào)度問題,作以下符號及變量定義:
集合:
I表示待加工晶圓集;
J表示晶圓的工序集;
Gj表示工序j的并行機器數(shù)目,Gj=1表示工序i只有一個加工模塊可以使用;
常數(shù):
Pij表示第i片晶圓在工序j的機器上的加工時間;
Tget表示機械手完成裝載活動所需要的時間,為定常數(shù);
Tput表示機械手完成卸載活動所需要的時間,為定常數(shù);
T1表示真空鎖從真空狀態(tài)轉(zhuǎn)換為大氣狀態(tài)所需要的時間,為定常數(shù);
T2表示真空鎖從大氣狀態(tài)轉(zhuǎn)換為真空狀態(tài)所需要的時間,為定常數(shù);
Tij噪r表示第i片晶圓從工序j的機器噪上運輸?shù)较乱还ば虻臋C器r上的時間;
變量:
Xij噪表示第i片晶圓在工序j的加工模塊的機器噪上進行加工時,Xij噪=1,否則Xij噪=0;
LLm表示真空鎖m的狀態(tài),當真空鎖處于大氣狀態(tài)時,LLm=0,否則LLm=1;
Sij噪表示第i片晶圓在工序j的機器噪上的開始時間;
Cij噪表示第i片晶圓在工序j的機器噪上的離開時間;
tij噪表示第i片晶圓運輸?shù)较乱还ば虻臋C器噪時,因真空鎖狀態(tài)切換等待的時間;
調(diào)度目標是最小化晶圓加工的總完工時間,因此,目標函數(shù)為:
在真空鎖處等待的時間:
加工模塊同時只能加工一片晶圓:
晶圓需加工完成后才可離開加工模塊:
搬運每次僅搬運1片晶圓,且裝卸時間相同:
晶圓一個階段只在一臺設(shè)備上加工:
晶圓進入首個加工模塊的時間須滿足:
遺傳算法(Genetic Algorithm,GA)是模擬達爾文生物進化論的自然選擇和遺傳學(xué)機理的生物進化過程的計算模型,是一種通過模擬自然進化過程搜索最優(yōu)解的方法。遺傳算法包括了編碼、交叉、變異、選擇等重要操作步驟。針對晶圓生產(chǎn)調(diào)度問題的多約束、多維度求解特性,對遺傳算法進行適應(yīng)性改進。
半導(dǎo)體晶圓調(diào)度需要解決工序與生產(chǎn)設(shè)備的對應(yīng)問題,因此,在染色體編碼中需包含這方面的信息。本研究提出了一種染色體的編碼方式,假設(shè)有3個待加工晶圓,晶圓1、晶圓2和晶圓3均具有3道工序,第一道工序和第二道工序可選生產(chǎn)設(shè)備有2臺,第三道工序可選生產(chǎn)設(shè)備有3臺。
染色體的編碼如圖2所示,數(shù)字1、2、3代表的是晶圓在不同工序選擇的機器編號,由于一個晶圓有3道工序,因此前3個數(shù)字1、2、2表示晶圓1在這三道工序上分別選擇第一臺機器、第二臺機器和第二臺機器,中間3個數(shù)字2、1、3表示晶圓2在這三道工序上分別選擇第二臺機器、第一臺機器和第三臺機器,最后3個數(shù)字1、1、2表示晶圓3在這三道工序上分別選擇第一臺機器、第一臺機器和第二臺機器。
圖2 染色體的編碼
接著,按照給定的染色體編碼,將晶圓放入工序?qū)?yīng)的機器中進行加工,記錄每一片晶圓開始加工的時間,以及加工結(jié)束的時間,由于機械手一次只能搬運一片晶圓,當遇到?jīng)_突時,優(yōu)先選擇前面的晶圓進行搬運。將最后一片晶圓的完工時間作為這批晶圓的總加工時間。
首先給定種群的初始值size;然后根據(jù)晶圓生產(chǎn)規(guī)則一道工序只在一臺機器上加工的特點,生成一個有n×m個基因的染色體,其中n為晶圓的數(shù)量,m為工序的數(shù)量,最后使其循環(huán)size次,得到一個初始種群。
適應(yīng)度函數(shù)。適應(yīng)度函數(shù)用于描述染色體對自然界的適應(yīng)情況,評價個體的質(zhì)量用晶圓完工時間指標構(gòu)造適應(yīng)度函數(shù)。
式中:f為適應(yīng)度函數(shù),Cmax為最后一片晶圓的完工時間。
交叉操作是種群新個體的主要來源,其結(jié)果會直接影響到算法的效率。傳統(tǒng)遺傳算法中都是采用固定的交叉概率,會存在一些問題:當給定的值較小時會使搜索范圍變小,不利于尋找更優(yōu)解;當給定值較大時可能導(dǎo)致已有的優(yōu)良染色體在交叉操作后變差。本研究采用自適應(yīng)的方法調(diào)整交叉概率[9],針對每個染色體優(yōu)化改進的交叉概率算式如下:
式中:Pc為染色體的交叉概率;噪1、噪2分別為0到1之間的隨機數(shù);favg為當前種群中所有染色體的平均適應(yīng)度值;fmax為當前種群中所有染色體的最大適應(yīng)度值;f為當前個體適應(yīng)度值。
此外,交叉操作要保持適中,如果交叉操作使染色體變化過大,則算法將會退化為隨機搜索算法,也不利于較優(yōu)染色體的保留;如果交叉操作不足,使染色體變化不大,則算法失去搜索能力和進化能力[10]。本研究采用多點交叉,實現(xiàn)方法為:將選中的父代個體染色體中隨機設(shè)置兩個交叉點,然后交換兩個個體在所設(shè)定的兩個交叉點之間的部分染色體。兩點交叉算子如圖3所示。
圖3 交叉操作
為了提高變異操作的指導(dǎo)性與精確性,對于不同的染色體采用不同的變異概率,對于優(yōu)質(zhì)個體應(yīng)該采用較低的變異概率與變異方式來進行優(yōu)良基因的保留,而對于劣質(zhì)個體應(yīng)該采用較高的變異概率與方式使其更適于生存[11]。
針對每個染色體優(yōu)化改進的變異概率計算公式為
式中:Pm為染色體的變異概率;噪3、噪4分別為0到1之間的隨機數(shù);favg為當前種群中所有染色體的平均適應(yīng)度值;fmax為當前種群中所有染色體的最大適應(yīng)度值;f′為當前個體適應(yīng)度值。
采用多點變異,隨機生成概率P,若P<Pm(變異概率),則該染色體發(fā)生變異,從染色體中隨機選擇幾個基因,讓其在對應(yīng)工序可加工機器集中重新選一臺加工機器。變異操作如圖4所示。
圖4 變異操作
選擇操作即遺傳操作后染色體的保留方法。本研究使用輪盤賭進行選擇。將所有父代和遺傳操作后的子代個體進行混合,并根據(jù)適應(yīng)度函數(shù)進行排序,各個個體的選擇概率和其適應(yīng)度值成比例,適應(yīng)度越大,選中概率也越大。通過這種選擇方式淘汰垃圾基因,并保持染色體規(guī)模的穩(wěn)定。
Step 1:設(shè)定晶圓生產(chǎn)調(diào)度案例,包括待加工晶圓數(shù)量、晶圓的工序數(shù)量、滿足各工序 生產(chǎn)要求的生產(chǎn)設(shè)備;確定遺傳算法參數(shù),包括染色體規(guī)模、交叉概率、變異概率、算法最大迭代次數(shù)等。
Step 2:以隨機方式初始化染色體,并計算初始種群平均適應(yīng)值。
Step 3:按照交叉概率執(zhí)行兩點交叉算子,按照變異概率執(zhí)行多點變異算子。
Step 4:將父代和子代進行混合,使用輪盤賭選擇保留的個體,迭代次數(shù)+1。
Step 5:判斷算法是否達到最大迭代次數(shù),若否則轉(zhuǎn)至Step 3;若是則輸出適應(yīng)度最大的染色體,算法結(jié)束。
根據(jù)多次實驗以及前人實驗結(jié)果,標準遺傳算法的參數(shù)設(shè)置為:迭代次數(shù)為500,種群總大小為100,交叉概率為0.9,變異概率為0.5。改進遺傳算法的參數(shù)設(shè)置為:迭代次數(shù)為500,種群總大小為100,k1,k2為0.9,k3,k4為0.12。每種規(guī)模的實例優(yōu)化計算10次,求解的最佳結(jié)果如表1所示,求解的平均結(jié)果如表2所示。
表1 最佳求解結(jié)果比較
表2 平均求解結(jié)果比較
從結(jié)果可以看出,改進遺傳算法獲得的結(jié)果始終優(yōu)于標準遺傳算法獲得的結(jié)果,并且隨著加工晶圓數(shù)的增加,改進遺傳算法獲得的結(jié)果與標準遺傳算法獲得的結(jié)果的差距越來越大。仿真實驗結(jié)果有力證明了改進的遺傳算法是有效的。
為確定改進遺傳算法是否能夠在較短的時間內(nèi)求得調(diào)度方案,對算法的運行時間進行了仿真分析,圖5可以看出,改進遺傳算法的運行時間隨晶圓數(shù)目的增加基本上呈線性增加,并不會因為數(shù)量的增加而導(dǎo)致運行時間呈指數(shù)型增長,同時能在較短的時間內(nèi)求得可行的解決方案,因此,改進遺傳算法具有一定的實用性。
圖5 算法運行時間
本研究的真空鎖狀態(tài)對機械手搬運晶圓的影響,提出的遺傳算法為此類集束型設(shè)備的調(diào)度問題提供了一個行之有效的求解方法。根據(jù)機械手調(diào)度晶圓選擇不同的加工腔加工晶圓,在滿足約束的前提下,盡可能使加工晶圓的總完工時間最小。仿真實驗結(jié)果表明了改進的遺傳算法的有效性。