基于改進遺傳算法的集束型裝備調(diào)度研究

鄒詠楠++羅鈞元++李林瑛

摘要：考慮機械手在輸入裝載室、加工模塊和輸出裝載室三者間搬運時間和空載時間下，求解半導體制造中具有滯留時間約束的集束型裝備調(diào)度問題，提出基于機械手搬運作業(yè)順序編碼的改進遺傳算法，包括種群初始化、選擇操作、變異操作和適應度函數(shù)計算等。仿真實驗結(jié)果驗證了提出算法的有效性。

關鍵詞：遺傳算法； 集束型裝備； 半導體制造； 滯留時間約束

中圖分類號：TP301 文獻標識碼：A 文章編號：1009-3044（2017）04-0263-02

Improved Genetic Algorithm for Cluster Tool Scheduling Problem

ZHOU Yong-nan，LUO Jun-yuan， LI Lin-ying

（School of Software， Dalian University of Foreign Languages， Liaoning 116044， China）

Abstract： Considering the robot transport time among the loadlock and the processing modules， for cluster tools with residency time constraints in semiconductor manufactory， this paper studied improved genetic algorithm based on single-arm robot move sequence coding， including population initialization， selection operation， mutation operation and fitness function calculation. Experimental examples showed that the proposed algorithm is effective.

Key words：Genetic Algorithm， Cluster Tools， Semiconductor Manufactory， Residency Time Constraints

1 概述

半導體制造集束型裝備是集成電路生產(chǎn)線上的常見裝備，由晶圓加工設備、物料搬運機械手和輸入裝載室組成。集成電路生產(chǎn)線對工藝和加工環(huán)境的嚴格要求，使得加工模塊間的晶圓搬運作業(yè)必須由計算機控制的單臂或雙臂機械手來完成。與經(jīng)典的流水車間調(diào)度問題相比，集束型裝備的調(diào)度問題不僅要合理地調(diào)度晶圓加工作業(yè)順序，還要有效地規(guī)劃機構手搬運作業(yè)順序，因此更加復雜[1，2]。本文該對這類調(diào)度問題，在考慮滯留時間約束的前提下，提出一種基于機械手搬運作業(yè)順序編碼的改進的遺傳算法。

2 問題描述

圖1所示的集束型裝備包括三個部分：單晶圓加工模塊、單臂/雙臂機械手和輸入輸出裝載室。晶圓在加工過程中，首先依照預先制定的加工配方，晶圓從輸入裝載室進入；在經(jīng)過激光或圖像定位后，進入加工模塊1，2，…，N完成加工；并在輸出裝載室冷卻后離開系統(tǒng)。集束型裝備調(diào)度問題的特點可有如下描述：1）晶圓在各個加工模塊間沒有緩沖，晶圓在上一加工晶圓被搬離后才能完成加載；2）各加工模塊一次只能加工一片晶圓；3）晶圓在加工模塊的停留時間具有滯留時間約束；4）物料運輸模塊為單臂機械手，執(zhí)行晶圓的移動、空載、裝載和卸載任務。

晶圓的加工過程是批量的周期性過程，相鄰兩個晶圓進入系統(tǒng)的時間間隔稱為生產(chǎn)周期。其調(diào)度問題的目標是在滿足滯留時間約束的前提下，確定機械手在一個生產(chǎn)周期內(nèi)的搬動作業(yè)順序，并使生產(chǎn)周期最小化。

3 改進遺傳算法

遺傳算法是一類基于概率而面向全局優(yōu)化的隨機搜索算法，以生物進化為原型，具有收斂速度快、計算時間少、魯棒性高等優(yōu)點[3]。雖然如此，由于無法全面地描述約束，遺傳算法在解決實際問題中還有很多局限性。本文針對這一局限性，結(jié)合求解問題的特殊性，對遺傳算法的編碼方式、初始種群產(chǎn)生方式和交叉變異操作進行改進。

3.1 編碼和解碼

根據(jù)集束型裝備的特點，提出了一種基于機械手搬運作業(yè)順序的整數(shù)編碼。該編碼方式以有限的加工模塊數(shù)作為染色體搜索空間維度，縮小了問題的搜索空間。設[Y={y0，y1，…，yN}]為染色體，基因[yi]表示機械手在工位[i]執(zhí)行的搬運作業(yè)號[4，5]。

對染色體進行編碼后，要按照編碼規(guī)則將種群中的每個染色體進行解碼，將染色體的基因信息再次解釋為機械手搬運作業(yè)信息。對于給定的一組機械手搬運作業(yè)順序，通過求解不等式即可獲知對應的調(diào)度方案，即求出最優(yōu)生產(chǎn)周期[T]以及調(diào)度方案。適應度函數(shù)定義為[Fit=s/T]，[s]為固定常數(shù)。

3.2 交叉操作

交叉操作可以使群體中優(yōu)良個體的基因特性在一定程度上得以保持。集束型裝備調(diào)度問題要求生成的機械手作業(yè)排序不能有重復的作業(yè)，對此選擇了單點交叉、順序交叉、部分映射交叉和兩點交叉四種可行的交叉方法。通過分析和實驗確定最終的交叉方案為兩點交叉[6]。

3.3 變異操作

變異可以使算法跳出局部最優(yōu)值，在更廣的范圍內(nèi)搜索全局值。反序變異操作在搜索空間中搜索到的領域聚集度較高，本算法采用反序變異操作。

3.4 選擇操作

采用經(jīng)典輪盤賭選擇方法能夠保證優(yōu)良基因得到延續(xù)，而且保證基因的多樣性。將種群中的最優(yōu)個體隨機替換掉下一代中的某個體，以保持遺傳算法的尋優(yōu)能夠不斷進行[5]。

3.5改進遺傳算法流程

如圖2所示，將遺傳算法與初始種群、交叉操作、變異操作、適應度函數(shù)計算等相結(jié)合，得到求解有晶圓滯留時間約束的集束型裝備調(diào)度問題的改進遺傳算法。

4 仿真實驗

改進遺傳算法的參數(shù)設置如下：種群規(guī)模100，最大迭代次數(shù)為150，交叉率為0.4，變異率為0.7。集束型裝備的生產(chǎn)數(shù)據(jù)如表1所示，其中任意機械手搬運作業(yè)的空載時間為cij=5|i-j|，其中i和j為工位號，ai為加工時間，bi為滯留時間上界，di為機械手負載搬運時間。經(jīng)過不到1秒計算得到最優(yōu)解為165秒。

[工位號＼&ai＼&bi＼&di＼&0＼&30＼&1000＼&10＼&1＼&100＼&110＼&10＼&3＼&30＼&60＼&10＼&4＼&125＼&130＼&20＼&]

5 結(jié)論

本文提出的算法有效地解決了在具有晶圓滯留時間約束的集束型裝備的調(diào)度過程中，由于滯留約束限制而產(chǎn)生的沖突和死鎖的問題，為此類集束型裝備的調(diào)度問題提供了一個可行的方法。實驗結(jié)果驗證了提出方法的有效性。

參考文獻：

[1] 李林瑛，盧睿，臧潔. 加工多類型晶圓的集束型裝備調(diào)度模型[J]. 數(shù)學的實踐與認識， 2016， 46（16）：152-161.

[2] 周炳海， 黎明. 考慮多晶圓流的集束型設備群調(diào)度方法[J]. 東北大學學報自然科學版， 2016， 37（5）：697-701.

[3] 劉曉冰， 焦璇， 寧濤，等. 基于雙鏈量子遺傳算法的柔性作業(yè)車間調(diào)度[J]. 計算機集成制造系統(tǒng)， 2015， 21（2）：495-502.

[4] 王躍崗， 車阿大. 基于混合量子進化算法的自動化制造單元調(diào)度[J]. 計算機集成制造系統(tǒng)， 2013， 19（9）：2193-2201.

[5] Pengyu Yan， Ada Che， Naiding Yang， et al. A tabu search algorithm with solution space partition and repairing procedure for cyclic robotic cell scheduling problem[J]. International Journal of Production Research， 2012， 50（22）：6403-6418.

[6] 楊煜俊， 龍傳澤， 陶宇. 作業(yè)車間類型多機器人制造單元調(diào)度算法[J]. 計算機集成制造系統(tǒng)， 2015， 21（12）：3239-3248.