黃國新，林文文，章天吉

（1.奧克斯空調(diào)股份有限公司，浙江 寧波 315100；2.奧克斯集團(tuán)有限公司，浙江 寧波 315100；3.寧波大學(xué) 機(jī)械工程與力學(xué)學(xué)院，浙江 寧波 315211）

半導(dǎo)體設(shè)備作為半導(dǎo)體芯片加工廠的微小單元，承擔(dān)了芯片制造過程中的多個(gè)重要環(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è)計(jì)十分復(fù)雜。與此同時(shí)，由于設(shè)備內(nèi)對晶圓的調(diào)度要求實(shí)時(shí)進(jìn)行，因此對系統(tǒng)的計(jì)算速度有著較高要求。

在眾多半導(dǎo)體設(shè)備中，集束型設(shè)備（Cluster Tool）是具有代表性的一類設(shè)備。該類設(shè)備由加工模塊（Processing Module，PM）、校準(zhǔn)模塊（Aligner，AL）、冷卻模塊（Cool，CL）、真空鎖（load lock，LL）和搬運(yùn)模塊（Transfer Module，TM）構(gòu)成，晶圓經(jīng)過設(shè)備內(nèi)各個(gè)模塊以完成指定工藝。

目前為止，有關(guān)晶圓生產(chǎn)的單臂束集束型設(shè)備的調(diào)度研究已有不少工作，研究方法上主要有數(shù)學(xué)規(guī)劃法、事件圖、Petri網(wǎng)和分支定界法[1]。文獻(xiàn)[2，3]中借助時(shí)間圖工具，對單臂和雙臂的集束型設(shè)備建立了考慮搬運(yùn)機(jī)械手資源約束及處理腔資源約束時(shí)的調(diào)度基礎(chǔ)周期（Fundamental Period，F(xiàn)P）模型，在此基礎(chǔ)上分析了FP對設(shè)備產(chǎn)能的影響，但其僅僅考慮了單種晶圓的No-wait調(diào)度問題。文獻(xiàn)[4]采用事件圖描述加工模塊和機(jī)械手的活動(dòng)，提出了隱枚舉思想的搜索算法。文獻(xiàn)[5]提出了一種構(gòu)造晶圓周期序列的策略和實(shí)現(xiàn)該策略的構(gòu)造算法。Chauvet等[6]提出了基于時(shí)間窗的含加工時(shí)間約束的調(diào)度算法，但未考慮晶圓的搬運(yùn)時(shí)間。周炳海等[7]研究了考慮晶圓多次重入的集束型設(shè)備調(diào)度，并提出了一種啟發(fā)式算法使系統(tǒng)總完工時(shí)間最小化。劉明祥[8]等對帶有駐留約束且具有多種晶圓類型的集束型設(shè)備群的調(diào)度問題進(jìn)行了研究，在引入時(shí)間約束集概念的基礎(chǔ)上建立了調(diào)度模型，同時(shí)，提出了一種逐級回溯的調(diào)度方法。然而，這些研究都忽略了真空鎖狀態(tài)轉(zhuǎn)換對于內(nèi)外機(jī)器手搬運(yùn)晶圓的影響。

本研究的真空鎖狀態(tài)轉(zhuǎn)換對機(jī)械手搬運(yùn)晶圓的影響，真空鎖存在大氣狀態(tài)和真空狀態(tài)。真空鎖可以在大氣狀態(tài)與真空狀態(tài)間轉(zhuǎn)換，外部的機(jī)器手需要真空鎖在大氣狀態(tài)下，才能將晶圓搬入或搬出真空鎖，設(shè)備內(nèi)部的機(jī)器手需要真空鎖在真空狀態(tài)下，才能將晶圓搬入或搬出真空鎖，這極大地影響了機(jī)械手搬運(yùn)晶圓的效率，如何盡可能地避免或減少機(jī)械手在真空鎖處等待真空鎖狀態(tài)轉(zhuǎn)換的時(shí)間成為難題，針對這一問題建立了帶真空鎖狀態(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）、校準(zhǔn)模塊（Aligner，AL）機(jī)械手搬運(yùn)模塊（robot module，RM）、若干加工模塊（process module，PM）以及冷卻模塊（Cool，CL）構(gòu)成，每個(gè)PM有一個(gè)槽位，可放置一片晶圓加工。晶圓在集束型設(shè)備的生產(chǎn)過程如圖1所示。

圖1 集束型設(shè)備生產(chǎn)過程

生產(chǎn)過程描述如下：

LP為晶圓盒，用于存放晶圓。首先，晶圓加工前須放置在AL處做校準(zhǔn)，晶圓完成校準(zhǔn)后才能被取走。接著，取走的晶圓從真空鎖LLA進(jìn)入系統(tǒng)，按事先設(shè)定的順序依次經(jīng)過一個(gè)或多個(gè)PM加工后，返回到真空鎖LLB中進(jìn)行冷卻。最后，冷卻完成的晶圓直接從真空鎖中取出。

為了有效地描述集束型設(shè)備的調(diào)度問題，做出如下基本假設(shè)和定義：（1）研究對象是單集束型設(shè)備。（2）晶圓搬運(yùn)模塊采用單臂機(jī)械手，每個(gè)機(jī)械手每次只能搬運(yùn)一片晶圓。（3）每個(gè)加工模塊每次只能放置一片晶圓進(jìn)行加工。（4）晶圓的加工路線相同。（5）晶圓加工前須放置在AL處做校準(zhǔn)，晶圓完成校準(zhǔn)后才能被取走。（6）真空鎖LLA與LLB可在大氣狀態(tài)與真空狀態(tài)間轉(zhuǎn)換，當(dāng)LLA或LLB狀態(tài)轉(zhuǎn)換為大氣狀態(tài)，機(jī)械手TM1才能將晶圓送入或取走，當(dāng)LLA或LLB狀態(tài)轉(zhuǎn)換為真空狀態(tài)，機(jī)械手TM2才能將晶圓送入或取走。LLA與LLB從狀態(tài)的轉(zhuǎn)換需要時(shí)間。（7）晶圓的加工時(shí)間遠(yuǎn)大于機(jī)械手的操作時(shí)間，但并不忽略機(jī)械手的操作時(shí)間[7]。（8）晶圓加工完成后需放在真空鎖中進(jìn)行冷卻，冷卻完后才能被取走。（9）晶圓的加工路徑為：

LLA→PM3/PM4→PM1/PM2/PM5/PM6→LLB

為清晰描述調(diào)度問題，作以下符號及變量定義：

集合：

I表示待加工晶圓集；

J表示晶圓的工序集；

Gj表示工序j的并行機(jī)器數(shù)目，Gj=1表示工序i只有一個(gè)加工模塊可以使用；

常數(shù)：

Pij表示第i片晶圓在工序j的機(jī)器上的加工時(shí)間；

Tget表示機(jī)械手完成裝載活動(dòng)所需要的時(shí)間，為定常數(shù)；

Tput表示機(jī)械手完成卸載活動(dòng)所需要的時(shí)間，為定常數(shù)；

T1表示真空鎖從真空狀態(tài)轉(zhuǎn)換為大氣狀態(tài)所需要的時(shí)間，為定常數(shù)；

T2表示真空鎖從大氣狀態(tài)轉(zhuǎn)換為真空狀態(tài)所需要的時(shí)間，為定常數(shù)；

Tij噪r表示第i片晶圓從工序j的機(jī)器噪上運(yùn)輸?shù)较乱还ば虻臋C(jī)器r上的時(shí)間；

變量：

Xij噪表示第i片晶圓在工序j的加工模塊的機(jī)器噪上進(jìn)行加工時(shí)，Xij噪=1，否則Xij噪=0；

LLm表示真空鎖m的狀態(tài)，當(dāng)真空鎖處于大氣狀態(tài)時(shí)，LLm=0，否則LLm=1；

Sij噪表示第i片晶圓在工序j的機(jī)器噪上的開始時(shí)間；

Cij噪表示第i片晶圓在工序j的機(jī)器噪上的離開時(shí)間；

tij噪表示第i片晶圓運(yùn)輸?shù)较乱还ば虻臋C(jī)器噪時(shí)，因真空鎖狀態(tài)切換等待的時(shí)間；

調(diào)度目標(biāo)是最小化晶圓加工的總完工時(shí)間，因此，目標(biāo)函數(shù)為：

在真空鎖處等待的時(shí)間：

加工模塊同時(shí)只能加工一片晶圓：

晶圓需加工完成后才可離開加工模塊：

搬運(yùn)每次僅搬運(yùn)1片晶圓，且裝卸時(shí)間相同：

晶圓一個(gè)階段只在一臺設(shè)備上加工：

晶圓進(jìn)入首個(gè)加工模塊的時(shí)間須滿足：

2 遺傳算法設(shè)計(jì)

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

2.1 染色體編碼與解碼

半導(dǎo)體晶圓調(diào)度需要解決工序與生產(chǎn)設(shè)備的對應(yīng)問題，因此，在染色體編碼中需包含這方面的信息。本研究提出了一種染色體的編碼方式，假設(shè)有3個(gè)待加工晶圓，晶圓1、晶圓2和晶圓3均具有3道工序，第一道工序和第二道工序可選生產(chǎn)設(shè)備有2臺，第三道工序可選生產(chǎn)設(shè)備有3臺。

染色體的編碼如圖2所示，數(shù)字1、2、3代表的是晶圓在不同工序選擇的機(jī)器編號，由于一個(gè)晶圓有3道工序，因此前3個(gè)數(shù)字1、2、2表示晶圓1在這三道工序上分別選擇第一臺機(jī)器、第二臺機(jī)器和第二臺機(jī)器，中間3個(gè)數(shù)字2、1、3表示晶圓2在這三道工序上分別選擇第二臺機(jī)器、第一臺機(jī)器和第三臺機(jī)器，最后3個(gè)數(shù)字1、1、2表示晶圓3在這三道工序上分別選擇第一臺機(jī)器、第一臺機(jī)器和第二臺機(jī)器。

圖2 染色體的編碼

接著，按照給定的染色體編碼，將晶圓放入工序?qū)?yīng)的機(jī)器中進(jìn)行加工，記錄每一片晶圓開始加工的時(shí)間，以及加工結(jié)束的時(shí)間，由于機(jī)械手一次只能搬運(yùn)一片晶圓，當(dāng)遇到?jīng)_突時(shí)，優(yōu)先選擇前面的晶圓進(jìn)行搬運(yùn)。將最后一片晶圓的完工時(shí)間作為這批晶圓的總加工時(shí)間。

2.2 初始化種群

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

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

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

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

2.4 交叉操作

交叉操作是種群新個(gè)體的主要來源，其結(jié)果會直接影響到算法的效率。傳統(tǒng)遺傳算法中都是采用固定的交叉概率，會存在一些問題：當(dāng)給定的值較小時(shí)會使搜索范圍變小，不利于尋找更優(yōu)解；當(dāng)給定值較大時(shí)可能導(dǎo)致已有的優(yōu)良染色體在交叉操作后變差。本研究采用自適應(yīng)的方法調(diào)整交叉概率[9]，針對每個(gè)染色體優(yōu)化改進(jìn)的交叉概率算式如下：

式中：Pc為染色體的交叉概率；噪1、噪2分別為0到1之間的隨機(jī)數(shù)；favg為當(dāng)前種群中所有染色體的平均適應(yīng)度值；fmax為當(dāng)前種群中所有染色體的最大適應(yīng)度值；f為當(dāng)前個(gè)體適應(yīng)度值。

此外，交叉操作要保持適中，如果交叉操作使染色體變化過大，則算法將會退化為隨機(jī)搜索算法，也不利于較優(yōu)染色體的保留；如果交叉操作不足，使染色體變化不大，則算法失去搜索能力和進(jìn)化能力[10]。本研究采用多點(diǎn)交叉，實(shí)現(xiàn)方法為：將選中的父代個(gè)體染色體中隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)，然后交換兩個(gè)個(gè)體在所設(shè)定的兩個(gè)交叉點(diǎn)之間的部分染色體。兩點(diǎn)交叉算子如圖3所示。

圖3 交叉操作

2.5 變異操作

為了提高變異操作的指導(dǎo)性與精確性，對于不同的染色體采用不同的變異概率，對于優(yōu)質(zhì)個(gè)體應(yīng)該采用較低的變異概率與變異方式來進(jìn)行優(yōu)良基因的保留，而對于劣質(zhì)個(gè)體應(yīng)該采用較高的變異概率與方式使其更適于生存[11]。

針對每個(gè)染色體優(yōu)化改進(jìn)的變異概率計(jì)算公式為

式中：Pm為染色體的變異概率；噪3、噪4分別為0到1之間的隨機(jī)數(shù)；favg為當(dāng)前種群中所有染色體的平均適應(yīng)度值；fmax為當(dāng)前種群中所有染色體的最大適應(yīng)度值；f′為當(dāng)前個(gè)體適應(yīng)度值。

采用多點(diǎn)變異，隨機(jī)生成概率P，若P＜Pm（變異概率），則該染色體發(fā)生變異，從染色體中隨機(jī)選擇幾個(gè)基因，讓其在對應(yīng)工序可加工機(jī)器集中重新選一臺加工機(jī)器。變異操作如圖4所示。

圖4 變異操作

2.6 選擇操作

選擇操作即遺傳操作后染色體的保留方法。本研究使用輪盤賭進(jìn)行選擇。將所有父代和遺傳操作后的子代個(gè)體進(jìn)行混合，并根據(jù)適應(yīng)度函數(shù)進(jìn)行排序，各個(gè)個(gè)體的選擇概率和其適應(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：以隨機(jī)方式初始化染色體，并計(jì)算初始種群平均適應(yīng)值。

Step 3：按照交叉概率執(zhí)行兩點(diǎn)交叉算子，按照變異概率執(zhí)行多點(diǎn)變異算子。

Step 4：將父代和子代進(jìn)行混合，使用輪盤賭選擇保留的個(gè)體，迭代次數(shù)+1。

Step 5：判斷算法是否達(dá)到最大迭代次數(shù)，若否則轉(zhuǎn)至Step 3；若是則輸出適應(yīng)度最大的染色體，算法結(jié)束。

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

根據(jù)多次實(shí)驗(yàn)以及前人實(shí)驗(yàn)結(jié)果，標(biāo)準(zhǔn)遺傳算法的參數(shù)設(shè)置為：迭代次數(shù)為500，種群總大小為100，交叉概率為0.9，變異概率為0.5。改進(jìn)遺傳算法的參數(shù)設(shè)置為：迭代次數(shù)為500，種群總大小為100，k1，k2為0.9，k3，k4為0.12。每種規(guī)模的實(shí)例優(yōu)化計(jì)算10次，求解的最佳結(jié)果如表1所示，求解的平均結(jié)果如表2所示。

表1 最佳求解結(jié)果比較

表2 平均求解結(jié)果比較

從結(jié)果可以看出，改進(jìn)遺傳算法獲得的結(jié)果始終優(yōu)于標(biāo)準(zhǔn)遺傳算法獲得的結(jié)果，并且隨著加工晶圓數(shù)的增加，改進(jìn)遺傳算法獲得的結(jié)果與標(biāo)準(zhǔn)遺傳算法獲得的結(jié)果的差距越來越大。仿真實(shí)驗(yàn)結(jié)果有力證明了改進(jìn)的遺傳算法是有效的。

為確定改進(jìn)遺傳算法是否能夠在較短的時(shí)間內(nèi)求得調(diào)度方案，對算法的運(yùn)行時(shí)間進(jìn)行了仿真分析，圖5可以看出，改進(jìn)遺傳算法的運(yùn)行時(shí)間隨晶圓數(shù)目的增加基本上呈線性增加，并不會因?yàn)閿?shù)量的增加而導(dǎo)致運(yùn)行時(shí)間呈指數(shù)型增長，同時(shí)能在較短的時(shí)間內(nèi)求得可行的解決方案，因此，改進(jìn)遺傳算法具有一定的實(shí)用性。

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

4 結(jié)語

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