鐘臻怡 楊家榮 呂 偉

（上海電氣集團股份有限公司中央研究院 上海 200070）

1 引言

半導體制造是現今最復雜的制造過程之一，具有多約束、可重入性、多目標、換模等特點，大多數半導體制造過程調度問題已被證明為NP-hard問題，因而給半導體晶圓制造系統建模和優(yōu)化調度帶來極大的復雜性，使其成為學術界的研究熱點。

關于帶換模約束調度問題前人有很多研究。Weng等［1］在調度問題中加入了關于工件加工順序的換模，并以最小化總加權完成時間為目標，提出了一個有效的啟發(fā)式算法。Arnaout等［2］針對換模時間與機器以及工件加工順序有關的非等同平行機調度問題提出了兩階段蟻群優(yōu)化算法，并與禁忌搜索算法等其他啟發(fā)式算法對比，結果表明所提算法的有效性。Arnaout等［3］對上一篇文獻所提做了改進，結果表明改進能夠提高算法的績效。Vallada和Ruiz［4］使用遺傳算法來解決換模時間與機器以及工件加工順序有關的非等同平行機調度問題，并與目前為止的最優(yōu)方法進行比較，驗證了遺傳算法的有效性。Ying等［5］針對換模時間與機器以及工件加工順序有關的調度問題提出了模擬退火算法，該算法運用了嚴格搜索策略以降低搜索難度，使算法能夠更快地找到最優(yōu)鄰域。Fleszar等［6］將關于機器和工件順序的換模加入到非等同平行機調度問題中，以最小化makespan為目標，運用基本蟻群算法（ant colony algorithm，ACO）對該調度問題進行求解。在Costa等［7］研究的非等同平行機調度問題中，換模時間也與工件加工順序有關，并且同時考慮了進行換模操作的有限人力資源，其中，換模的時間與工人的操作熟練度有關，隨后提出了三種遺傳算法，實驗結果表明混合遺傳算法的效果最好。Wang等［8］研究了非等同平行機調度問題，該調度問題以最小化延遲工件數量和最大完工時間為目標，換模時間等約束都均與工件加工順序相關，并且針對小規(guī)模問題提出了數學整數規(guī)劃模型，針對大規(guī)模問題提出了一個指派規(guī)則。

上述文獻在問題域方面主要考慮了基于工件加工順序的換模約束、基于機器和工件加工順序的換模約束、換模時間隨著機器和工件加工順序變化而變化等問題，有些還同時考慮了人力資源等。近年來，為了確保晶圓的加工質量，在實際生產中也會運用到參數調整。目前已有學者將參數調整作為一種特殊的換模考慮到調度問題中。Cai等［9］研究單機調度問題，在帶有普通換模的多工件族單機調度問題的基礎上，考慮了參數調整相關約束，并且提出了簡單的啟發(fā)式算法。

通過對上述研究現狀分析可知，很多文獻都沒有考慮參數調整約束特征。且多以平行機為研究對象，在本文中，為了同時兼顧半導體晶圓制造的可重入性，將研究帶有參數調整過程的可重入流水車間調度問題。

蟻群算法在車間調度問題中應用廣泛［10～12］，但是容易陷入局部最優(yōu)，為了提高蟻群算法的全局搜索能力，本文將分布估計算法［13～14］引入到蟻群算法中。

2 問題描述

在具有L個層次的J個步驟的可重入流水車間調度中，有來自I個工件族的工件待加工，工件族i中的工件加工時間是pi。若第l層的第j臺機器，自從最后一次加工工件族i的工件，連續(xù)加工了ni個或者更多的不屬于工件族i的工件，那么，在下一時刻在該臺機器上加工工件族i時，必須先進行一次參數調整。在同一臺機器上連續(xù)加工不同的工件時，需要進行換模操作。本文研究帶換模約束的可重入流水車間調度問題，試圖在參數調整次數與換模次數之間尋求一個均衡點，以實現系統最小makespan為調度目標。

本問題的假設如下：

1）來自同一工件族的工件之間不需要進行換模；

2）每次參數調整之前必須進行換模；

3）對于調度問題中的第一個工件，不管它屬于哪一個工件族，都不需要進行參數調整，也就是說對于每種工件族在0時刻都有一個隱含的試運行；

4）工件加工沒有優(yōu)先級，即一旦工件的一個工序開始加工，則此工序不允許中斷；

5）各個工序之間沒有有限緩沖或者搬運時間；

6）一臺機器在同一時刻至多只能加工一個工件，且一個工件在任意時刻至多只能在一臺機器上加工。

3 數學模型

相關參數符號如下：

I為一組工件族，用i表示工件族序號；

L為一組待加工的層次，用l表示待加工層次序號；

J為一共有J個待加工步驟或機器，用j表示加工步驟序號；

為第l層的第j個步驟中一組調度的位置，用k表示調度位置的序號；如果工件族i的某一工件的第l層的第j個加工步驟在該層的該步驟中是第k個加工的，那么該工件在該層該步驟的位置用k表示；

pi為工件族i中的工件加工時間；

si為工件族i中的工件準備時間；

qi為工件族i進行參數調整需要的時間；

mi為工件族i所具有的工件數。

決策變量定義如下：

Ci，l，j表示工件族i在第l層的步驟j的完成時間。

根據上述問題描述、模型假設、參數以及決策變量，對所研究的帶換模約束的可重入流水車間調度問題建模如下：

約束（2）表示每個工件族總的加工工件個數不超過每個工件族可加工的工件總數；約束（3）決定工件族i的第l層的步驟j上的k位置上是否需要執(zhí)行換模過程。每臺機器上的第一個工件在加工之前不需要換模，工件計數從0時刻開始，因此，設此外，任何具有負數標識的都設為0；約束（4）判斷工件族i的第l層的步驟j上的k位置上加工之前是否需要進行參數調整。如果機器j在第k-ni到k-1這ni個位置上沒有加工過與工件i同族的工件，那么機器j加工第k位置上的工件族i的工件之前需要進行參數調整方可加工該工件，否則可能導致產品出現質量問題，另外，在0時刻存在一個隱含的參數調整過程，所以約束（4）從k=2開始；約束（5）表明了加工族開始時間要求；約束（6）表明了工件族加工順序要求，直到某個工件族的某一層的前一工序完成后，后一工序才能開始加工；約束（7）表明了工件族加工順序要求，直到某個工件的某一層的最后一道工序完成后，后一層的第一道工序才能開始加工；約束（8）表明了Cmax的時間要求；約束（9）表明了每個位置至多只能有一個工件族可以加工；約束（10）表明了決策變量的范圍。

4 算法構建

4.1 編碼

4.1.1 節(jié)點

搜索空間中節(jié)點的構成如下：（a，pi，si，qi，ni，i，b），a表示工件族i中工件的序號，a∈[0，ci]，ci表示每個工件族中工件的個數，pi表示工件族的加工時間，si表示工件族的準備時間，qi表示工件族的參數調整時間，ni表示工件極限值，i表示工件族序號，I表示工件族數量，b表示節(jié) 點 編 號，，節(jié) 點 總 數 為，節(jié)點用πb=（a，pi，si，qi，ni，i，b）表示，節(jié)點集合為

4.1.2 路徑

螞蟻根據狀態(tài)轉移概率遍歷搜索空間的所有節(jié)點，依次存入禁忌表Tabu中。可選節(jié)點集合Allowed=π-Tabu。禁忌表Tabu中所有節(jié)點構成了蟻群的一條運動路徑，確定了各個層次各臺機器上加工工件的順序，也就是蟻群算法的一個解。在本問題中，有個節(jié)點需要被訪問，假設已訪問R-1個節(jié)點，則禁忌表表示在該臺機器上已訪問的節(jié)點集合，表示該臺機器上總的可選節(jié)點，Allowed=π-Tabu表示當前第R個即將訪問的節(jié)點的可選節(jié)點集合。

4.2 啟發(fā)強度

首先引入如下記號：

m為蟻群中螞蟻數量；

dxy為路徑節(jié)點x和y之間的距離，反映由x到y的啟發(fā)強度。

將m只螞蟻隨機放在m個節(jié)點上作為起點，每只螞蟻以所在節(jié)點為中心，計算其他可選節(jié)點的可能性，可能性越大，該路徑上的啟發(fā)強度就越高。啟發(fā)強度記為dxy由式（11）計算得出：

當節(jié)點y中的工件需要換模時，取ey=1，則d xy較??；否則ey=0。當節(jié)點y中機器最近加工的ni個工件都不來自節(jié)點y中的工件族i時，取fy=1，則dxy較??；否則fy=0。

4.3 狀態(tài)轉移規(guī)則與隨機概率規(guī)則

螞蟻k根據狀態(tài)轉移規(guī)則選擇下一個要訪問的節(jié)點y。狀態(tài)轉移規(guī)則為

其中，ηxs(t)和dxs(t)分別表示t時刻節(jié)點x和s之間的信息素強度和啟發(fā)強度。α和β分別反映了螞蟻運動過程中所積累的信息素和啟發(fā)信息在選擇路徑中的相對重要性。

隨機概率規(guī)則給出了螞蟻k在t時刻位于節(jié)點x進行某次移動時選擇前進到節(jié)點y的概率：

當(t)大于等于隨機概率值時，螞蟻選擇節(jié)點y為下一前進方向。

為了改進現有蟻群算法容易陷入局部最優(yōu)解的問題，把分布估計算法中的全局優(yōu)化思想引入蟻群算法。首先在狀態(tài)轉移規(guī)則中考慮各個節(jié)點之間的概率分布因子對螞蟻搜索的影響，則狀態(tài)轉移規(guī)則為

其中，pxs表示節(jié)點x與s之間被訪問的次數。

隨機概率規(guī)則為

4.4 信息素的衰減與釋放

信息素隨著時間不斷釋放與衰減，釋放主要源自于螞蟻運動時在路徑上留下的信息素的加強；衰減主要源于模擬生態(tài)的信息素揮發(fā)。具體根據式（16）調整［15］：

4.5 算法具體步驟

步驟1：初始化相關參數。

步驟2：將迭代次數t初始值設定為0。

步驟3：隨機選擇每只螞蟻的初始節(jié)點。

步驟4：計算每只螞蟻每個當前時刻的可選工序集以及對應啟發(fā)強度，根據本文所提出的概率轉移規(guī)則選擇前進的節(jié)點，直到所有螞蟻遍歷所有節(jié)點。

步驟5：更新信息素。

步驟6：令t=t+1，如果達到最大迭代次數T則停止，否則轉到步驟3。

5 仿真實驗分析

5.1 參數設計

本實驗結果通過makespan值和CPU時間來衡量，且設定最大迭代次數為100。

本實驗測試了蟻群算法和所提出的混合蟻群分布估計算法（hybrid ant colony algorithm with esti?mation of distribution algorithm，ACO-EDA）求解各種不同規(guī)模的帶換模和參數調整的可重入流水車間調度問題的性能。問題實例隨機產生如下：I={3 ，5，7} ，M={4 ，6，8} ，J={3 ，4，5} ，L={1，2，3}；每種工件族的加工時間、換模時間和參數調整時間以及參數調整極限值分別由[45，65]，[5，10]，[45，65]，[3，5]離散均勻分布隨機產生。I，M，J，L共有3×3×3×3=81種規(guī)模，對每種規(guī)模隨機產生和測試10個不同的實例，故本實驗共產生和使用810個測試實例。蟻群算法的參數設置：初始信息素量為5，螞蟻數量為I*M，迭代次數T=100，α=2，β=5，γ=0.3。

本文算法采用以下計算機配置進行實現。CPU：英特爾奔騰雙核T2130 1.86GHz；內存：896MB；電腦系統：Windows XPprofessional；編程語言：C++。

5.2 實驗結果

實驗結果如表1所示，表1中的數據（除最后一行外）都是實驗中相同規(guī)模的10個實例的平均性能。

從表1中可以看出，ACO和ACO-EDA在運行時間方面差不多，但是ACO-EDA幾乎在各種規(guī)模均能比ACO產生更好的解，這是由于EDA考慮了全局信息，將全局信息融入ACO使得ACO-EDA在解的質量方面優(yōu)于ACO。

表1 不同規(guī)模問題的實驗結果

44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81平均5×6×5×2 5×6×5×3 5×8×3×1 5×8×3×2 5×8×3×3 5×8×4×1 5×8×4×2 5×8×4×3 5×8×5×1 5×8×5×2 5×8×5×3 7×4×3×1 7×4×3×2 7×4×3×3 7×4×4×1 7×4×4×2 7×4×4×3 7×4×5×1 7×4×5×2 7×4×5×3 7×6×3×1 7×6×3×2 7×6×3×3 7×6×4×1 7×6×4×2 7×6×4×3 7×6×5×1 7×6×5×2 7×6×5×3 7×8×3×1 7×8×3×2 7×8×3×3 7×8×4×1 7×8×4×2 7×8×4×3 7×8×5×1 7×8×5×2 7×8×5×3 14163.2 23611.6 5269.8 11739.2 19385.1 6896 15953.8 25882.9 8650.8 20158.8 33487.1 3591.2 8405.1 13979.1 4676.4 11214.8 18783 5913.2 14181.5 23478.5 5956 13688.6 22185.9 7643.8 18892.2 30466.6 9843 23292.2 38599.5 8499.1 19329.4 31472.6 11345.6 26458.3 43386 14163.5 33143.3 53848.1 12061.1 14667.3 20394.2 11189.9 24210.7 34817 16395.1 31484.9 47757 19183 39257 59511.4 4902.6 7529.8 11830.8 6602.5 10685.7 16649.3 7517.7 14770 20811.8 12676.7 26031.9 37122.1 17915.2 28864.7 38125.6 15248.5 38967.1 47475.7 25690.9 51617.7 70495.7 27753 77736 97639.8 40894.9 75697.9 106406 18132.8 13984.5 23168.5 4446.7 11663 18799 6277 16311.6 26219 7714.5 20483 33099.1 3050 8182.9 13693.3 3984.3 11116.9 18570.3 4880.1 13549.3 23598.3 5237.3 13440.8 22550 6928.1 18610.9 30607.8 9125.8 23722.4 38361.1 8040.8 19371 31518.5 10837.1 26523.7 42932.2 14081.3 32908 54214.4 11830 13290.7 19695.1 9291.1 17347.6 26556.7 12523 23795.2 39060.1 19392.4 40525 60508.7 5524 8673.1 12522.8 6941.6 12949.2 18041.3 8493.2 15875.5 22129.9 14769.9 28356.2 32082 13648.8 35678.6 37038.7 14967 34319.8 45721.2 26768 42430.8 66394.1 26746.8 58277.5 80458.3 34530.7 94462.3 116866 17745.8問題工件種類×工件個數×步驟數×層次數ACO makespan CPU/s ACO-EDA makespan CPU/s

圖1、2、3分別描述了兩個算法在I=3，I=5，I=7時的270個問題的平均進化曲線。縱軸表示每個算法的270個例子的平均makespan值。從各圖中均可以看出，兩種算法的初始解十分接近，然而不同之處在于，ACO收斂速度更快，ACO-EDA雖然收斂速度不如ACO，但是最終解的質量優(yōu)于ACO。這是由于ACO雖然收斂速度快，但是容易陷入局部最優(yōu)，而ACO-EDA考慮了全局信息，從而進行全局優(yōu)化。

圖1 I=3時的進化曲線

圖2 I=5時的進化曲線

圖3 I=7時的進化曲線

6 結語

本文對帶換模約束的可重入流水車間問題進行了研究，提出了混合蟻群分布估計算法，將分布估計算法引入到蟻群算法中。首先對該問題進行了問題描述，并以系統makespan最小化為目標建立數學規(guī)劃模型，隨后對蟻群算法進行了針對本問題的編碼設計和啟發(fā)強度設計，并將分布估計算法引入到蟻群算法中，提高了蟻群算法的全局搜索能力。最后實驗結果證明混合蟻群分布估計算法在運行時間差不多的情況下，幾乎在各種規(guī)模下均能比蟻群算法產生更好的解，說明了引入分布估計算法的有效性。