基于混合蟻群算法的半導體生產線爐管區調度方法

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

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

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

爐管區包含數十臺不同類型的設備，在實際生產過程中，晶圓動態地重復訪問爐管區，以完成不同晶圓層的加工.在生產調度領域，爐管區調度通常被歸納為一類帶重入特性的并行批處理機調度問題.

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

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

1 問題建模

1.1 問題描述

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

綜上所述，本文研究的問題為考慮多產品復雜重入流、不兼容工藝菜單、不同準備時間、等待時間約束和工件動態到達的爐管區β1→β2調度問題，以最小化工件平均流動時間為目標設計優化算法.

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

1.2 爐管區β1→β2調度問題數學模型

爐管區β1→β2調度問題模型為

(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為工件總數，工件索引i=1,2,…,n；Fi為工件i的流動時間；M為機臺總數，機臺索引m∈M=[1,N1+N2]，N1、N2分別為β1、β2內爐管數量；Mk為工序k的并行機數量；mk為工序k可加工機臺的編號，

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

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

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

2 基于混合蟻群算法的分層調度

2.1 基于混合蟻群算法的分層調度方法架構

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

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

2.2 可變閾值組批算法

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

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

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

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

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

(18)

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

2.3 設備選擇規則

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

2.4 改進蟻群優化算法

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

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

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

其中：ε為一固定值.

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

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

(19)

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

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

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

(20)

(21)

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

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

(22)

ηij=Bf2/B2+1/tf2

(23)

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

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

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

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

(24)

D轉移概率計算公式為

(25)

步驟3判斷候選表是否為空，若是，則結束，得到批的序列，若不是，則轉步驟2.

(5) 改進ACO算法描述.

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

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

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

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

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

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

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

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

3 實驗與分析

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

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

表1 調度問題描述數據Tab.1 Description data of scheduling problem

3.1 算法參數設計

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

通過統計平均值，得到田口實驗的響應圖，如圖4所示.

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

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

3.2 算法性能對比分析

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

3.2.1與無IVTRP的算法對比 為了驗證本文針對組批層提出的IVTRP規則與批次排序層提出的改進蟻群算法的有效性，將本文提出的含IVTRP組批規則的IVTRP-LPT算法、IVTRP-ACO算法與目前解決并行批處理設備較優的4個算法[16]進行對比，分析本文提出的算法在爐管區并行批處理機調度中減小晶圓平均流動時間的有效性與性能.4個對比算法分別采用表3中的1、4、5、6.

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

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

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

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

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

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

(26)

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

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

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

3.3 實例驗證

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

4 結語

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