滾動時域下最小加工時間批調度與粒子群求解

王宗光，謝小青，楊玉龍，廖世龍*

(1.蘭州理工大學經濟管理學院，甘肅 蘭州 730050； 2.山東大學管理學院，山東 濟南 250100)

1 引言

批調度問題主要指工件排序及工件合批，是半導體生產過程中提煉出的新型調度問題[1]。合批根據批處理設備的容量、工件形狀材質、工件到達時間以及加工成本等多種因素綜合處理。因此，批調度在求解難度上遠高于古典調度[2]。實踐生產中，批調度以適當的時間周期或事件驅動進行循環調度，僅需考慮怎樣對某一時段內的工件分批、排程[3]，將動態、長期的全局調度問題分解為各時段內靜態的局部子調度問題。傳統批調度在各調度周期內只使用一種方法和一種確定的規則來解決問題，以便于調度的實現。而滾動時域調度方法則是時間驅動的循環調度策略。

當前批調度的研究可分為兩種：一是理論。Liu的研究表明即便單臺機器的工件集只有兩個到達時間，批調度問題也是NP難題[4]。Zhao證明了目標為拖期懲罰的連續型批調度問題為強NP難[5]。二是算法，研究主要集中于初始時刻全局信息完全時，利用常規算法或群智能優化算法等離線算法進行一次的全局靜態調度，獲得調度最優值[6-8]。Melouks和Damodaran分別采用模擬退火算法、遺傳算法對制造跨度進行優化研究[9，10]。Tang和Song設計了離散粒子群算法并將其應用在鋼輥熱處理混合流水車間[11]。閆萍和袁媛以化工領域設備批處理過程為研究對象，構建了分批與批調度決策的優化模型并提出改進的DE算法，仿真得出與PSO算法相比，改進的DE算法性能更好[12]。

實際生產加工中，工件動態到達處理設備，對工件信息了解有限。Ovacik和Marcos較早的將滾動調度方法應用到經典調度問題中并取得了較好的效果[13，14]。但是，滾動時域調度策略下，各調度周期內只進行局部調度且很難考慮全局信息，因此，無法對全局調度性能指標作估計和控制[15]。Nelson和Sourirajan將滾動調度策略和實時狀態信息結合起來，首先把動態調度過程細分為多個連續靜態調度，再在每個區間內逐個優化，最后達到局部最優[16，17]，進一步適應動態生產環境的不斷變化，該研究表明滾動調度策略在解決調度問題上極具適用性[18]。

針對工件動態到達且調度開始時刻工件信息不完全的批調度問題，在時域內利用粒子群算法進行調度優化尋求局部調度最優，并加入懲罰函數，確保局部調度目標與全局目標一致。對滾動時域策略下各調度規則下的調度結果進行了仿真，并對此類動態調度問題中不同參數取值下的仿真結果進行了討論。

2 滾動時域策略下批調度數學建模

2.1 滾動時域批調度問題描述

圖1 時域l中工件調度流程圖

2.2 符號說明

參數符號：

T：調度時域周期長度；

B：批處理設備的容量；

j：工件集合，其中j={1，2，…，n}；

rtj：工件j的到達時間；

ptj：工件j的加工時間；

sj：工件j的尺寸；

weightj：工件j的權重參數；

決策變量符號：

l：調度時域個數集，其中l∈{1，2，…，L}，L為調度時域個數的最大值；

ctj：工件j的完工時間；

bhl：時域l內待加工工件集；

bkl：調度時域l下的第k(k=1，2，…，Kl)批工件集；

RTkl：批bkl的到達時間；

STkl：批bkl的開始時間；

PTkl：批bkl的加工時間；

CTkl：批bkl的完工時間；

CTl：時域l中最后一批工件的完工時間；

Sl：時域l內得到加工的工件集；

S′l：時域l內未得到加工的工件集。

2.3 模型假設

1) 工件集合j={1，2，…，n}，每個工件包含如下信息：rtj、ptj、sj和weightj；

2) 批設備容量為B，是各時域中各批次的工件尺寸之和的最大值。批加工一旦開始，不能中斷，也不能放入新工件；

3) 以批次進行加工，批bkl的到達時間RTkl為批中所有工件的最大到達時間、加工時間PTkl為批中工件最大加工時間、開始加工時間計算方法：

當k=1時

ST1l=max{RT1l，CTl-1，(l-1)T}

(1)

當k=2，3，…，Kl時

STkl=max{RTkl，CT(k-1)l}

(2)

從而，批bkl的完工時間CTkl為

CTkl=STkl+PTkl

(3)

4) 調度時域l的周期為T。上一時域的結束時間即為下一時域的開始時間，某一時域的結束時間為該時域內最后一個批次的完工時間。

2.4 滾動時域批調度數學模型

(4)

st.Yjkl={0，1}

(5)

(6)

(7)

Sl={j|j∈bhl，stj

(8)

S′l={j|j∈bhl，stj≥l*T}

(9)

(10)

(11)

其中j={1，2，…，n}，k={1，2，…，Kl}，l={1，2，…，L}。式(4)是目標函數，表示最小加權完工時間和；式(5)中，Yjkl為{0，1}決策變量，當工件j屬于時域l中第k批時，Yjkl=1，否則，Yjkl=0；式(6)用以確保所有工件都能得到分批且工件不會重復加工；式(7)是工件分批的主要約束條件，表示同一批次內所有工件的尺寸和應當不超過批設備容量；式(8)表示時域l中已加工的工件集；式(9)表示時域l中還沒有加工的工件集；式(10)表示時域l中加工工件數；式(11)表示時域l內工件分批數量。

3 滾動時域批調度PSO算法實現

3.1 模型的初始化

第一個時域中待加工工件集為到達時間在周期內的所有工件集合，后續時域中待加工工件集的確定方法參照圖1。假設時域l中，待加工工件數為n(l)，PSO算法的粒子數為N，各粒子用n(l)維向量表示。粒子i的位置向量Xi=(xi1，xi2，…，xin(l))，各Xi都表示一個工件序列。xij(j∈{1，2，…，n(l)})是粒子i中工件j的優先值(xij越小，越靠前加工)，隨速度向量Vi=(vi1，vi2，…，vin(l))中vij的變化而變化。

3.2 PSO算法中工件排序、分批

時域l中，以先到先加工的規則進行工件初始調度，bhl按rtj從小到大依次排序。若rtj相同，ptj越小，工件排序越靠前。得到時域l內工件調度的初始排序πl，πl(i)表示πl的第i個工件。令第1個工件優先值為πl(1)=rand(0，1)，其它工件優先值為[19]

πl(i+1)=πl(i)+rand(0，1)

(12)

將待加工工件先在批設備容量B的約束條件下分批，再計算當前時域中微粒的適應值。其中，活批是工件合批過程中，若至少存在一個批bk，在將工件j放入批bk后，仍然容量約束條件，則稱批bk為j的活批。否則，批bk為確定批。

為保證調度目標，決策人員不會為了盡可能填滿批設備而無限制的等待滿足容量約束的工件到達。對于活批bk，在批等待時間內到達的所有工件都可以合入成為同一批。分批規則：對于工件j有兩種安排方式，一是若當前不存在批，或不存在對于j的活批，則j生成新的批，此時新的批為活批；二是若存在對于j的活批bk，當j的到達時間與活批bk的到達時間間隔大于批等待時間，j進入新批，此時活批bk為確定批；否則，bk仍為活批。

4 局部懲罰函數與算法流程

4.1 局部調度懲罰函數

滾動時域調度下，①各調度時域結束時，部分工件已完成加工，后續時域中全局調度的自由度減??；②各調度時域下只加工部分工件，全局信息少。因此，時域l中目標懲罰函數Δfl表示為

(13)

(14)

4.2 批調度算法流程

Step1：給出初始時刻信息不完全的n個工件集合S；

Step2：根據工件到達時間確定第一個時域l內待加工工件集合bhl，該時域內工件信息已知；

Step5：返回局部最優調度適應值fl，可得工件排序和分批，進而求得時域l內的最優目標值Fl以及時域l內得到處理的工件集Sl和未得到處理的工件集S′l；

Step6：令Tabu={j|j∈S-Sl}，若Tabu不為空集，將時域l內未熱處理的工件集合S′l滾動進入l+1時域，與step2中的bhl+1合并，即bhl+1=S′l∪bhl+1，進入step3；若為空集，結束。

5 仿真研究

5.1 仿真參數設計與算法有效性分析

5.1.1 仿真參數設計

本文采用Melouks等提出的隨機產生數據的方法獲得算例[20]，算例劃分標準如下：

1)工件個數n分為J1、J2、J3、J4、J5類問題，工件數分別為20、40、60、80、100；

2)工件加工時間ptj服從[1，20]離散均勻分布；

3)工件尺寸sj服從[1，10]上的離散均勻分布；

4)工件到達時間rtj服從[0，rnE[ptj]]的離散均勻分布，其中r={0.1，0.2，0.3，0.4，0.5}，對應于r1、r2、r3、r4、r5類問題，其工件到達時間間隔分別為1、2、3、4、5；

在批處理設備的容量B=30，PSO算法中粒子個數m=80，迭代次數NC_max=80的參數下，所有算例運行100次，利用Matlab2011b實現。由于算例中數據均為隨機產生，為防止個別極值的出現對運行結果產生影響，最終結果以除去10個最小值和10個最大之后的其余數值的平均值表示。文中不討論工件尺寸sj、加工時間ptj，得到不同到達時間下調度時域周期長度T分別為50、100、150時不同工件數的加權完成時間和。

對五種常規調度介紹如下，后續對五種常規調度的調度結果與PSO算法下批調度模型優化后的調度結果進行比較。

1)先到先加工(FIFO)規則，調度時域內工件按到達時間rt非降生成排序，常用于調度車間的一般調度問題中；

2)基于優先權優先(PSF)規則，調度時域內工件按其權重weight非增生成排序，常用于工件含權重參數的批調度問題，但此調度規則容易造成熱處理爐等批處理設備的空閑時間；

3)加權最小到達時間優先(WLAT)規則，調度時域內工件按其重要度與到達時間的比值weight/rt非增生成排序，是FIFO規則和PSF規則的折中，不會導致熱處理爐產生大量的空閑等待時間；

4)加權最短加工時間優先(WSPT)規則，調度時域內工件按重要度與加工時間的比值weight/pt非增生成排序，在解決目標為加權完工時間和靜態全局調度的問題中效果最佳；

5)最短加工時間優先(SPT)規則，能在解決大規模工件的靜態調度問題中實現出很好的優化性能。

5.1.2 基于PSO算法的滾動時域批調度模型的有效性與適用性分析

圖2中為r=0.1時的調度結果。首先，在不同工件數和調度周期下，基于PSO算法的滾動時域調度模型相對于其它五種常規調度規則的平均改進比最大值為24.99%，最小值為7.15%，體現了PSO算法對滾動時域策略下的批調度模型有較強的適用性；其次，調度周期T為50，SPT規則效果最佳；調度周期T為100、150時，WALT規則效果最佳。在相同工件數的情況下，隨調度周期的增加，由于SPT規則未考慮工件權重信息，調度結果也隨之增大。但調度周期的長短對FIFO、PSF、WLAT、WSPT四種規則的調度結果影響較小。工件密集到達，按照WLAT規則排序后不僅可保證較大權重的工件及早加工，而且批的開始加工時間較小。因此，WLAT規則在處理密集到達工件的調度時有較大優勢。

圖2 r=0.1時調度結果 圖3 r=0.2時調度結果

圖3為r=0.2時的調度結果。PSO算法下調度結果的平均改進比值在7.9%到31.78%間，FIFO規則明顯優于WSPT規則，但WLAT規則效果仍是最好的。此外，隨著調度周期變大，SPT、WSPT和PSF規則的調度結果也逐漸增大。

圖4和圖5分別為r=0.3、r=0.4時的調度結果。滾動時域批調度模型中PSO算法相對于常規調度規則的平均改進仍然可觀。在所有算例中，五種簡單調度規則中FIFO規則的調度優化效果相對最優，其次為WLAT規則，再次之為WSPT規則，PSF和SPT規則調度效果最差。相同工件數的算例中，除FIFO規則外，其它四種調度規則都是隨時域周期的增大，調度結果增大。

圖4 r=0.3時調度結果 圖5 r=0.4時調度結果

圖6 r=0.5時調度結果

圖6為r=0.5時的調度結果。此時，與其它常規調度規則相比，FIFO規則仍表現出極好的性能，但PSO算法調度結果在各調度周期下相對于FIFO規則的優化效果則不明顯。說明了PSO算法在處理工件分散到達的情況下優化效果不盡理想。導致這一現象的原因主要有兩點：①工件到達時間間隔較長，各調度時域內到達的工件數量少，導致調度時域內待調度工件數量也較少，PSO算法的優化迭代性能得不到體現；②工件到達較為分散，導致整個調度過程產生較多的調度周期。盡管PSO算法調度過程中，各時域內都設定了懲罰函數以確保局部調度目標與全局目標相一致，但過多的局部調度仍然會對全局目標產生不小的影響。

綜合圖2到圖6以及圖7，可知：

1)除了在r=0.1，調度周期為T1、工件數分別為80和100的兩個算例，PSO算法下批調度模型優化后的調度結果均優于常規調度規則，說明基于PSO算法的滾動時域批調度模型具有很好的調度優化效果。這兩個算例中SPT規則較優的原因是由于工件到達時間間隔較短，且每個時域內需加工的批數又相對較少，造成工件在批處理車間的阻塞，導致在每個調度周期的決策時刻，可供調度的工件數目較多。此時，按照工件加工時間排序還會使得絕大部分時域內調度批數的增加，因而SPT規則的調度結果較理想。

2)FIFO、PSF、WLAT、WSPT、SPT五種常規調度規則中，隨著工件到達時間的增加，FIFO規則的調度優化效果逐漸優于WLAT規則的調度效果，且調度周期的長短對FIFO規則影響較小，從而間接證明了FIFO規則在實際調度中作為最常用的調度規則有獨有優勢。

3)附錄中的圖5中，三條折線均為先升后降的走勢，說明隨到達時間參數r取值的增大，即工件到達由密集到分散時， PSO算法下滾動時域批調度模型的調度優化性能先上升后下降。其次，由折線的不同高度可知，隨調度周期T的增大，模型及PSO算法的調度優化效果增強。這表明，PSO算法下滾動時域批調度模型在解決調度周期長的批調度問題中效果更佳，優勢明顯。

圖7 到達參數、時域周期與平均改進比折線圖

綜上，當到達參數固定后，在調度周期較長(即T越大)的批調度問題中， PSO算法下滾動時域批調度模型的效果越好。考慮極限的情況，即當T→∞時，PSO算法可達到最優調度，此時的批調度策略為一次的全局靜態調度，調度結果為滾動時域批調度問題的下界；當T→0時，PSO算法優化效果差，此時批調度方法為實時在線調度，調度結果為滾動時域批調度問題的上界。

6 結束語

設計了滾動時域調度策略，加入目標懲罰函數，得出PSO算法下各調度時域內的局部最優調度。仿真結果表明滾動時域調度策略下，PSO算法在解決工件密集到達以及調度周期較長的批調度問題時優化性能較好。同時，隨著調度周期增多，懲罰函數越能影響調度效果。但調度時域內局部懲罰函數的設定并未有統一的標準，決策人員只能根據調度目標和實際調度情況進行調整。