蔣小康，張 朋，呂佑龍，趙新明，張 潔

(1. 東華大學(xué) 機械工程學(xué)院， 上海 216020； 2. 上海交通大學(xué) 機械與動力工程學(xué)院， 上海 200240)

作為先進制造業(yè)的典型代表，半導(dǎo)體制造具有可重入、混線生產(chǎn)、批處理加工、機器負載不均衡及良率隨機等不同于傳統(tǒng)生產(chǎn)線的混合特性，因而被認為是當今最復(fù)雜的制造過程之一[1].按實際工作區(qū)域，半導(dǎo)體制造廠可分為爐管區(qū)、刻蝕區(qū)、黃光區(qū)和薄膜區(qū).其中，爐管區(qū)主要用于氧化、擴散與低壓化學(xué)氣相沉積等熱處理過程，該區(qū)域以批處理模式組織生產(chǎn)，由于生產(chǎn)過程加工時間長，在制品多，因而被認為是半導(dǎo)體制造過程的主要瓶頸之一.目前，爐管區(qū)的生產(chǎn)組織主要依賴于現(xiàn)場操作人員的經(jīng)驗，存在很大局限性，因此急需制定快速有效的調(diào)度策略，縮短晶圓的生產(chǎn)周期，提高企業(yè)的生產(chǎn)效益.

爐管區(qū)包含數(shù)十臺不同類型的設(shè)備，在實際生產(chǎn)過程中，晶圓動態(tài)地重復(fù)訪問爐管區(qū)，以完成不同晶圓層的加工.在生產(chǎn)調(diào)度領(lǐng)域，爐管區(qū)調(diào)度通常被歸納為一類帶重入特性的并行批處理機調(diào)度問題.

Ikura等[2]于1986對批調(diào)度問題進行了最早的研究，認為批調(diào)度是不同于經(jīng)典調(diào)度問題的一類具有強應(yīng)用背景的新型調(diào)度問題，工件以一定條件組成一批進行加工.復(fù)雜重入多機臺并行批調(diào)度問題是在半導(dǎo)體爐管區(qū)生產(chǎn)過程中提煉出的一類符合實際情況調(diào)度題.近年來，國內(nèi)外已經(jīng)有學(xué)者和工業(yè)人士在半導(dǎo)體爐管區(qū)調(diào)度的理論和實踐方面做了大量的工作，但這些工作具有一定的局限性，并未完全考慮到爐管區(qū)的實際加工約束與限制.關(guān)于單一機臺組的研究較多，將爐管區(qū)從半導(dǎo)體制造生產(chǎn)線上剝離出來，未考慮到前后道工序?qū)t管生產(chǎn)的影響，更未考慮到設(shè)備之間的等待時間約束[3-5].Parsa等[3]針對最小化總加權(quán)滯后的單一機臺組調(diào)度問題，找到預(yù)組批的最佳方案，提出了1個動態(tài)規(guī)劃算法，并在此基礎(chǔ)上提出了多個啟發(fā)式算法，在求解小規(guī)模問題上具有明顯優(yōu)勢.Cheng等[4]針對以最小化制造期的相同并行機調(diào)度問題，提出了一類改進的蟻群優(yōu)化算法，該算法尤其適合大規(guī)模單一機臺組調(diào)度問題.Parsa等[5]針對最小化平均流動時間(MFT)的單一機臺組調(diào)度問題，提出了1個最大-最小蟻群算法，證明了其算法優(yōu)于CPLEX和幾種啟發(fā)式算法，但其求解時間較長.有部分研究[6-8]考慮了半導(dǎo)體生產(chǎn)線上爐管區(qū)前后道工序，但忽略了重入性，僅對單一層上晶圓的生產(chǎn)進行調(diào)度，未考慮全局優(yōu)化.Ham等[8]針對考慮等待時間限制的兩機臺組調(diào)度問題，提出了一種整數(shù)規(guī)劃算法 i-RTD，解決了簡單的兩機臺組的實時調(diào)度.根據(jù)Ahmadi等[9]引入的多工藝多機臺組調(diào)度問題的定義，用δ、β、→分別代表離散加工機臺組、批加工機臺組和流動方向，批處理機臺組前存在兩種可能的加工系統(tǒng)，分別為δ→β和β1→β2，代表批處理機臺組前存在離散加工機臺組和批處理機臺組前一機臺組依舊為批處理加工機臺組.李程[10]針對半導(dǎo)體爐管區(qū)瓶頸設(shè)備的β1→β2型批調(diào)度問題，以瓶頸機臺的連續(xù)滿批運行為目標，在考慮爐管區(qū)工藝和設(shè)備容量限制的前提下，提出了一種理想的基于規(guī)則的批調(diào)度算法(RSBP)，解決了重入環(huán)境下爐管區(qū)瓶頸設(shè)備的實時派工問題.賈文友等[11]對爐管區(qū)β1→β2問題進行了更加詳細的描述，考慮了不兼容工藝菜單、有限的等待時間以及重入流特性的爐管區(qū)調(diào)度問題，為提高瓶頸設(shè)備的利用率，提出了1個拉式調(diào)度算法，其中包括3個子算法，以更好地進行瓶頸設(shè)備的組批派工.實驗在作者設(shè)計的半導(dǎo)體晶圓加工仿真平臺上進行，通過評價平均流動時間、產(chǎn)量以及瓶頸機臺利用率3個指標，證明其結(jié)果均優(yōu)于遺傳算法.文獻[10-11]在爐管區(qū)調(diào)度問題上進行了卓有成效的工作，但未考慮到爐管區(qū)內(nèi)機臺組上不同工藝菜單之間的設(shè)備準備時間.元啟發(fā)式算法是解決大規(guī)模組合優(yōu)化算法問題常用的方法之一，蟻群優(yōu)化(ACO)作為一種典型的智能構(gòu)建型元啟發(fā)式算法，通過模擬自然界中螞蟻的覓食行為，借助信息素濃度τ尋找最短路徑，其并發(fā)多線程搜索機制可充分利用全局信息已獲得優(yōu)化搜索解，已在眾多調(diào)度領(lǐng)域得到有效驗證[12-13].

基于上述分析，當前研究未全面考慮實際加工特點及各類約束，在求解方法上多以精確算法和基于規(guī)則的調(diào)度算法為主，因此僅能在有限時間內(nèi)求解小規(guī)模調(diào)度問題，而在大規(guī)模問題上求解質(zhì)量較差.現(xiàn)有爐管區(qū)智能算法大都應(yīng)用于約束較為簡單的問題，缺乏各類約束且僅使用智能算法，求解時間較長，難以滿足爐管區(qū)快速響應(yīng).因此，本文針對一類包含復(fù)雜重入流、不兼容工藝菜單、不同準備時間、等待時間約束及工件動態(tài)到達的爐管區(qū)β1→β2調(diào)度問題，以最小化晶圓平均流動時間為目標，構(gòu)建爐管區(qū)β1→β2調(diào)度模型.將調(diào)度過程分成工件組批、設(shè)備選擇和批次排序3個相互關(guān)聯(lián)的階段，設(shè)計規(guī)則與智能算法結(jié)合的混合算法，針對工件組批階段設(shè)計了可變閾值的組批策略，針對復(fù)雜約束設(shè)計了基于混合蟻群算法HACO的IVTRP-ACO分層調(diào)度算法.

1 問題建模

1.1 問題描述

以某多產(chǎn)品半導(dǎo)體生產(chǎn)線的爐管區(qū)兩并行批處理機臺組調(diào)度問題為研究對象，通過對爐管區(qū)工件Lot(即晶圓卡，通常由25片晶圓組成)的工藝路線進行分析，建立半導(dǎo)體生產(chǎn)線爐管區(qū)的問題模型，如圖1所示.考慮的設(shè)備集包括兩個并行批處理機臺組MG1，MG2和1個后續(xù)加工設(shè)備集MG3.MG1機臺組為晶圓生產(chǎn)中的常壓柵氧化爐管，MG2機臺組為低壓化學(xué)氣相沉積爐管，兩機臺組均包含若干功能相同的爐管設(shè)備，MG3為工件該層加工剩余工藝加工設(shè)備集簡稱.將晶圓處于MG1機臺組的加工過程稱為階段1，即β1，其中包括前后兩道工序F1與F2，分別存在s、h類工藝；處于MG2機臺組的加工過程稱為階段2，即β2，僅包含一道工序F3，存在g類工藝.圖1中，工藝1為爐管加工各工序的第一類工藝，實際的爐管區(qū)生產(chǎn)過程具有5個約束：①重入流，如圖1所示，重入流包括兩部分，其一為MG1機臺組內(nèi)的前后道工藝，在前道工藝F1完成后還需重新進入MG1機臺加工后道工藝F2；其二為某層加工完后，下一層工藝要求晶圓需重新進入爐管區(qū)進行加工，以形成理想電路.工件在設(shè)備上的流動情況可表示為MG1→MG1→MG2→MG3→…→MG1.②不兼容工藝菜單.不同工藝類型的工件不能放在一批進行加工.③不同準備時間.當批處理機前后加工不同工藝的產(chǎn)品時，設(shè)備存在不同的準備時間.④等待時間約束.在β1加工完成后必須在規(guī)定時間內(nèi)進入β2內(nèi)加工，否則工件需要返工乃至報廢.⑤動態(tài)到達.工件是動態(tài)到達的，工件到達時間，加工類型與加工時間均未知.

綜上所述，本文研究的問題為考慮多產(chǎn)品復(fù)雜重入流、不兼容工藝菜單、不同準備時間、等待時間約束和工件動態(tài)到達的爐管區(qū)β1→β2調(diào)度問題，以最小化工件平均流動時間為目標設(shè)計優(yōu)化算法.

本文的調(diào)度模型給出如下假設(shè)：① 各工藝類型的加工時間和設(shè)備的加工能力已知； ② 任一工件只有前一道工序完成后方可進入下一道工序；③ 每臺設(shè)備都可加工多個工件，但有容量限制；④ 工件的每道工序只能在一臺設(shè)備上加工；⑤ 工件以及工件所在批次的加工時間只與工藝有關(guān)，而與設(shè)備無關(guān)；⑥ 屬于同一批次的工件一旦進行加工則不能中斷，屬于非搶占式加工；⑦ 設(shè)備加工不同批次的準備時間與批次的加工順序與工藝類型有關(guān).

1.2 爐管區(qū)β1→β2調(diào)度問題數(shù)學(xué)模型

爐管區(qū)β1→β2調(diào)度問題模型為

(1)

(2)

(3)

(4)

(5)

WT2,i≤QT ?i

(6)

Cw ki=rw ki+pkji?w,k,i

(7)

rw k′i=Cw ki+WTk′,i+RTkj′，j

(8)

?w,k,i,j,k′=k+1

(9)

?w,k,i

rw′i=Cw i+HTw i?w,i,w′=w+1

(10)

rw k′i≥rw ki?w,i,k′=k+1

(11)

rw，1,i≥0 ?w,i

(12)

RTkj，j′=Xj,j′RTkj，j′

(13)

式中：n為工件總數(shù)，工件索引i=1,2,…,n；Fi為工件i的流動時間；M為機臺總數(shù)，機臺索引m∈M=[1,N1+N2]，N1、N2分別為β1、β2內(nèi)爐管數(shù)量；Mk為工序k的并行機數(shù)量；mk為工序k可加工機臺的編號，

Ow ki為工件i的第w層的第k道工序；B1、B2分別為β1、β2內(nèi)爐管加工最大容量；w為工件i當前加工層數(shù)；k為工序索引，k∈K={1,2,3}； WTi,k,k+1為工件i在第k道工序和下一工序間的等待時間；QT為工序2與工序3之間的等待時間上限；ri、Ci分別為工件i的釋放時間及完工時間，其中Ci=CLi3i(工件i最后一層的最后一道工序的完工時間)，F(xiàn)i=Ci-ri；rw i、Cw i分別為工件i的第w層的到達時間與完工時間；pkji為工件i在工序k上加工工藝為j的加工時間；rw ki、Cw ki分別為工件i的第w層的第k道工序的開始加工時間與完工時間；HTw i為工件i的第w層的后續(xù)加工時間，即MG3加工時間；RTkj，j′為工序k的當前工藝類型j與設(shè)備之前加工類型j′之間的準備時間(不同工藝類型有工藝準備時間/相同工藝類型無工藝準備時間)。

決策變量：rw kim為工件i的第w層的第k道工序的開始時間，該操作在機器m上加工。

式(1)表示目標為最小化平均流動時間；式(2)表示F1和F2共用一個并行機臺組，機臺總數(shù)是β1，β2內(nèi)并行機數(shù)量之和；式(3)表示Ow ki加工機臺的唯一性；式(4)和(5)表示設(shè)備的最大加工容量限制；式(6)表示第二道工序與第三道工序之間有等待時間的限制；式(7)表示工件i的第w層的第k階段的完工時間等于開始加工時間與加工時間之和；式(8)表示第k′階段的開始加工時間等于階段k的完工時間與上一階段的等待時間和準備時間之和，k′=k+1；式(9)表示工件i第w層的完工時間為第w層三階段的加工時間、到達時間、等待時間與準備時間之和；式(10)表示工件i的w′層到達時間為w層的完工時間與w層的后續(xù)加工時間之和，w′=w+1；式(11)表示工件必須嚴格地按照工藝流程依次在各道工序上加工，同一工件只有在上一道工序加工完成之后，后一道工序才能開始加工；式(12)表示沒有工件可以在開始時間前進行加工；式(13)表示相同設(shè)備的準備時間與前后工藝的類型相關(guān)，工藝菜單相同無工藝準備時間，工藝不同時則存在工藝準備時間.

2 基于混合蟻群算法的分層調(diào)度

2.1 基于混合蟻群算法的分層調(diào)度方法架構(gòu)

在爐管區(qū)生產(chǎn)中，MG1和MG2都屬于并行批處理機臺組，故可將其調(diào)度問題拆分為3個子問題為各個緩沖區(qū)中不同工件的組批問題，并行機臺組中的設(shè)備選擇問題以及組批完成后批次排序問題.本研究基于時間序列模型的分解策略，將整個調(diào)度時間軸分解為多個時間域T，在各時間域內(nèi)針對各子問題形成3個求解層次為組批層，設(shè)備選擇層和批次排序?qū)?通過將分段時域內(nèi)的調(diào)度問題進行分層處理，有效降低了問題的復(fù)雜度，通過設(shè)計各層的求解算法，分別實現(xiàn)子問題的求解.

由于爐管區(qū)調(diào)度對整個半導(dǎo)體生產(chǎn)線影響巨大，要求調(diào)度方案兼具較高求解質(zhì)量和較低的計算時間，為了達到此目標，本文將綜合利用調(diào)度規(guī)則求解速度快與元啟發(fā)式算法求解質(zhì)量高的優(yōu)勢，保證解的高質(zhì)量的同時，提高求解速度.時域T內(nèi)每層的具體處理方法如下為首先通過設(shè)計啟發(fā)式規(guī)則對動態(tài)到達的工件構(gòu)造組批問題求解，然后利用設(shè)備指派規(guī)則得到設(shè)備選擇問題解，最后在人工蟻群在分布于問題空間的信息素指引下，針對各批次任務(wù)逐步構(gòu)造批次排序問題解.時域T內(nèi)基于混合蟻群算法的爐管區(qū)分層調(diào)度方法框架見圖3.

2.2 可變閾值組批算法

針對工件組批問題，常用的組批方法包括啟發(fā)式規(guī)則和元啟發(fā)算法.由于啟發(fā)式規(guī)則結(jié)構(gòu)簡單、便于操作，因而在實際生產(chǎn)中應(yīng)用廣泛.爐管區(qū)調(diào)度過程的組批階段需滿足兩個約束：① 不兼容工藝菜單約束，僅相同工藝菜單的Lot才可以被分為同一批；② 設(shè)備容量約束，批中的Lot數(shù)量不能超過爐管的容量.針對工件到達時間，優(yōu)先級等未知的特點，設(shè)計了一種基于最小加工批量(MBS)規(guī)則的組批算法.

MBS規(guī)則：設(shè)B為批加工設(shè)備的最大加工批量，X為工藝菜單對應(yīng)緩沖區(qū)工件的個數(shù)，a為最小批量個數(shù)，只有當緩沖區(qū)中工件數(shù)至少達到a(a≤B)時才開始加工一批工件.即在調(diào)度時刻，即使機器空閑，但是緩沖區(qū)中工件個數(shù)小于最小組批個數(shù)，設(shè)備仍然保持空閑狀態(tài)，直至滿足組批條件，具體操作為：0≤X

MBS規(guī)則中的最小組批個數(shù)是算法的關(guān)鍵，在實際應(yīng)用中主要由人工經(jīng)驗確定.其中a=1和a=B為兩個特殊情況為.a=1表示只要緩沖區(qū)有工件就以一個工件為一批進行加工；a=B是指只有緩沖區(qū)工件數(shù)滿足最大加工批量才可以組批并加載到設(shè)備加工.

雖然MBS在半導(dǎo)體生產(chǎn)線上大量應(yīng)用，但其缺陷在于MBS屬于固定閾值策略，對變化的加工環(huán)境適應(yīng)性較差.Akcali等[14]針對這一缺陷，在多產(chǎn)品混合的批調(diào)度問題中提出了基于產(chǎn)品數(shù)量與產(chǎn)品類型的可變閾值控制策略VTPP(Variable-Threshold-by-Product Policy)與VTRP(Variable-Threshold-by-Recipe Policy).VTPP針對產(chǎn)品數(shù)量的多少，設(shè)置了兩種不同的閾值，實現(xiàn)對輕重負載的不同響應(yīng)；VTRP則針對不同工藝的加工時間與工件到達時間的關(guān)系，設(shè)計不同的閾值.但文獻中閾值相對固定，需要靠經(jīng)驗確定，還未實現(xiàn)動態(tài)適應(yīng).本文針對這一問題，設(shè)計了改進的基于工藝菜單的閾值可變控制策略IVTRP.

IVTRP規(guī)則繼承VTRP規(guī)則的思路，考慮不同工藝的加工時間與工件到達間隔的關(guān)系，將工件到達分為稀疏、較少、較多及密集4種情況，以權(quán)衡設(shè)備利用率和等待時間.通過對爐管加工特性進行分析，本文設(shè)計了閾值(最小組批個數(shù))由設(shè)備容量，工藝的加工時間與工件到達間隔的關(guān)系決定的IVTRP規(guī)則，動態(tài)地調(diào)整組批時的閾值，為不同工藝菜單的工件提供不同的組批方案.具體操作為

(18)

式中：tr為對于工藝菜單r的可變閾值；λr為工藝菜單r兩工件的到達時間間隔；Pr為工藝菜單r的加工時間.工件到達情況區(qū)間以B+1作為系數(shù)劃分，能更好體現(xiàn)工件達到的密集程度.如工藝菜單r的間隔時間大于菜單r的加工時間的B+1倍，表明工件達到密度極低，更多的等待只會造成設(shè)備利用率的低下.本文針對工件到達稀疏的情況，設(shè)置最小閥值為1，即一有工件到達就加工，以滿足等待時間的約束.當加工時間大于B+1倍到達間隔時，說明在任一組批時刻，工藝r的等待隊列都大于最大容量.因此，針對工件到達密集的情況，最大容量組批能提高設(shè)備的利用率.當工件到達相對稀疏時，結(jié)合實際爐管加工情況[14]，本文確定了規(guī)則中相應(yīng)參數(shù)和取值.兩工件的到達時間間隔通過記錄同一加工工藝的兩工件到達緩沖區(qū)的時間，若存在多個工件則取間隔時間的均值，例如工藝1在調(diào)度時刻的緩沖區(qū)存在3個工件，到達時間分別為2、10、14，則工藝1的工件到達間隔為4.

2.3 設(shè)備選擇規(guī)則

設(shè)備的選擇是指為組批完成后的批從功能相同的機臺組機臺中選擇合適的加工設(shè)備.目前解決方法主要有基于兩工序之間等待時間最短的最小期望延時規(guī)則、最早空閑設(shè)備優(yōu)先安排的最早空閑設(shè)備規(guī)則、機器緩沖長度最短的最短緩沖長度規(guī)則和隨機選擇方法.本研究著重點在于組批與批次排序，所以本文采用高效的最早空閑設(shè)備規(guī)則，即當并行批處理設(shè)備中，設(shè)備出現(xiàn)空閑或者從故障轉(zhuǎn)化為可用時，立即安排批次優(yōu)先級最高的批在該設(shè)備上加工.

2.4 改進蟻群優(yōu)化算法

工件組批完成后，需進入組批加工優(yōu)先級的判斷階段，以確定優(yōu)先加工哪批工件.本文采用具有較強全局搜索能力且搜索質(zhì)量較高的ACO算法解決批次排序問題.下文具體介紹針對問題約束的改進蟻群優(yōu)化算法.

(1) 編碼、解碼機制.本文采用IVTRP規(guī)則組批得到的批次序號作為編碼依據(jù)，蟻群算法中的節(jié)點代表批次.針對MG1和MG2兩階段的編碼分別為{1,2，…，F(xiàn)1+F2}和{F1+F2+1,F1+F2+2，…，F(xiàn)1+F2+F3}.每個階段的蟻群算法搜索都得到一串序列，解碼為批次的優(yōu)先級，即序列最前端為每個階段中最高的優(yōu)先級批次.

(2) 信息素定義和更新.信息素的定義依賴于所研究的對象，本問題中每個階段的批排序問題類似于旅行商問題，即尋找1條最優(yōu)的路徑(順序)，所以τij定義為批j安排到批i之后加工的期望值，S為待排批次集合.初始化蟻群的信息素矩陣元素

其中：ε為一固定值.

分布于問題空間的信息素作為螞蟻間的間接通信媒介，能夠指引螞蟻找到更好的問題解.信息素更新是ACO算法重要的搜索特征，信息素的濃度會由于人工螞蟻在節(jié)點上的釋放而增加，也會由于信息素的蒸發(fā)而不斷減少.信息素的增加能提高人工螞蟻訪問節(jié)點的概率，信息素的蒸發(fā)則能使得算法避免陷入局部最優(yōu).信息素更新分局部更新和全局更新，局部更新是指為減小已選擇過的路徑再次被選擇的概率而做的信息素局部調(diào)整：

τij=(1-ρlocal)τij+ρlocalΔτij

(19)

式中：ρlocal、ρglobal分別為局部和全局信息素蒸發(fā)率；0<ρlocal<1，Δτij=τij(0).

全局更新則指在一次迭代所有螞蟻完成尋優(yōu)后根據(jù)找到的當前最優(yōu)解進行信息素的更新，本文利用在螞蟻已經(jīng)建立了完整的軌跡后再釋放信息素的蟻周系統(tǒng)來更新信息素的方案：

τij(t+1)=(1-ρglobal)τij(t)+

(20)

(21)

(3) 啟發(fā)式信息、候選列表與禁忌表.啟發(fā)式信息直接影響著人工螞蟻對下一節(jié)點的選取.本文中階段1和階段2的啟發(fā)式公式分別為

ηij=Bf1/B1+1/tf1+ωY1

(22)

ηij=Bf2/B2+1/tf2

(23)

公式由三部分組成，第一部分為設(shè)備的容量程度，Bf1和Bf2分別為階段1和階段2批中工件的個數(shù)，B1和B2分別為階段1和階段2并行批處理設(shè)備的最大容量；第二部分考慮了剩余時間，tf1和tf2分別為階段1和階段2的剩余加工時間； 第三部分考慮了等待時間約束，ω為一固定因子，代表等待時間約束的重要程度.

twait為工件在階段1后道工序加工完至階段2加工的等待時間，當twait接近等待時間限制時，使啟發(fā)式信息急劇上升，表明優(yōu)先選取該批進行加工，以保證機臺組之間的時間約束.啟發(fā)式信息中Bf1/B1表明當批中工件數(shù)越接近滿批，該批被選中的概率越高.批的剩余加工時間越小，表明工件越緊急，被選中的概率越高.

(4) 解的構(gòu)建.螞蟻按照如下步驟構(gòu)建可行解為.

步驟1將螞蟻放置在0的位置上.

(24)

D轉(zhuǎn)移概率計算公式為

(25)

步驟3判斷候選表是否為空，若是，則結(jié)束，得到批的序列，若不是，則轉(zhuǎn)步驟2.

(5) 改進ACO算法描述.

步驟1初始化禁忌表、候選表、α、β、qm0、螞蟻數(shù)量、ρlocal、ρglobal等.

步驟2初始化iter=0(iter為迭代次數(shù))，τij(0)初始化為常數(shù)ε，Δτij(0)初始化為0.將螞蟻置于初始點上.

步驟3將初始點置于當前解集中；對螞蟻按照狀態(tài)轉(zhuǎn)移規(guī)則為作業(yè)i選擇下一個未遍歷的作業(yè)j; 移動螞蟻至節(jié)點Vij, 將節(jié)點Vij放置當前解集中,按局部更新策略方程修改軌跡強度.

步驟4判斷路徑下工件的等待時間約束是否滿足，若是則轉(zhuǎn)步驟5，否則刪除不可行解，轉(zhuǎn)步驟5.

步驟5計算各螞蟻的目標函數(shù)值Zδ(δ=1,2,…,M′),M′為螞蟻數(shù)目比較所得最小值，記錄當前的最優(yōu)解.

步驟6判斷迭代次數(shù)是否到達其最大值，若是則轉(zhuǎn)步驟8；否則iter=iter+1，轉(zhuǎn)步驟7.選擇各禁忌表目標值最小的作為當前解決方案.

步驟7按全局更新策略方程修改軌跡強度，重復(fù)步驟3、4、5、6.

步驟8輸出當前最優(yōu)解(批的一個排序).

3 實驗與分析

根據(jù)某晶圓制造廠爐管區(qū)實際生產(chǎn)數(shù)據(jù)，設(shè)計多組不同規(guī)模的測試算例驗證算法的性能.仿真試驗使用C語言實現(xiàn)IVTRP-ACO等算法，在配置為AMD E-450 1.65 GHz的CPU，2G內(nèi)存的PC機上進行運行.具體問題描述信息見表1.

由表1可知，調(diào)度問題是B為8的兩并行批處理機臺組調(diào)度，調(diào)度周期為一個月，考慮晶圓制造的如下特性：① 重入特性，主要體現(xiàn)在考慮Lot的加工層數(shù)、后續(xù)加工時間等信息； ② 工件的不兼容工藝菜單為不同加工工藝之間不能被同時加工，其中階段1 MG1機臺組前后道工序分別存在4種和8種工藝類型，階段2 MG2機臺組存在4種加工類型，各類型對應(yīng)加工時間從某一實際加工范圍內(nèi)選?。虎?不同準備時間為爐管對不同工藝菜單產(chǎn)品加工需要準備時間，這是由物理化學(xué)特性決定的，不同工藝可能使用的氣體，溫度等都大不相同，所以工藝準備時間也不同.本文考慮工藝間準備時間在[5,20]間隨機產(chǎn)生，且當相同工藝菜單之間無工藝準備時間，工藝準備時間與加工順序有關(guān)，先加工菜單i再加工菜單j與先加工菜單j再加工菜單i的準備時間也不同.若爐管所加工前后兩個批次的工藝菜單相同，則準備時間為0；④ 機臺之間加工等待時間與晶圓運輸時間.

表1 調(diào)度問題描述數(shù)據(jù)Tab.1 Description data of scheduling problem

3.1 算法參數(shù)設(shè)計

對蟻群算法性能起關(guān)鍵作用的參數(shù)有信息素與啟發(fā)式重視程度、信息素揮發(fā)系數(shù)、迭代次數(shù)、偽隨機參數(shù)以及螞蟻個數(shù)等[12]，本節(jié)采用田口實驗法來確定各實驗參數(shù)的取值.針對單層爐管區(qū)并行批調(diào)度問題，其關(guān)鍵影響因素包括工件數(shù)量、加工類型、加工時間、工件到達時間.除加工時間外，所采用的算例如表1，其中加工時間分別服從[10,30]、[10,30]和[10,60]之間的均勻分布，在該算例條件下，設(shè)計了7個因子3水平的18次實驗的L18(37)直交表進行參數(shù)的選擇.其中選取了7個對蟻群算法影響較大的因素[12,15]作為實驗中的7個因子，其各因子的3個水平取值分別為信息素濃度重視程度α{0.95,0.9,0.85}、啟發(fā)式信息素濃度重視程度β{0.95,0.9,0.85}、局部信息素蒸發(fā)率ρlocal{0.15,0.1,0.05}、全局信息素蒸發(fā)率ρglobal{0.15,0.1,0.05}、迭代次數(shù)iter{50,80,100}、偽隨機參數(shù)qm0{0.15,0.1,0.05}和初始化信息素濃度Q{40,50,60}.實驗結(jié)果如表2所示.

通過統(tǒng)計平均值，得到田口實驗的響應(yīng)圖，如圖4所示.

通過田口實驗分析方法對圖4中的數(shù)據(jù)進行分析，圖中數(shù)字1～3代表對應(yīng)因素的不同水平，如α1代表信息素濃度重視程度α取0.95.晶圓平均流動時間屬于望小特性，由此可得各因素的較優(yōu)的實驗數(shù)據(jù).綜上所述，IVTRP-ACO算法基本參數(shù)為：α取0.85，β取0.9，ρlocal取0.05，ρlocal取0.15，iter 取100，qm0為0.15，Q取40.除此之外蟻群算法的另一個重要參數(shù)-螞蟻個數(shù)，在本文中將螞蟻個數(shù)設(shè)置為組批完成后批的個數(shù)， 這樣動態(tài)地改變螞蟻個數(shù)使得搜索時間減少同時能保證求解質(zhì)量[15].

表2 田口試驗方案直交表設(shè)計及結(jié)果Tab.2 Design and results of Taguchi experiment of orthogonal table

3.2 算法性能對比分析

為了驗證本文所提出的基于混合蟻群算法的分層調(diào)度算法的性能，采用批處理調(diào)度中常用的7種調(diào)度方法FFLPT-LPT[16]、FFERT-LPT[16]、FFLPT-SPT、MBS-LPT、IVTRP-LPT、BRFFERT-AR[16]、遺傳算法(GA)[17]以及ILOG公司的CPLEX工具與本文提出的 IVTRP-ACO調(diào)度算法進行對比.上述方法主要包括組批策略與排序策略兩部分，設(shè)備選擇都采用最早空閑規(guī)則選取，實驗一對比各算法的平均流動時間驗證各階段算法的有效性；實驗二將IVTRP-ACO與啟發(fā)式算法、遺傳算法對比，進一步驗證IVTRP-ACO算法的優(yōu)越性.表3為實驗的所設(shè)計的對比算例.

3.2.1與無IVTRP的算法對比 為了驗證本文針對組批層提出的IVTRP規(guī)則與批次排序?qū)犹岢龅母倪M蟻群算法的有效性，將本文提出的含IVTRP組批規(guī)則的IVTRP-LPT算法、IVTRP-ACO算法與目前解決并行批處理設(shè)備較優(yōu)的4個算法[16]進行對比，分析本文提出的算法在爐管區(qū)并行批處理機調(diào)度中減小晶圓平均流動時間的有效性與性能.4個對比算法分別采用表3中的1、4、5、6.

表3 對比算例示意表Tab.3 Comparison of example tables

本文在組批方法上采用經(jīng)典的FFLPT組批規(guī)則，MBS規(guī)則和本文提出的IVTRP規(guī)則進行比較.批排序方法上應(yīng)用SPT規(guī)則、LPT規(guī)則與提出的改進蟻群算法進行比較.為了更加直觀、準確的體現(xiàn)出算法的性能，算法將在每個測試算例上均運行10次，統(tǒng)計出這10次的平均值用于對比.衡量的指標有晶圓平均流動時間和CPU運行時間.其中t為運行時間.

通過對比算例1、4、5，分別采用FFLPT規(guī)則，MBS規(guī)則和IVTRP規(guī)則進行分批，批排序和設(shè)備選擇均一致，且并行批處理設(shè)備數(shù)為4.

分析實驗結(jié)果可知，CPLEX精確解方法雖能得到較優(yōu)解，但是計算耗時過長，且在規(guī)定時間內(nèi)解的質(zhì)量與工件負載有關(guān).圖5為FFLPT-LPT、MBS-LPT、IVTRP-LPT的平均流動時間，圖6為相應(yīng)的運算時間.可知不同工件負載下前兩種算法的效果相當，且計算時間也相當，但均遜色于IVTRP-LPT算法.比如當τ=0.5時，使用IVTRP組批規(guī)則的算法的晶圓平均流動時間僅為MBS與FFLPT規(guī)則的73%.3種負載下IVTRP規(guī)則的效果均優(yōu)于MBS與FFLPT 35%以上，說明IVTRP規(guī)則在工件動態(tài)到達時的組批效果明顯優(yōu)于MBS與FFLPT.同時可以看出，當工件負載變大時，IVTRP-LPT的求解質(zhì)量有輕微減低，但是減低幅度在1%以內(nèi)，可知IVTRP規(guī)則在求解爐管區(qū)組批問題中穩(wěn)定性較高.從實驗結(jié)果可知，考慮了工件到達間隔與加工時間的可變閾值策略的確能很好地提高組批效果，對實際加工做出動態(tài)反映當τ從0.5增加到1時，MBS-LPT算法質(zhì)量有小幅波動，這是由于當τ過小使得工件間隔時間延長，同時爐管區(qū)加工時間長，容易造成爐管工作時經(jīng)常不能滿批，工件等待時間加長，造成改進平均流動時間的效果不好.但當τ過大時，容易造成緩沖區(qū)堆積，間接造成等待時間加長.因此，當τ=0.75時算法的性能更優(yōu).綜上所述，IVTRP規(guī)則在工件動態(tài)到達情況下效果較好，且質(zhì)量穩(wěn)定，尤其在工件負載τ=0.75時質(zhì)量最為穩(wěn)定.

通過對比IVTRP-LPT、IVTRP-SPT和IVTRP-ACO算法，比較SPT，LPT與改進ACO算法在批次排序?qū)訉t管區(qū)平均工件流動時間的影響.為了更加清晰直觀地說明改進ACO算法在批次排序上的性能，繪制圖7比較3種算法的性能，圖中δ為3種算法的目標函數(shù)值與IVRP-LPT目標函數(shù)的比值.從圖7可知，在平均流動時間方面，基于混合蟻群算法的爐管區(qū)調(diào)度算法IVTRP-ACO較IVTRP-SPT和IVTRP-LPT都有明顯優(yōu)勢，尤其在τ=0.75時優(yōu)勢最為明顯.當τ=0.75時，IVTRP-ACO的晶圓平均流動時間較IVTRP-SPT方法降低25.51%，較IVTRP-LPT算法降低7.41%.較規(guī)則相比，蟻群優(yōu)化算法具有更大的搜索空間，這一特點也使得在一定時間內(nèi)，蟻群算法尋找到全局最優(yōu)解或近憂解的概率更大.但較大的搜索空間也將帶來求解時間的問題，相對基于規(guī)則的啟發(fā)式算法，蟻群算法的求解時間將較長，但往往也是能接受的.綜上所述，改進ACO算法在批次排序?qū)拥男Ч^優(yōu)，利用改進ACO算法排序能很好地減低晶圓平均流動時間.

上述情況均考慮到工件的加工層數(shù)服從[25,30]之間均勻分布，層數(shù)的差異較小，為了驗證算法對層數(shù)敏感程度，現(xiàn)采取隨機產(chǎn)生少量晶圓的工件層數(shù)在[5,10]內(nèi)，其余符合[5,30]之間，并通過對表現(xiàn)較好的3類算法為IVTRP-LPT、FFLPT-LPT和算法IVTRP-ACO進行不同規(guī)模下的對比實驗.圖8所示為3種算法的目標函數(shù)值與IVTRP-ACO目標函數(shù)的平均比值δ′.可以看出，當工件的加工層數(shù)差異較大時，所提出的IVTRP-ACO算法也能很好解決，并且解的質(zhì)量也較穩(wěn)定，且相對其他兩種方法平均分別提高17.9%，35.8%.其相對提高的幅度與工件尺寸差異不大情況下大致相同，有同樣好的效果.綜上所述，不管調(diào)度問題如何變化，即使工件層數(shù)差異較大時，IVTRP-ACO算法相對于其他對比算法都有很大的提高，說明算法的穩(wěn)健性較好.

(26)

試驗過程中將CPLEX的運行時間上限設(shè)置為6 h.分析實驗結(jié)果可知，對于較小規(guī)模和負載的爐管區(qū)調(diào)度問題，CPLEX可以求出相對質(zhì)量較好的精確解， 而對于較大規(guī)模的問題卻難以在可接受的時間內(nèi)得到滿意的解.如M=4,τ=0.5時平均流動時間與IVTRP-ACO相近.M=6,τ=1時，未能在6 h的合理時間范圍內(nèi)得到合理的解.相比之下，IVTRP-ACO算法能對整個問題模型起到有效的優(yōu)化作用，相對商用軟件CPLEX平均可減低16.08%的平均流動時間.BRFFERT-AR[16]是在FFERT基礎(chǔ)上引進BR分批規(guī)則與AR批排序規(guī)則的改進啟發(fā)式算法，與表4中FFERT-LPT相比其在平均流動時間上的確有改進，但在6種規(guī)模下還是劣于本文提出的IVTRP-ACO算法.IVTRP-ACO算法較改進啟發(fā)式算法的效果有一定提高，最大程度為11.32%，平均減少流動時間10.51%.由于遺傳算法在組合優(yōu)化問題上優(yōu)于啟發(fā)式規(guī)則，且批次排序效果也得到了廣泛的驗證，本文采用了FFLPT組批，利用GA算法[18]進行批排序的方案作為元啟發(fā)式算法的對比對象.GA算法參數(shù)設(shè)置如下為種群規(guī)模與利用FFLPT組批完成后批次的數(shù)目相同，交叉概率為0.8，變異概率為0.01以及迭代次數(shù)為100次.從表4可以看出，本文所提出的算法在爐管區(qū)調(diào)度問題中稍優(yōu)于GA算法，平均求解效果提高7.10%.且可以看出IVTRP-ACO算法的求解質(zhì)量不會隨測試問題規(guī)模的變化而有大的波動，說明IVTRP-ACO算法在求解爐管區(qū)調(diào)度問題上有很好的穩(wěn)定性.在計算時間方面，所提出的IVTRP-ACO算法的平均計算時間雖然比啟發(fā)式智能算法長，但是由于爐管區(qū)加工時間大約為2～3 h，所耗費的時間能夠保持在合理的范圍內(nèi).

表4 不同測試問題下爐管區(qū)調(diào)度方法對比Tab.4 Comparison of furnace scheduling methods for different test problems

由此可知，本文所提出的基于混合蟻群算法的IVTRP-ACO算法在降低晶圓平均流動時間方面均優(yōu)于目前常用的幾種啟發(fā)式規(guī)則、改進啟發(fā)式規(guī)則、GA算法以及商用軟件CPLEX，且求解質(zhì)量具有較好的穩(wěn)定性和穩(wěn)健性，求解時間恰當，特別適合中大規(guī)模的半導(dǎo)體生產(chǎn)線爐管區(qū)β1→β2調(diào)度問題.

3.3 實例驗證

采用上海某晶圓制造廠爐管區(qū)實際生產(chǎn)情況的數(shù)據(jù)，包括Lot的投料策略、Lot進入和流出爐管區(qū)的時間、各階段的加工類型及對應(yīng)加工時間等，對基于混合蟻群算法的爐管區(qū)調(diào)度算法-IVTRP-ACO算法進行實例驗證.其中蟻群算法所涉及參數(shù)與對比試驗中一致.該企業(yè)某段時間的生產(chǎn)狀態(tài)為爐管區(qū)有7種不同制造工藝的產(chǎn)品同時在線加工，Lot的投料策略都是采用的固定時間間隔的投料策略(CONTIME)，MG1機臺組有5臺相同并行機，MG2機臺組有4臺相同并行機.設(shè)備經(jīng)過該層MG2的后續(xù)加工和下一層MG1之前加工的總時間通過統(tǒng)計得到.利用制造廠一個月內(nèi)晶圓的實際生產(chǎn)結(jié)果與算法優(yōu)化的結(jié)果進行比較，在該一個月內(nèi)總共釋放 1 440 個晶圓.流動時間得到改善的晶圓數(shù)目占總測試數(shù)目的96.39%，改進最大幅度為58%，平均流動時間減少了14.13%.在工業(yè)現(xiàn)場的實際應(yīng)用進一步證明了IVTRP-ACO的可靠性和有效性.

4 結(jié)語

針對半導(dǎo)體生產(chǎn)線爐管區(qū)多約束的β1→β2調(diào)度問題，以最小化晶圓平均流動時間為目標，建立了帶重入特性的爐管區(qū)β1→β2調(diào)度模型.結(jié)合實際生產(chǎn)中兩爐管之間的工藝等待時間約束和不兼容工藝菜單，提出了1種基于混合蟻群算法的分層調(diào)度算法，通過所提出的可變閾值控制的IVTRP規(guī)則對工件進行組批，通過改進蟻群優(yōu)化算法對批次進行整體尋優(yōu)，將所提出的IVTRP-ACO算法與基于規(guī)則的啟發(fā)式算法、改進啟發(fā)式算法、GA算法以及CPLEX等進行對比，說明了算法的有效性和可行性.將算法結(jié)果與實際生產(chǎn)數(shù)據(jù)進行比較，表明所提出算法能有效減少晶圓的平均流動時間.