基于遺傳算法的含真空鎖狀態約束的集束型設備智能調度

黃國新，林文文，章天吉

（1.奧克斯空調股份有限公司，浙江 寧波 315100；2.奧克斯集團有限公司，浙江 寧波 315100；3.寧波大學 機械工程與力學學院，浙江 寧波 315211）

半導體設備作為半導體芯片加工廠的微小單元，承擔了芯片制造過程中的多個重要環節。半導體設備產能的高低直接影響芯片加工廠的效益，而高效穩定的調度系統是保證最優產能的前提。由于設備內的加工存在諸多步驟和約束，從而導致了設備調度系統的設計十分復雜。與此同時，由于設備內對晶圓的調度要求實時進行，因此對系統的計算速度有著較高要求。

在眾多半導體設備中，集束型設備（Cluster Tool）是具有代表性的一類設備。該類設備由加工模塊（Processing Module，PM）、校準模塊（Aligner，AL）、冷卻模塊（Cool，CL）、真空鎖（load lock，LL）和搬運模塊（Transfer Module，TM）構成，晶圓經過設備內各個模塊以完成指定工藝。

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

本研究的真空鎖狀態轉換對機械手搬運晶圓的影響，真空鎖存在大氣狀態和真空狀態。真空鎖可以在大氣狀態與真空狀態間轉換，外部的機器手需要真空鎖在大氣狀態下，才能將晶圓搬入或搬出真空鎖，設備內部的機器手需要真空鎖在真空狀態下，才能將晶圓搬入或搬出真空鎖，這極大地影響了機械手搬運晶圓的效率，如何盡可能地避免或減少機械手在真空鎖處等待真空鎖狀態轉換的時間成為難題，針對這一問題建立了帶真空鎖狀態轉換約束的數學模型，并且采用遺傳算法來解決該調度問題，又針對傳統遺傳算法容易陷入局部最優，遺傳參數難以確定的問題，采用了自適應改變交叉和變異概率的算子調整概率值，從而避免早熟問題的出現，并解決了遺傳參數難以確定的問題。

1 問題描述

本研究的集束型設備由真空鎖模塊（load lock，LL）、校準模塊（Aligner，AL）機械手搬運模塊（robot module，RM）、若干加工模塊（process module，PM）以及冷卻模塊（Cool，CL）構成，每個PM有一個槽位，可放置一片晶圓加工。晶圓在集束型設備的生產過程如圖1所示。

圖1 集束型設備生產過程

生產過程描述如下：

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

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

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

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

集合：

I表示待加工晶圓集；

J表示晶圓的工序集；

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

常數：

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

Tget表示機械手完成裝載活動所需要的時間，為定常數；

Tput表示機械手完成卸載活動所需要的時間，為定常數；

T1表示真空鎖從真空狀態轉換為大氣狀態所需要的時間，為定常數；

T2表示真空鎖從大氣狀態轉換為真空狀態所需要的時間，為定常數；

Tij噪r表示第i片晶圓從工序j的機器噪上運輸到下一工序的機器r上的時間；

變量：

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

LLm表示真空鎖m的狀態，當真空鎖處于大氣狀態時，LLm=0，否則LLm=1；

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

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

tij噪表示第i片晶圓運輸到下一工序的機器噪時，因真空鎖狀態切換等待的時間；

調度目標是最小化晶圓加工的總完工時間，因此，目標函數為：

在真空鎖處等待的時間：

加工模塊同時只能加工一片晶圓：

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

搬運每次僅搬運1片晶圓，且裝卸時間相同：

晶圓一個階段只在一臺設備上加工：

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

2 遺傳算法設計

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

2.1 染色體編碼與解碼

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

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

圖2 染色體的編碼

接著，按照給定的染色體編碼，將晶圓放入工序對應的機器中進行加工，記錄每一片晶圓開始加工的時間，以及加工結束的時間，由于機械手一次只能搬運一片晶圓，當遇到沖突時，優先選擇前面的晶圓進行搬運。將最后一片晶圓的完工時間作為這批晶圓的總加工時間。

2.2 初始化種群

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

2.3 適應度函數

適應度函數。適應度函數用于描述染色體對自然界的適應情況，評價個體的質量用晶圓完工時間指標構造適應度函數。

式中：f為適應度函數，Cmax為最后一片晶圓的完工時間。

2.4 交叉操作

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

式中：Pc為染色體的交叉概率；噪1、噪2分別為0到1之間的隨機數；favg為當前種群中所有染色體的平均適應度值；fmax為當前種群中所有染色體的最大適應度值；f為當前個體適應度值。

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

圖3 交叉操作

2.5 變異操作

為了提高變異操作的指導性與精確性，對于不同的染色體采用不同的變異概率，對于優質個體應該采用較低的變異概率與變異方式來進行優良基因的保留，而對于劣質個體應該采用較高的變異概率與方式使其更適于生存[11]。

針對每個染色體優化改進的變異概率計算公式為

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

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

圖4 變異操作

2.6 選擇操作

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

2.7 基于遺傳算法的調度流程

Step 1：設定晶圓生產調度案例，包括待加工晶圓數量、晶圓的工序數量、滿足各工序 生產要求的生產設備；確定遺傳算法參數，包括染色體規模、交叉概率、變異概率、算法最大迭代次數等。

Step 2：以隨機方式初始化染色體，并計算初始種群平均適應值。

Step 3：按照交叉概率執行兩點交叉算子，按照變異概率執行多點變異算子。

Step 4：將父代和子代進行混合，使用輪盤賭選擇保留的個體，迭代次數+1。

Step 5：判斷算法是否達到最大迭代次數，若否則轉至Step 3；若是則輸出適應度最大的染色體，算法結束。

3 仿真實驗

根據多次實驗以及前人實驗結果，標準遺傳算法的參數設置為：迭代次數為500，種群總大小為100，交叉概率為0.9，變異概率為0.5。改進遺傳算法的參數設置為：迭代次數為500，種群總大小為100，k1，k2為0.9，k3，k4為0.12。每種規模的實例優化計算10次，求解的最佳結果如表1所示，求解的平均結果如表2所示。

表1 最佳求解結果比較

表2 平均求解結果比較

從結果可以看出，改進遺傳算法獲得的結果始終優于標準遺傳算法獲得的結果，并且隨著加工晶圓數的增加，改進遺傳算法獲得的結果與標準遺傳算法獲得的結果的差距越來越大。仿真實驗結果有力證明了改進的遺傳算法是有效的。

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

圖5 算法運行時間

4 結語

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