黃國新，林文文，章天吉

（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ù)難以確定的問題。

1 問題描述

本研究的集束型設(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è)備上加工：

晶圓進入首個加工模塊的時間須滿足：

2 遺傳算法設(shè)計

遺傳算法（Genetic Algorithm，GA）是模擬達爾文生物進化論的自然選擇和遺傳學(xué)機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。遺傳算法包括了編碼、交叉、變異、選擇等重要操作步驟。針對晶圓生產(chǎn)調(diào)度問題的多約束、多維度求解特性，對遺傳算法進行適應(yīng)性改進。

2.1 染色體編碼與解碼

半導(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)先選擇前面的晶圓進行搬運。將最后一片晶圓的完工時間作為這批晶圓的總加工時間。

2.2 初始化種群

首先給定種群的初始值size；然后根據(jù)晶圓生產(chǎn)規(guī)則一道工序只在一臺機器上加工的特點，生成一個有n×m個基因的染色體，其中n為晶圓的數(shù)量，m為工序的數(shù)量，最后使其循環(huán)size次，得到一個初始種群。

2.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)。適應(yīng)度函數(shù)用于描述染色體對自然界的適應(yīng)情況，評價個體的質(zhì)量用晶圓完工時間指標構(gòu)造適應(yīng)度函數(shù)。

式中：f為適應(yīng)度函數(shù)，Cmax為最后一片晶圓的完工時間。

2.4 交叉操作

交叉操作是種群新個體的主要來源，其結(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 交叉操作

2.5 變異操作

為了提高變異操作的指導(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 變異操作

2.6 選擇操作

選擇操作即遺傳操作后染色體的保留方法。本研究使用輪盤賭進行選擇。將所有父代和遺傳操作后的子代個體進行混合，并根據(jù)適應(yīng)度函數(shù)進行排序，各個個體的選擇概率和其適應(yīng)度值成比例，適應(yīng)度越大，選中概率也越大。通過這種選擇方式淘汰垃圾基因，并保持染色體規(guī)模的穩(wěn)定。

2.7 基于遺傳算法的調(diào)度流程

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é)束。

3 仿真實驗

根據(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 算法運行時間

4 結(jié)語

本研究的真空鎖狀態(tài)對機械手搬運晶圓的影響，提出的遺傳算法為此類集束型設(shè)備的調(diào)度問題提供了一個行之有效的求解方法。根據(jù)機械手調(diào)度晶圓選擇不同的加工腔加工晶圓，在滿足約束的前提下，盡可能使加工晶圓的總完工時間最小。仿真實驗結(jié)果表明了改進的遺傳算法的有效性。