基于滾動變時間窗的重組批處理機調度研究

1.上海交通大學機械與動力工程學院，上海 200240

2.安徽工程大學機械與汽車工程學院，安徽蕪湖 241000

賈文友1，2，江志斌1，李友1

基于滾動變時間窗的重組批處理機調度研究

1.上海交通大學機械與動力工程學院，上海 200240

2.安徽工程大學機械與汽車工程學院，安徽蕪湖 241000

賈文友1，2，江志斌1，李友1

1 引言

半導體芯片制造的整個過程可以分為晶圓制造、偵測、裝配與封裝、最終測試4個主要階段。其中，半導體晶圓制造因其具有多重入、多產品混線生產和設備造價昂貴等特性，被譽為最為復雜的制造系統。根據加工操作方式的不同，可以將半導體晶圓制造中的加工設備劃分為：單加工型設備、批處理型設備等[1]。所謂批處理是指在不超過批處理型設備的最大加工能力時，一次可以加工多個未完成工件。每次實際加工多個未完成工件集稱為批（Batch）。半導體晶圓制造系統中的瓶頸機一般為批處理型設備，它制約著半導體制造系統的績效，合理調度對改善半導體生產線的性能具有重要意義[2]。文獻[3-4]研究了半導體晶圓制造系統中批處理型設備優化調度算法。

關于批處理機的調度問題，Potts等進行了綜述研究[5-6]。文獻[7]研究工件不允許等待下含兩個相鄰批處理機的flow-shop調度問題。文獻[8]研究柔性作業車間的批量生產調度方法。文獻[9]研究工件存在等待時間限制下第一個設備組為批處理機，第二個設備組為離散型設備的混合flow-shop調度問題，且要求所有工件在調度開始可用。文獻[10]針對半導體晶圓生產線中批處理設備的重組批調度問題提出基于規則的拉式湊管調度算法。然而很多文獻針對重組批處理機的調度提出的動態調度算法和全局優化算法等，存在未能充分考慮平衡算法的運行時間和目標函數值等問題。

關于工件動態到達下大規模實時調度問題，分解策略是一種有效措施[11]。滾動時域策略是一種基于時間序列分解策略，是用沿調度時間滾動進行的一系列小規模或有限時段的局部調度代替大規模或無限時段的一次全局調度，是一個隨調度時刻向前推進的迭代過程。在滾動時域策略下，大規模實時調度問題沿著調度時間軸分解成許多時間窗下的子問題進行調度優化。在每個調度子問題中，為了獲得精確的優化調度解，可采用混合的整數線性規劃方法進行研究[12-13]。

本文研究對象是具有重入特性的半導體晶圓生產線中重組批處理機的調度問題，以拖延時間和最小為目標，考慮等待時間限制和工件動態到達。文獻[14]已證明以拖延時間和最小為目標調度問題是NP難題。本文首先對具有重入特性的重組批處理機的代表性問題進行描述，并定義全文術語；然后延伸基于時間序列分解策略，提出基于滾動變時間窗的三層混合調度算法，將大規模的具有重入特性的半導體晶圓生產線中的重組批處理機的調度問題分解成變時間窗對應的子問題，每個子問題通過混合三層調度算法實施優化調度；最后通過實例與分析驗證本文算法能夠在較短CPU時間內獲得滿意的目標函數值。

2 問題描述和術語定義

2.1 問題描述

為了使研究問題更具有代表性，建立如圖1所示的具有重入特性的重組批處理機的加工工藝流程簡圖，具體描述如下：

加工工藝流程簡圖主要包括兩個設備組，設備組1和設備組2，且這兩個設備組均是批處理機，設備組2的最大批處理能力大于設備組1；設備組的產品組批包括兩種類型：產品相容和不相容：設備組1具有產品不相容性組批、重入特性；設備組2具有產品相容性組批，但由設備組1提供的批不拆分，具有最大批處理能力限制，需要對進入緩沖器中產品批進行重組批、排序。基于滾動變時間窗的三層混合優化調度算法確定緩沖器工件如何進入設備組2。主要假設如下：

（1）設備組2由于加工時間長，故此工位是生產瓶頸，假設設備組2不會出現饑餓。

（2）搶占不允許，即任意設備一旦開始加工，加工過程就不允許中斷。

（3）緩沖器里產品批到達是動態的。

（4）設備組2的緩沖器里產品批存在等待時間限制，即為了避免由于工件表面接觸空氣時間過長而對產品的質量造成影響，產品批在設備組1中加工完成后必須在規定的時間內進入設備組2中加工。

（5）三層混合調度算法中第一層完成緩沖器里產品批實時狀態信息和設備組2實時狀態信息的記錄、保存和傳送；第二層完成進入緩沖器中產品重組批、排序；第三層完成重組優先批的裝載分配及其分配完畢后緩沖器里產品批實時狀態信息和設備組2的實時狀態信息更新、保存。

（6）不計工件從設備1組到緩沖器，從緩沖器到設備組2和在緩沖器重組批的過程時間。

圖1 具有重入特性的批處理加工工藝流程簡圖

2.2 術語定義

為了使術語具有通用性，對后面需要的術語進行如下定義：

J為當設備組2出現設備空閑可用時，緩沖器里來自設備組1的不同批的數量集；N為當設備組2出現設備空閑可用時，重組批的數量集；S為設備組2的最大加工能力；M為一個足夠大的正整數；t為設備組2出現設備空閑可用時當前時間；qj為批j在設備組1和設備組2之間等待限制時間；P為設備組2的加工時間；sj為批j包含的工件數量；rj為批j到達緩沖器的時間；dj為批j的交貨時間；ZSj為批j總加工工序數量集；DSj為批j在設備組2上所屬的加工工序數；Pk，j為批j在第k個加工工序中加工時間；PRj為批j在設備組2后純剩余的加工時間；drn為重組批n的交貨時間；Crn為重組批n的完工時間；PRrn為重組批n在設備組2后純剩余加工時間；∑T總拖延時間和。注：j=1，2，…，J；n=1，2，…，N；k=1，2，…，ZSj。

3 重組批處理機優化調度算法

為了優化半導體晶圓制造系統中重組批處理機的調度，基于滾動變時間窗的三層混合調度算法被提出，首先研究算法總體框架的構建，然后研究用于重組批及排序的松弛混合整數線性規劃模型建模。

3.1 算法總體框架構建

以拖延時間和最小為目標，且具有等待時間限制和工件動態到達的重組批處理機的NP難調度問題，在分解規則下，將總的調度時間窗分解為許多時間窗，每個時間窗的長度等于相鄰兩個觸發事件之間的時間間隔，其值是變化的，即變時間窗；在滾動時域策略下，每個時間窗之間不斷更新優化調度結果。在每個變步長的時間窗下的子問題通過三層混合調度算法實行優化調度：產生觸發并傳遞調度參數信息；重組批及其排序；裝載重組優先批且更新調度參數實時信息。第一、三層延伸半導體晶圓制造系統實時調度仿真平臺實施[15]，如圖2所示；第二層在CPLEX和開發程序聯合平臺求解，在“基于松弛的混合整數線性規劃模型構建”部分研究。基于滾動變時間窗的三層混合調度算法總體框架流程圖如圖3所示，具體包括如下步驟。

步驟1在滾動時域策略下，實時調度仿真平臺產生調度參數信息傳遞觸發事件：一臺重組批處理設備空閑可用，第一層被開始執行，初始化時間窗。

步驟2實時調度仿真平臺傳遞緩沖器里的不同產品族的工件數量、到達時間等實時信息的數據庫，作為第二層執行的源數據，該空閑可用重組批處理設備為“等待”狀態。

步驟3計算重組批的數量集(N)，判斷：如果N＞1，程序往下執行，否則跳過第二層，直接轉到步驟7。

步驟4接受第一層任務輸出的源數據，第二層開始被執行，即執行通過CPLEX和開發程序聯合平臺運行基于松弛的混合整數線性規劃模型的重組批及其排序優化求解過程。

步驟5輸出在總拖延時間和最小的目標函數下優化的重組批的一維排序數組，作為第三層的源數據傳遞給實時調度仿真平臺。

圖2 半導體晶圓制造系統實時調度仿真平臺主要界面

圖3 算法流程圖

步驟6接受第二層反饋的源數據，第三層開始被執行。

步驟7實時調度仿真平臺將重組優先批裝載到處于“等待”狀態空閑可用重組批處理設備，更新并保存設備組2前的緩沖器里的實時信息，更新并保存設備組2狀態信息。

步驟8程序終止判斷：如果沒有完成全部調度計劃，繼續往下執行，否則終止基于滾動變時間窗的三層混合調度算法。

步驟9實時調度仿真平臺實時記錄并保存重組批處理設備組（即設備組2）前的緩沖器里的不同產品族的工件數量、到達時間等實時狀態信息；實時記錄并保存重組批處理設備組實時狀態信息，等待下一個調度參數信息傳遞觸發事件產生。

3.2 基于松弛的混合整數線性規劃模型構建

每個時間窗內的子問題，由于規模被減小，精確算法可以適用。在整數規劃模型求解重組批及其排序優化調度問題中，重組批狀態的0-1變量和重組批的排序位置序號是決策變量；滿足設備加工時間，同一設備不能同時加工兩個重組批，同一重組批只能占有一個排序位置序號等是約束條件；總拖延時間和最小為目標函數，具體整數規劃模型如下。

目標函數：等式（1）是每個時間窗內的總拖延時間和最小的目標函數。約束條件式（2）用于計算重組批n的完工時間。約束條件式（3）和（4）用于確保每個重組批只占有一個排序位置號，且每個排序位置號只有一個重組批。約束條件式（5）引入重組批狀態的0-1變量。約束條件式（6）確保緩沖器中每個批都被進行重組批，且只被進行1次重組批。約束條件式（7）用于計算批j在設備組2后純剩余的加工時間，其中μk是調整系數。約束條件式（8）用于確定調整系數。約束條件式（9）用于計算當設備組2出現設備空閑可用時，重組批的數量集N。約束條件式（10）用于確保任一重組批包含工件數量小于至多等于設備組2的最大加工能力S。約束條件式（11）用于計算重組批n在設備組2后純剩余的加工時間，其值等于重組批中所包含產品族中在設備組2后純剩余的加工時間的最小值。約束條件式（12）用于計算重組批n的交貨時間，其等于重組批中所包含產品族中交貨期的最小值。約束條件式（13）用于確保被調度批j在緩沖器里的等待時間不超過設備組1和設備組2之間等待限制時間qj。

在CPLEX和開發程序聯合平臺中，線性的約束適合CPLEX求解。約束條件式（11）～（13）中表達關系式是非線性的，需要進行線性化。

綜上，等式（1）、約束條件式（2）～（10）和（14）～（16）構建基于松弛的混合整數線性規劃模型，適合CPLEX和開發程序聯合平臺優化求解。

4 實例與分析

為了評價基于滾動變時間窗的三層混合調度算法的有效性，一個簡化的小型半導體晶圓制造系統被構建和調試運行。如圖4所示，設有8個不同的設備組域，其中DIK對應于圖1中的設備組1，LPC對應于設備組2，DIK和LPC之間具有等待時間限制和工件動態到達的特性。

圖4 具有重入特性的半導體晶圓制造小型批處理機系統

圖5 小型批處理系統的展開圖及其對應的加工時間

表1 某時間窗下緩沖器里半導體晶圓的主要實時調度參數

圖5是圖4的工序展開圖，表示8個不同的設備組域含有12個加工工序。不同設備組域的上標表示重入的次數，例如DIK2表示第二次在DIK進行加工。設有4種不同類型的半導體晶圓產品被同時加工，即I=4；不同類型的半導體晶圓產品在DIK和LPC之間等待時間限制相同，且qj=11 360；4種不同類型的半導體晶圓產品有相同的加工路線，即ZSj=12；由于LPC是最后一道工序，所以DSj=12和PRj=0。

如圖5所示，每道加工工序的上面標注給定的加工時間，4種不同半導體晶圓產品第二次在DIK加工時間不相同，即PTi，DIK2(i=1，2，3，4)的值分別是180，263，410，300。假設設備組2的最大加工能力是12，即S=12。

實時調度仿真平臺、CPLEX和開發程序聯合平臺都在借用Visual Basic.NET 2008編程，CPLEX為12.2版，運行硬件配置為Intel Core 2 Duo 2.0 GHz具有2 GB DDR-2 RAM。

每當在LPC中有1臺空閑可用設備時，第一層中實時調度仿真平臺輸出LPC緩沖器里的工件數量、到達時間等實時信息的數據庫。表1是實時調度仿真平臺輸出的主要實時調度參數，定義為案例1，其中緩沖器里來自設備組1的不同批的數量集是8，即J=8。

在第二層中，根據表1數據，CPLEX和開發程序聯合平臺基于松弛的混合整數線性規劃模型進行重組批及其排序，主要的執行結果是：CPU運行時間是0.02 s，目標函數值是53，重組批的數量集N=4，重組批的優化排序后位置序號的一維數組(Position(1)，Position(2)，Position(3)，Position(4))=(4，3，2，1)，重組批的0-1變量xjn如表2所示，可知實時調度仿真平臺重組優先批是第4個位置重組批，包括原來第3個批和第6個批。

在第三層中，實時調度仿真平臺裝載重組優先批，然后更新并保存重組批處理設備組前的緩沖器里的不同半導體晶圓的工件數量、到達時間等實時信息，更新并保存重組批處理設備組實時狀態信息，案例1的當前時間窗終止，并判斷總調度是否終止。

表2 重組批的0-1變量xjn的值

為了進一步評價基于滾動變時間窗的三層混合調度算法有效性，使用常用的智能算法即遺傳算法作為參考算法對比。遺傳算法模型的主要參數中設置種群數量：80；交叉概率：0.8；變異概率：0.1和遺傳代數：120。

在滾動變時間窗的三層混合調度算法和遺傳算法對比時，設計兩個代表案例對比4個考核指標。

4個重要指標是：CPU運行時間，CPU運行時間改進率，目標函數值和目標函數值偏差率。

驗證3個代表案例：案例1、案例2和案例3。其中案例1，在前面已經詳細敘述。關于案例2，緩沖器里來自設備組1的不同批的數量集是16即J=16。通過第一層中實時調度仿真平臺，LPC設備組的緩沖器里的不同半導體晶圓的工件數量、到達時間等實時信息主要包括：sj=[3，3，4，4，5，5，6，6，6，6，7，7，8，8，9，9]，rj= [100，100，150，150，200，200，300，300，180，263，180，263,410,410,300,300]和dj=[3 611，3 611，3 611，3 611，3 627,3 627,3 627,3 627,3 636,3 636,3 636,3 636,3 245，3 245，3 245，3 245]。關于案例3，令J=18。

滾動變時間窗的三層混合調度算法和遺傳算法的實驗結果對比分析如表3所示。在案例1～3中，滾動變時間窗的三層混合調度算法的目標函數值優于遺傳算法的目標函數值的偏差率分別為+3.64%、+4.19%和+4.30%，同時CPU運行時間改進率分別為+99.81%、+53.71%和-9.66%。可見，滾動變時間窗的三層混合調度算法在兩個案例中執行效果較好，在目標函數較優的情況下能保持CPU運行時間較短，但是隨著調度規模增加，優勢變弱。

表3 基于松弛的混合整數線性規劃模型方法和遺傳算法重要指標對比表

5 結束語

本文以拖延時間和最小為目標，對具有等待時間限制和工件動態到達的重組批處理調度NP難題進行研究，提出了基于滾動變時間窗的三層混合調度算法，實驗結果表明本文所設計的調度算法能保持滿意的目標函數值和較短的CPU運行時間。基于滾動變時間窗的三層混合調度算法優越性體現在該算法是一種混合整數線性規劃求解（CPLEX求解）和啟發式算法（即實時調度仿真平臺運行）混合調度（Math-heuristic）算法。為了進一步提高該算法的魯棒性，需要根據半導體晶圓制造廠的實際情況進一步實驗和改進調度算法。

[1]江志斌.半導體芯片制造系統建模與優化調度控制[M].上海：上海交通大學出版社，2011.

[2]M?nch L，Fowler J W，Dauzère-pérès S，et al.A survey of problems，solution techniques，and future challenges in scheduling semiconductor manufacturing operations[J].Journal of Scheduling，2011，14（6）：583-599.

[3]Jia Wenyou，Jiang Zhibin，Li You.Closed loop controlbased real-time dispatching heuristic on parallel batch machines with incompatible job families and dynamic arrivals[J].International Journal of Production Research，2013，51（15）：4570-4584.

[4]Jia Wenyou，Jiang Zhibin，Li You.A job-family-oriented algorithm for re-entrant batch processing machine scheduling[C]//2013 IEEE International Conference on Automation Science and Engineering（CASE），2013：1022-1027.

[5]Potts C N，Kovalyov M Y.Scheduling with batching：a review[J].European Journal of Operational Research，2000，120（2）：228-249.

[6]Mathirajan M，Sivakumar A.A literature review，classification and simple meta-analysis on scheduling of batch processors in semiconductor[J].The International Journal of Advanced Manufacturing Technology，2006，29（9）：990-1001.

[7]Lin B M T，Cheng T.Batch scheduling in the no-wait two-machine flowshop to minimize the makespan[J].Computers&Operations Research，2001，28（7）：613-624.

[8]曾強，沈玲，潘啟東，等.批量生產柔性作業車間多目標精細化調度方法[J].計算機工程與應用，2014，50（2）：263-270.

[9]Su L H.A hybrid two-stage flowshop with limited waiting time constraints[J].Computers&Industrial Engineering，2003，44（3）：409-424.

[10]李程，江志斌，李友，等.基于規則的批處理設備調度方法在半導體晶圓制造系統中應用[J].上海交通大學學報，2013，47（2）：230-235.

[11]孫凱，邢立寧，陳英武.基于分解優化策略的多敏捷衛星聯合對地觀測調度[J].計算機集成制造系統，2013，19（1）：127-136.

[12]Klemmt A，Weigert G，Werner S.Optimisation approaches for batch scheduling in semiconductor manufacturing[J]. European Journal of Industrial Engineering，2011，5（3）：338-359.

[13]Xiao J，Zheng L.A MILP-based batch scheduling for twostage hybrid flowshop with sequence-dependent setups in semiconductor assembly and test manufacturing[C]// 2010IEEEConferenceon AutomationScienceand Engineering（CASE），2010：87-92.

[14]Du J，Leung J Y T.Minimizing total tardiness on one machine is NP-hard[J].Mathematics of Operations Research，1990，15（3）：483-495.

[15]Li Y，Jiang Z B，Jia W Y.A pull VPLs based release policy and dispatching rule for semiconductor wafer fabrication[C]//2012 IEEE International Conference on Automation Science and Engineering（CASE），2012：396-400.

[16]Montagne E.Sequencing with time delay costs[J].Industrial Engineering Research Bulletin，1969，5：20-31.

JIA Wenyou1，2,JIANG Zhibin1,LI You1

1.School of Mechanical Engineering,Shanghai Jiaotong University,Shanghai 200240,China
2.School of Mechanical and Automotive Engineering,Anhui Polytechnic University,Wuhu,Anhui 241000,China

To address the scheduling problem of reforming batch processing machine for minimizing total tardiness with limited waiting time constraints and dynamic arrivals,a rolling variable time windows-based three-phase combined algorithm is proposed.With decomposition rule and rolling horizon control strategy,the scheduling horizon is decomposed into many variable time windows.Each sub-problem corresponds to a time window.At each sub-problem,the scheduling algorithm includes three phases：to send information of scheduling parameters;to reform and sequence batches;and to load super-hot reforming batch and update the state of manufacturing system.The experiments are implemented on realtime scheduling simulation platform and CPLEX.The results show that the proposed algorithm can obtain better solutions in less computation time.

reforming batch processing machine;rolling variable time window;three-phase combined algorithm

針對具有等待時間限制和工件動態到達的重組批處理機調度問題，以拖延時間和最小為目標，提出基于滾動變時間窗的三層混合調度算法。該調度算法是應用滾動時域策略，將重組批處理機調度問題分解為許多變時間窗的子問題；每個子問題調度分三層執行：即產生觸發并傳遞參數、重組批及排序、派工并更新參數。通過實時調度仿真平臺和CPLEX平臺進行實例驗證，結果表明基于滾動變時間窗的三層混合調度算法能夠在較短計算時間內獲得滿意優化解。

重組批處理機；滾動變時間窗；三層混合調度算法

A

TP391.9

10.3778/j.issn.1002-8331.1311-0411

JIA Wenyou,JIANG Zhibin,LI You.Rolling variable time windows for reforming batch processing scheduling problem.Computer Engineering and Applications,2014,50（18）：19-24.

國家科技02重大專項（No.2011ZX02501—005）。

賈文友（1973—），男，博士研究生，講師，主要研究領域為復雜制造系統建模、調度等；江志斌（1958—），男，博士，教授，長江學者，主要研究領域為生產調度與控制、生產與服務系統、動態系統理論及在制造系統中的應用、醫療衛生系統工程；李友（1987—），男，博士研究生，主要研究領域為半導體晶圓制造系統建模、調度和仿真。E-mail：jiawy@sjtu.edu.cn

2013-11-28

2014-03-26

1002-8331（2014）18-0019-06

CNKI網絡優先出版：2014-04-09，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1311-0411.html