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

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

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

基于滾動變時間窗的重組批處理機調(diào)度研究

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

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

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

1 引言

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

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

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

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

2 問題描述和術(shù)語定義

2.1 問題描述

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

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

（1）設(shè)備組2由于加工時間長，故此工位是生產(chǎn)瓶頸，假設(shè)設(shè)備組2不會出現(xiàn)饑餓。

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

（3）緩沖器里產(chǎn)品批到達是動態(tài)的。

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

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

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

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

2.2 術(shù)語定義

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

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

3 重組批處理機優(yōu)化調(diào)度算法

為了優(yōu)化半導(dǎo)體晶圓制造系統(tǒng)中重組批處理機的調(diào)度，基于滾動變時間窗的三層混合調(diào)度算法被提出，首先研究算法總體框架的構(gòu)建，然后研究用于重組批及排序的松弛混合整數(shù)線性規(guī)劃模型建模。

3.1 算法總體框架構(gòu)建

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

步驟1在滾動時域策略下，實時調(diào)度仿真平臺產(chǎn)生調(diào)度參數(shù)信息傳遞觸發(fā)事件：一臺重組批處理設(shè)備空閑可用，第一層被開始執(zhí)行，初始化時間窗。

步驟2實時調(diào)度仿真平臺傳遞緩沖器里的不同產(chǎn)品族的工件數(shù)量、到達時間等實時信息的數(shù)據(jù)庫，作為第二層執(zhí)行的源數(shù)據(jù)，該空閑可用重組批處理設(shè)備為“等待”狀態(tài)。

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

步驟4接受第一層任務(wù)輸出的源數(shù)據(jù)，第二層開始被執(zhí)行，即執(zhí)行通過CPLEX和開發(fā)程序聯(lián)合平臺運行基于松弛的混合整數(shù)線性規(guī)劃模型的重組批及其排序優(yōu)化求解過程。

步驟5輸出在總拖延時間和最小的目標(biāo)函數(shù)下優(yōu)化的重組批的一維排序數(shù)組，作為第三層的源數(shù)據(jù)傳遞給實時調(diào)度仿真平臺。

圖2 半導(dǎo)體晶圓制造系統(tǒng)實時調(diào)度仿真平臺主要界面

圖3 算法流程圖

步驟6接受第二層反饋的源數(shù)據(jù)，第三層開始被執(zhí)行。

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

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

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

3.2 基于松弛的混合整數(shù)線性規(guī)劃模型構(gòu)建

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

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

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

綜上，等式（1）、約束條件式（2）～（10）和（14）～（16）構(gòu)建基于松弛的混合整數(shù)線性規(guī)劃模型，適合CPLEX和開發(fā)程序聯(lián)合平臺優(yōu)化求解。

4 實例與分析

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

圖4 具有重入特性的半導(dǎo)體晶圓制造小型批處理機系統(tǒng)

圖5 小型批處理系統(tǒng)的展開圖及其對應(yīng)的加工時間

表1 某時間窗下緩沖器里半導(dǎo)體晶圓的主要實時調(diào)度參數(shù)

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

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

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

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

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

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

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

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

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

4個重要指標(biāo)是：CPU運行時間，CPU運行時間改進率，目標(biāo)函數(shù)值和目標(biāo)函數(shù)值偏差率。

驗證3個代表案例：案例1、案例2和案例3。其中案例1，在前面已經(jīng)詳細(xì)敘述。關(guān)于案例2，緩沖器里來自設(shè)備組1的不同批的數(shù)量集是16即J=16。通過第一層中實時調(diào)度仿真平臺，LPC設(shè)備組的緩沖器里的不同半導(dǎo)體晶圓的工件數(shù)量、到達時間等實時信息主要包括：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]。關(guān)于案例3，令J=18。

滾動變時間窗的三層混合調(diào)度算法和遺傳算法的實驗結(jié)果對比分析如表3所示。在案例1～3中，滾動變時間窗的三層混合調(diào)度算法的目標(biāo)函數(shù)值優(yōu)于遺傳算法的目標(biāo)函數(shù)值的偏差率分別為+3.64%、+4.19%和+4.30%，同時CPU運行時間改進率分別為+99.81%、+53.71%和-9.66%?？梢?，滾動變時間窗的三層混合調(diào)度算法在兩個案例中執(zhí)行效果較好，在目標(biāo)函數(shù)較優(yōu)的情況下能保持CPU運行時間較短，但是隨著調(diào)度規(guī)模增加，優(yōu)勢變?nèi)酢?/p>

表3 基于松弛的混合整數(shù)線性規(guī)劃模型方法和遺傳算法重要指標(biāo)對比表

5 結(jié)束語

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

[1]江志斌.半導(dǎo)體芯片制造系統(tǒng)建模與優(yōu)化調(diào)度控制[M].上海：上海交通大學(xué)出版社，2011.

[2]M?nch L，F(xiàn)owler 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]曾強，沈玲，潘啟東，等.批量生產(chǎn)柔性作業(yè)車間多目標(biāo)精細(xì)化調(diào)度方法[J].計算機工程與應(yīng)用，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]李程，江志斌，李友，等.基于規(guī)則的批處理設(shè)備調(diào)度方法在半導(dǎo)體晶圓制造系統(tǒng)中應(yīng)用[J].上海交通大學(xué)學(xué)報，2013，47（2）：230-235.

[11]孫凱，邢立寧，陳英武.基于分解優(yōu)化策略的多敏捷衛(wèi)星聯(lián)合對地觀測調(diào)度[J].計算機集成制造系統(tǒng)，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

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

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

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—），男，博士研究生，講師，主要研究領(lǐng)域為復(fù)雜制造系統(tǒng)建模、調(diào)度等；江志斌（1958—），男，博士，教授，長江學(xué)者，主要研究領(lǐng)域為生產(chǎn)調(diào)度與控制、生產(chǎn)與服務(wù)系統(tǒng)、動態(tài)系統(tǒng)理論及在制造系統(tǒng)中的應(yīng)用、醫(yī)療衛(wèi)生系統(tǒng)工程；李友（1987—），男，博士研究生，主要研究領(lǐng)域為半導(dǎo)體晶圓制造系統(tǒng)建模、調(diào)度和仿真。E-mail：jiawy@sjtu.edu.cn

2013-11-28

2014-03-26

1002-8331（2014）18-0019-06

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-04-09，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1311-0411.html