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

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

1 引言

批調(diào)度問(wèn)題主要指工件排序及工件合批，是半導(dǎo)體生產(chǎn)過(guò)程中提煉出的新型調(diào)度問(wèn)題[1]。合批根據(jù)批處理設(shè)備的容量、工件形狀材質(zhì)、工件到達(dá)時(shí)間以及加工成本等多種因素綜合處理。因此，批調(diào)度在求解難度上遠(yuǎn)高于古典調(diào)度[2]。實(shí)踐生產(chǎn)中，批調(diào)度以適當(dāng)?shù)臅r(shí)間周期或事件驅(qū)動(dòng)進(jìn)行循環(huán)調(diào)度，僅需考慮怎樣對(duì)某一時(shí)段內(nèi)的工件分批、排程[3]，將動(dòng)態(tài)、長(zhǎng)期的全局調(diào)度問(wèn)題分解為各時(shí)段內(nèi)靜態(tài)的局部子調(diào)度問(wèn)題。傳統(tǒng)批調(diào)度在各調(diào)度周期內(nèi)只使用一種方法和一種確定的規(guī)則來(lái)解決問(wèn)題，以便于調(diào)度的實(shí)現(xiàn)。而滾動(dòng)時(shí)域調(diào)度方法則是時(shí)間驅(qū)動(dòng)的循環(huán)調(diào)度策略。

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

實(shí)際生產(chǎn)加工中，工件動(dòng)態(tài)到達(dá)處理設(shè)備，對(duì)工件信息了解有限。Ovacik和Marcos較早的將滾動(dòng)調(diào)度方法應(yīng)用到經(jīng)典調(diào)度問(wèn)題中并取得了較好的效果[13，14]。但是，滾動(dòng)時(shí)域調(diào)度策略下，各調(diào)度周期內(nèi)只進(jìn)行局部調(diào)度且很難考慮全局信息，因此，無(wú)法對(duì)全局調(diào)度性能指標(biāo)作估計(jì)和控制[15]。Nelson和Sourirajan將滾動(dòng)調(diào)度策略和實(shí)時(shí)狀態(tài)信息結(jié)合起來(lái)，首先把動(dòng)態(tài)調(diào)度過(guò)程細(xì)分為多個(gè)連續(xù)靜態(tài)調(diào)度，再在每個(gè)區(qū)間內(nèi)逐個(gè)優(yōu)化，最后達(dá)到局部最優(yōu)[16，17]，進(jìn)一步適應(yīng)動(dòng)態(tài)生產(chǎn)環(huán)境的不斷變化，該研究表明滾動(dòng)調(diào)度策略在解決調(diào)度問(wèn)題上極具適用性[18]。

針對(duì)工件動(dòng)態(tài)到達(dá)且調(diào)度開始時(shí)刻工件信息不完全的批調(diào)度問(wèn)題，在時(shí)域內(nèi)利用粒子群算法進(jìn)行調(diào)度優(yōu)化尋求局部調(diào)度最優(yōu)，并加入懲罰函數(shù)，確保局部調(diào)度目標(biāo)與全局目標(biāo)一致。對(duì)滾動(dòng)時(shí)域策略下各調(diào)度規(guī)則下的調(diào)度結(jié)果進(jìn)行了仿真，并對(duì)此類動(dòng)態(tài)調(diào)度問(wèn)題中不同參數(shù)取值下的仿真結(jié)果進(jìn)行了討論。

2 滾動(dòng)時(shí)域策略下批調(diào)度數(shù)學(xué)建模

2.1 滾動(dòng)時(shí)域批調(diào)度問(wèn)題描述

圖1 時(shí)域l中工件調(diào)度流程圖

2.2 符號(hào)說(shuō)明

參數(shù)符號(hào)：

T：調(diào)度時(shí)域周期長(zhǎng)度；

B：批處理設(shè)備的容量；

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

rtj：工件j的到達(dá)時(shí)間；

ptj：工件j的加工時(shí)間；

sj：工件j的尺寸；

weightj：工件j的權(quán)重參數(shù)；

決策變量符號(hào)：

l：調(diào)度時(shí)域個(gè)數(shù)集，其中l(wèi)∈{1，2，…，L}，L為調(diào)度時(shí)域個(gè)數(shù)的最大值；

ctj：工件j的完工時(shí)間；

bhl：時(shí)域l內(nèi)待加工工件集；

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

RTkl：批bkl的到達(dá)時(shí)間；

STkl：批bkl的開始時(shí)間；

PTkl：批bkl的加工時(shí)間；

CTkl：批bkl的完工時(shí)間；

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

Sl：時(shí)域l內(nèi)得到加工的工件集；

S′l：時(shí)域l內(nèi)未得到加工的工件集。

2.3 模型假設(shè)

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

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

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

當(dāng)k=1時(shí)

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

(1)

當(dāng)k=2，3，…，Kl時(shí)

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

(2)

從而，批bkl的完工時(shí)間CTkl為

CTkl=STkl+PTkl

(3)

4) 調(diào)度時(shí)域l的周期為T。上一時(shí)域的結(jié)束時(shí)間即為下一時(shí)域的開始時(shí)間，某一時(shí)域的結(jié)束時(shí)間為該時(shí)域內(nèi)最后一個(gè)批次的完工時(shí)間。

2.4 滾動(dòng)時(shí)域批調(diào)度數(shù)學(xué)模型

(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)是目標(biāo)函數(shù)，表示最小加權(quán)完工時(shí)間和；式(5)中，Yjkl為{0，1}決策變量，當(dāng)工件j屬于時(shí)域l中第k批時(shí)，Yjkl=1，否則，Yjkl=0；式(6)用以確保所有工件都能得到分批且工件不會(huì)重復(fù)加工；式(7)是工件分批的主要約束條件，表示同一批次內(nèi)所有工件的尺寸和應(yīng)當(dāng)不超過(guò)批設(shè)備容量；式(8)表示時(shí)域l中已加工的工件集；式(9)表示時(shí)域l中還沒(méi)有加工的工件集；式(10)表示時(shí)域l中加工工件數(shù)；式(11)表示時(shí)域l內(nèi)工件分批數(shù)量。

3 滾動(dòng)時(shí)域批調(diào)度PSO算法實(shí)現(xiàn)

3.1 模型的初始化

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

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

時(shí)域l中，以先到先加工的規(guī)則進(jìn)行工件初始調(diào)度，bhl按rtj從小到大依次排序。若rtj相同，ptj越小，工件排序越靠前。得到時(shí)域l內(nèi)工件調(diào)度的初始排序πl(wèi)，πl(wèi)(i)表示πl(wèi)的第i個(gè)工件。令第1個(gè)工件優(yōu)先值為πl(wèi)(1)=rand(0，1)，其它工件優(yōu)先值為[19]

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

(12)

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

為保證調(diào)度目標(biāo)，決策人員不會(huì)為了盡可能填滿批設(shè)備而無(wú)限制的等待滿足容量約束的工件到達(dá)。對(duì)于活批bk，在批等待時(shí)間內(nèi)到達(dá)的所有工件都可以合入成為同一批。分批規(guī)則：對(duì)于工件j有兩種安排方式，一是若當(dāng)前不存在批，或不存在對(duì)于j的活批，則j生成新的批，此時(shí)新的批為活批；二是若存在對(duì)于j的活批bk，當(dāng)j的到達(dá)時(shí)間與活批bk的到達(dá)時(shí)間間隔大于批等待時(shí)間，j進(jìn)入新批，此時(shí)活批bk為確定批；否則，bk仍為活批。

4 局部懲罰函數(shù)與算法流程

4.1 局部調(diào)度懲罰函數(shù)

滾動(dòng)時(shí)域調(diào)度下，①各調(diào)度時(shí)域結(jié)束時(shí)，部分工件已完成加工，后續(xù)時(shí)域中全局調(diào)度的自由度減?。虎诟髡{(diào)度時(shí)域下只加工部分工件，全局信息少。因此，時(shí)域l中目標(biāo)懲罰函數(shù)Δfl表示為

(13)

(14)

4.2 批調(diào)度算法流程

Step1：給出初始時(shí)刻信息不完全的n個(gè)工件集合S；

Step2：根據(jù)工件到達(dá)時(shí)間確定第一個(gè)時(shí)域l內(nèi)待加工工件集合bhl，該時(shí)域內(nèi)工件信息已知；

Step5：返回局部最優(yōu)調(diào)度適應(yīng)值fl，可得工件排序和分批，進(jìn)而求得時(shí)域l內(nèi)的最優(yōu)目標(biāo)值Fl以及時(shí)域l內(nèi)得到處理的工件集Sl和未得到處理的工件集S′l；

Step6：令Tabu={j|j∈S-Sl}，若Tabu不為空集，將時(shí)域l內(nèi)未熱處理的工件集合S′l滾動(dòng)進(jìn)入l+1時(shí)域，與step2中的bhl+1合并，即bhl+1=S′l∪bhl+1，進(jìn)入step3；若為空集，結(jié)束。

5 仿真研究

5.1 仿真參數(shù)設(shè)計(jì)與算法有效性分析

5.1.1 仿真參數(shù)設(shè)計(jì)

本文采用Melouks等提出的隨機(jī)產(chǎn)生數(shù)據(jù)的方法獲得算例[20]，算例劃分標(biāo)準(zhǔn)如下：

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

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

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

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

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

對(duì)五種常規(guī)調(diào)度介紹如下，后續(xù)對(duì)五種常規(guī)調(diào)度的調(diào)度結(jié)果與PSO算法下批調(diào)度模型優(yōu)化后的調(diào)度結(jié)果進(jìn)行比較。

1)先到先加工(FIFO)規(guī)則，調(diào)度時(shí)域內(nèi)工件按到達(dá)時(shí)間rt非降生成排序，常用于調(diào)度車間的一般調(diào)度問(wèn)題中；

2)基于優(yōu)先權(quán)優(yōu)先(PSF)規(guī)則，調(diào)度時(shí)域內(nèi)工件按其權(quán)重weight非增生成排序，常用于工件含權(quán)重參數(shù)的批調(diào)度問(wèn)題，但此調(diào)度規(guī)則容易造成熱處理爐等批處理設(shè)備的空閑時(shí)間；

3)加權(quán)最小到達(dá)時(shí)間優(yōu)先(WLAT)規(guī)則，調(diào)度時(shí)域內(nèi)工件按其重要度與到達(dá)時(shí)間的比值weight/rt非增生成排序，是FIFO規(guī)則和PSF規(guī)則的折中，不會(huì)導(dǎo)致熱處理爐產(chǎn)生大量的空閑等待時(shí)間；

4)加權(quán)最短加工時(shí)間優(yōu)先(WSPT)規(guī)則，調(diào)度時(shí)域內(nèi)工件按重要度與加工時(shí)間的比值weight/pt非增生成排序，在解決目標(biāo)為加權(quán)完工時(shí)間和靜態(tài)全局調(diào)度的問(wèn)題中效果最佳；

5)最短加工時(shí)間優(yōu)先(SPT)規(guī)則，能在解決大規(guī)模工件的靜態(tài)調(diào)度問(wèn)題中實(shí)現(xiàn)出很好的優(yōu)化性能。

5.1.2 基于PSO算法的滾動(dòng)時(shí)域批調(diào)度模型的有效性與適用性分析

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

圖2 r=0.1時(shí)調(diào)度結(jié)果 圖3 r=0.2時(shí)調(diào)度結(jié)果

圖3為r=0.2時(shí)的調(diào)度結(jié)果。PSO算法下調(diào)度結(jié)果的平均改進(jìn)比值在7.9%到31.78%間，F(xiàn)IFO規(guī)則明顯優(yōu)于WSPT規(guī)則，但WLAT規(guī)則效果仍是最好的。此外，隨著調(diào)度周期變大，SPT、WSPT和PSF規(guī)則的調(diào)度結(jié)果也逐漸增大。

圖4和圖5分別為r=0.3、r=0.4時(shí)的調(diào)度結(jié)果。滾動(dòng)時(shí)域批調(diào)度模型中PSO算法相對(duì)于常規(guī)調(diào)度規(guī)則的平均改進(jìn)仍然可觀。在所有算例中，五種簡(jiǎn)單調(diào)度規(guī)則中FIFO規(guī)則的調(diào)度優(yōu)化效果相對(duì)最優(yōu)，其次為WLAT規(guī)則，再次之為WSPT規(guī)則，PSF和SPT規(guī)則調(diào)度效果最差。相同工件數(shù)的算例中，除FIFO規(guī)則外，其它四種調(diào)度規(guī)則都是隨時(shí)域周期的增大，調(diào)度結(jié)果增大。

圖4 r=0.3時(shí)調(diào)度結(jié)果 圖5 r=0.4時(shí)調(diào)度結(jié)果

圖6 r=0.5時(shí)調(diào)度結(jié)果

圖6為r=0.5時(shí)的調(diào)度結(jié)果。此時(shí)，與其它常規(guī)調(diào)度規(guī)則相比，F(xiàn)IFO規(guī)則仍表現(xiàn)出極好的性能，但PSO算法調(diào)度結(jié)果在各調(diào)度周期下相對(duì)于FIFO規(guī)則的優(yōu)化效果則不明顯。說(shuō)明了PSO算法在處理工件分散到達(dá)的情況下優(yōu)化效果不盡理想。導(dǎo)致這一現(xiàn)象的原因主要有兩點(diǎn)：①工件到達(dá)時(shí)間間隔較長(zhǎng)，各調(diào)度時(shí)域內(nèi)到達(dá)的工件數(shù)量少，導(dǎo)致調(diào)度時(shí)域內(nèi)待調(diào)度工件數(shù)量也較少，PSO算法的優(yōu)化迭代性能得不到體現(xiàn)；②工件到達(dá)較為分散，導(dǎo)致整個(gè)調(diào)度過(guò)程產(chǎn)生較多的調(diào)度周期。盡管PSO算法調(diào)度過(guò)程中，各時(shí)域內(nèi)都設(shè)定了懲罰函數(shù)以確保局部調(diào)度目標(biāo)與全局目標(biāo)相一致，但過(guò)多的局部調(diào)度仍然會(huì)對(duì)全局目標(biāo)產(chǎn)生不小的影響。

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

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

2)FIFO、PSF、WLAT、WSPT、SPT五種常規(guī)調(diào)度規(guī)則中，隨著工件到達(dá)時(shí)間的增加，F(xiàn)IFO規(guī)則的調(diào)度優(yōu)化效果逐漸優(yōu)于WLAT規(guī)則的調(diào)度效果，且調(diào)度周期的長(zhǎng)短對(duì)FIFO規(guī)則影響較小，從而間接證明了FIFO規(guī)則在實(shí)際調(diào)度中作為最常用的調(diào)度規(guī)則有獨(dú)有優(yōu)勢(shì)。

3)附錄中的圖5中，三條折線均為先升后降的走勢(shì)，說(shuō)明隨到達(dá)時(shí)間參數(shù)r取值的增大，即工件到達(dá)由密集到分散時(shí)， PSO算法下滾動(dòng)時(shí)域批調(diào)度模型的調(diào)度優(yōu)化性能先上升后下降。其次，由折線的不同高度可知，隨調(diào)度周期T的增大，模型及PSO算法的調(diào)度優(yōu)化效果增強(qiáng)。這表明，PSO算法下滾動(dòng)時(shí)域批調(diào)度模型在解決調(diào)度周期長(zhǎng)的批調(diào)度問(wèn)題中效果更佳，優(yōu)勢(shì)明顯。

圖7 到達(dá)參數(shù)、時(shí)域周期與平均改進(jìn)比折線圖

綜上，當(dāng)?shù)竭_(dá)參數(shù)固定后，在調(diào)度周期較長(zhǎng)(即T越大)的批調(diào)度問(wèn)題中， PSO算法下滾動(dòng)時(shí)域批調(diào)度模型的效果越好。考慮極限的情況，即當(dāng)T→∞時(shí)，PSO算法可達(dá)到最優(yōu)調(diào)度，此時(shí)的批調(diào)度策略為一次的全局靜態(tài)調(diào)度，調(diào)度結(jié)果為滾動(dòng)時(shí)域批調(diào)度問(wèn)題的下界；當(dāng)T→0時(shí)，PSO算法優(yōu)化效果差，此時(shí)批調(diào)度方法為實(shí)時(shí)在線調(diào)度，調(diào)度結(jié)果為滾動(dòng)時(shí)域批調(diào)度問(wèn)題的上界。

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

設(shè)計(jì)了滾動(dòng)時(shí)域調(diào)度策略，加入目標(biāo)懲罰函數(shù)，得出PSO算法下各調(diào)度時(shí)域內(nèi)的局部最優(yōu)調(diào)度。仿真結(jié)果表明滾動(dòng)時(shí)域調(diào)度策略下，PSO算法在解決工件密集到達(dá)以及調(diào)度周期較長(zhǎng)的批調(diào)度問(wèn)題時(shí)優(yōu)化性能較好。同時(shí)，隨著調(diào)度周期增多，懲罰函數(shù)越能影響調(diào)度效果。但調(diào)度時(shí)域內(nèi)局部懲罰函數(shù)的設(shè)定并未有統(tǒng)一的標(biāo)準(zhǔn)，決策人員只能根據(jù)調(diào)度目標(biāo)和實(shí)際調(diào)度情況進(jìn)行調(diào)整。