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

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

關(guān)鍵詞：遺傳算法； 集束型裝備； 半導(dǎo)體制造； 滯留時(shí)間約束

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：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 概述

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

2 問題描述

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

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

3 改進(jìn)遺傳算法

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

3.1 編碼和解碼

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

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

3.2 交叉操作

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

3.3 變異操作

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

3.4 選擇操作

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

3.5改進(jìn)遺傳算法流程

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

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

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

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

5 結(jié)論

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

參考文獻(xiàn)：

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

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

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

[4] 王躍崗， 車阿大. 基于混合量子進(jìn)化算法的自動(dòng)化制造單元調(diào)度[J]. 計(jì)算機(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è)車間類型多機(jī)器人制造單元調(diào)度算法[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2015， 21（12）：3239-3248.