基于滾動(dòng)變時(shí)間窗的重組批處理機(jī)調(diào)度研究

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

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

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

基于滾動(dòng)變時(shí)間窗的重組批處理機(jī)調(diào)度研究

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

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

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

1 引言

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

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

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

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

2 問(wèn)題描述和術(shù)語(yǔ)定義

2.1 問(wèn)題描述

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

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

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

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

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

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

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

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

圖1 具有重入特性的批處理加工工藝流程簡(jiǎn)圖

2.2 術(shù)語(yǔ)定義

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

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

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

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

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

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

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

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

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

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

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

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

圖3 算法流程圖

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

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

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

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

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

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

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

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

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

4 實(shí)例與分析

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

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

圖5 小型批處理系統(tǒng)的展開(kāi)圖及其對(duì)應(yīng)的加工時(shí)間

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

本文以拖延時(shí)間和最小為目標(biāo)，對(duì)具有等待時(shí)間限制和工件動(dòng)態(tài)到達(dá)的重組批處理調(diào)度NP難題進(jìn)行研究，提出了基于滾動(dòng)變時(shí)間窗的三層混合調(diào)度算法，實(shí)驗(yàn)結(jié)果表明本文所設(shè)計(jì)的調(diào)度算法能保持滿意的目標(biāo)函數(shù)值和較短的CPU運(yùn)行時(shí)間?；跐L動(dòng)變時(shí)間窗的三層混合調(diào)度算法優(yōu)越性體現(xiàn)在該算法是一種混合整數(shù)線性規(guī)劃求解（CPLEX求解）和啟發(fā)式算法（即實(shí)時(shí)調(diào)度仿真平臺(tái)運(yùn)行）混合調(diào)度（Math-heuristic）算法。為了進(jìn)一步提高該算法的魯棒性，需要根據(jù)半導(dǎo)體晶圓制造廠的實(shí)際情況進(jìn)一步實(shí)驗(yàn)和改進(jìn)調(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]曾強(qiáng)，沈玲，潘啟東，等.批量生產(chǎn)柔性作業(yè)車間多目標(biāo)精細(xì)化調(diào)度方法[J].計(jì)算機(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é)報(bào)，2013，47（2）：230-235.

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

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

重組批處理機(jī)；滾動(dòng)變時(shí)間窗；三層混合調(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.

國(guó)家科技02重大專項(xiàng)（No.2011ZX02501—005）。

賈文友（1973—），男，博士研究生，講師，主要研究領(lǐng)域?yàn)閺?fù)雜制造系統(tǒng)建模、調(diào)度等；江志斌（1958—），男，博士，教授，長(zhǎng)江學(xué)者，主要研究領(lǐng)域?yàn)樯a(chǎn)調(diào)度與控制、生產(chǎn)與服務(wù)系統(tǒng)、動(dòng)態(tài)系統(tǒng)理論及在制造系統(tǒng)中的應(yīng)用、醫(yī)療衛(wèi)生系統(tǒng)工程；李友（1987—），男，博士研究生，主要研究領(lǐng)域?yàn)榘雽?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