基于插入-分段的無等待流水作業(yè)調(diào)度復(fù)合啟發(fā)式算法

李亞志 朱 夏

(東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,南京 211189)

(東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)與信息集成教育部重點(diǎn)實(shí)驗(yàn)室,南京 211189)

無等待流水作業(yè)調(diào)度是實(shí)際生產(chǎn)調(diào)度環(huán)境中一個(gè)重要的有約束組合優(yōu)化問題,可描述為:n個(gè)任務(wù)在m臺(tái)機(jī)器上按給定加工時(shí)間,順序進(jìn)行加工,且任務(wù)在加工過程中不能被中斷.常見的優(yōu)化目標(biāo)有最小化最大完工時(shí)間[1-2]、總延遲[3]和總完工時(shí)間[4-6]等.其中,最小化總完工時(shí)間是實(shí)際應(yīng)用中的重要指標(biāo),可促進(jìn)資源的穩(wěn)定有效利用、任務(wù)的快速周轉(zhuǎn)以及制品庫存的最小化.該問題在m≥2時(shí)為NP-難問題[4].

目前,通常采用元啟發(fā)式和啟發(fā)式算法求解該問題.元啟發(fā)式算法包括聲搜索算法[6]、離散粒子群算法[7]、基于可變鄰域搜索的混合遺傳算法[8]等.啟發(fā)式算法可分為構(gòu)造啟發(fā)式算法和復(fù)合啟發(fā)式算法.Rajendran等[9]提出了2種基于任務(wù)插入的構(gòu)造啟發(fā)式算法.Bertolissi[10]提出了1種基于比較的構(gòu)造啟發(fā)式算法.Aldowaisan等[4]基于置換策略提出了4種復(fù)合啟發(fā)式算法.Framinan等[5]提出了1種復(fù)合啟發(fā)式算法(FNM).FNM算法是目前用于求解最小化總完工時(shí)間的無等待流水作業(yè)調(diào)度問題的最新復(fù)合啟發(fā)式算法.

元啟發(fā)式算法隨著任務(wù)數(shù)n的增加,其運(yùn)行時(shí)間會(huì)越來越長,難以適用于實(shí)時(shí)性要求高的大規(guī)模無等待流水作業(yè)調(diào)度問題．在啟發(fā)式算法中,鄰域結(jié)構(gòu)的設(shè)計(jì)是提高算法性能的關(guān)鍵．鑒于此,本文構(gòu)造了一個(gè)基于插入-分段的鄰域結(jié)構(gòu),提出了一種基于插入-分段的復(fù)合啟發(fā)式算法(ISCH),同時(shí)采用文獻(xiàn)[2]提出的目標(biāo)增量法來評(píng)價(jià)新構(gòu)造的解,降低算法運(yùn)行時(shí)間．

1 問題描述

最小化總完工時(shí)間的無等待流水作業(yè)調(diào)度問題可描述為,從零時(shí)刻開始,n個(gè)具有相同工藝路線的任務(wù)按照給定加工次序,在m臺(tái)機(jī)器上順序加工,且滿足如下假設(shè):① 每臺(tái)機(jī)器1次只能加工1個(gè)任務(wù);② 每個(gè)任務(wù)不能同時(shí)在多臺(tái)機(jī)器上加工;③ 工序準(zhǔn)備時(shí)間包含在加工時(shí)間內(nèi),與順序無關(guān);④ 任務(wù)一旦開始加工便不允許中斷;⑤ 任務(wù)未到達(dá)時(shí)允許機(jī)器閑置.

設(shè)任務(wù)j在機(jī)器k上的加工時(shí)間為tj,k.Tj為任務(wù)j在m臺(tái)機(jī)器上的加工時(shí)間之和.在解π中引入開始虛任務(wù)j0,規(guī)定j0在每臺(tái)機(jī)器上的加工時(shí)間為0.得到n+1個(gè)任務(wù)的一個(gè)解π={π[0],π[1],π[2],…,π[n]},且π[0]≡j0.令di,j為解π的相鄰任務(wù)i和j在第1臺(tái)機(jī)器上的開工時(shí)間間隔 (即二者的距離).則解π的目標(biāo)函數(shù)值是總完工時(shí)間，即

(1)

式中,

(2)

根據(jù)式(2)可以求出由n+1個(gè)任務(wù)組成的任意2個(gè)不同任務(wù)之間的距離矩陣.同時(shí)規(guī)定，對(duì)任務(wù)j,dj,j=∞(1≤j≤n);虛任務(wù)j0是任意解π的起始任務(wù),它不會(huì)成為任何其他任務(wù)的后繼,故dj,j0=∞(1≤j≤n).由于求解di,j的時(shí)間復(fù)雜度為O(m),因此,求解距離矩陣的時(shí)間復(fù)雜度為O(mn2).

基于已知的距離矩陣,求解F(π)的時(shí)間復(fù)雜度為O(n),而求最小化總完工時(shí)間的無等待流水作業(yè)調(diào)度問題的最優(yōu)解就是在全體可行解空間Π中找到一個(gè)解π*,使得

F(π*)≤F(π) ?π∈Π

(3)

2 基本性質(zhì)

啟發(fā)式算法的基本思想是搜索．常用的基本鄰域結(jié)構(gòu)操作主要有3種:插入、移位和對(duì)換.根據(jù)無等待流水作業(yè)調(diào)度的解中任務(wù)距離的獨(dú)立性和式(1),應(yīng)用目標(biāo)增量法[2],對(duì)這3種基本操作的性質(zhì)進(jìn)行分析.

定理1若將任務(wù)j插入到解π中的位置p(0≤p≤n)之后,則插入目標(biāo)增量ΔI為

(4)

式中，

π′={π[0],…,π[p],j,π[p+2],…,π[n+1]}

證明解π′的總完工時(shí)間為

(5)

式中，n′=n+1為解π′的任務(wù)數(shù).

式(5)減去式(1),得

ΔI=F(π′)-F(π)=

證畢．

定理2若將解π中的任務(wù)π[p]從位置p移到位置q(1≤p,q≤n),則移位目標(biāo)增量ΔM為

(6)

定理3若將解π中分別位于位置p和q的任務(wù)π[p]和π[q](1≤p

(7)

定理2和定理3的證明過程類似于定理1.

使用由3種基本操作構(gòu)成的鄰域結(jié)構(gòu)進(jìn)行搜索,可使目標(biāo)增量的時(shí)間復(fù)雜度降為O(1).因此,應(yīng)用基本操作的目標(biāo)增量方法可以大大減少算法的運(yùn)行時(shí)間.

3 ISCH算法

本文針對(duì)最小化完工時(shí)間的無等待流水作業(yè)調(diào)度問題提出ISCH算法．其主要思想為:首先,根據(jù)問題特點(diǎn)構(gòu)造初始解;然后,從初始解中依次選取一個(gè)未處理任務(wù),在當(dāng)前解中找到任務(wù)最佳插入位置,并采用基于插入-分段的優(yōu)化方法優(yōu)化新解;迭代上述過程,直至初始解為空;最后,應(yīng)用迭代序?qū)?duì)換算法是(IBSC)進(jìn)一步優(yōu)化當(dāng)前解,得到問題的最終解.

3.1 基本鄰域結(jié)構(gòu)的最佳操作

根據(jù)定理1,當(dāng)一個(gè)新任務(wù)插入到當(dāng)前解的所有可能位置時(shí),可求出插入到這些位置的目標(biāo)函數(shù)增量;選取引起目標(biāo)函數(shù)增量最小的位置作為最佳插入位置,將新任務(wù)插入到這個(gè)位置產(chǎn)生新解,而無需產(chǎn)生整個(gè)鄰域的解.由此,便可構(gòu)造基本鄰域結(jié)構(gòu)的新任務(wù)最佳位置插入算法(JBIP).該算法的具體描述如下:

1 Temp=∞,Pos=-1;

2 Forp=0 ton

根據(jù)定理1計(jì)算當(dāng)任務(wù)j插入到解π的位置p之后的增量ΔI;

如果Temp>ΔI,則Temp=ΔI,Pos=p;

3 如果Pos≠-1,則將新任務(wù)j插入到解π的最佳插入位置Pos,得到新的解π;

4 返回π.

JBIP算法的時(shí)間開銷主要在第2步,其時(shí)間復(fù)雜度均為O(n),因此JBIP算法的時(shí)間復(fù)雜度為O(n).

類似地,可根據(jù)定理2和定理3分別構(gòu)造出時(shí)間復(fù)雜度均為O(n)的任務(wù)最佳移位算法(JBMP)和任務(wù)對(duì)最佳對(duì)換算法(JBSP).

3.2 初始解生成算法

初始解對(duì)最終解有重要影響.本文提出了一種將所有任務(wù)按照Tj非降序排序的初始解生成方法(ISG),若存在加工時(shí)間相同的任務(wù),則根據(jù)式(2)優(yōu)先排序距離當(dāng)前已排序解中尾任務(wù)最近的任務(wù).

3.3 移位局部優(yōu)化算法

應(yīng)用JBIP算法可得任務(wù)j的最佳插入位置,同時(shí)將解π分段成左、右2個(gè)子解πL={π[1],…,π[Pos],j}和πR={j,π[Pos+1],…,π[k]}.由于2個(gè)子解任務(wù)間的內(nèi)在原有關(guān)聯(lián)關(guān)系被改變,因此可采用移位局部優(yōu)化算法(MLO),對(duì)子解σ進(jìn)行優(yōu)化.MLO算法的具體描述如下:

1 令n為子解σ的長度;

2 Forp=1 ton

如果σ[p]≠j,則

調(diào)用最佳移位算法JBMP,尋找σ[p]在σ中的最佳移位位置并在σ中進(jìn)行移位操作;

3 返回σ.

MLO算法的時(shí)間開銷主要在第2步,其時(shí)間復(fù)雜度為O(n2),故該算法的時(shí)間復(fù)雜度為O(n2).

3.4 構(gòu)造解算法

構(gòu)造解算法(SGA)用于構(gòu)造生成新的解．本文采用NEH算法思想[11],設(shè)計(jì)SGA算法.其基本思想為:從初始解Q中選取1個(gè)未排序任務(wù)插入到當(dāng)前解πC的最佳位置,采用MLO算法對(duì)左、右2個(gè)子解πLC和πRC分別進(jìn)行移位局部優(yōu)化;重復(fù)上述過程直到Q為空.

SGA算法的具體描述如下:

1πC=Φ;

2 Forp=1 ton

調(diào)用最佳位置插入算法JBIP將Q[p]插入πC;

將πC中Q[p]兩側(cè)的子解(含Q[p])置為πLC和πRC;

如果p≥3,則

調(diào)用移位局部優(yōu)化算法MLO(πLC,Q[p]);

調(diào)用移位局部優(yōu)化算法MLO(πRC,Q[p]);

3 返回πC.

SGA算法的時(shí)間開銷主要在第2步,其最壞時(shí)間復(fù)雜度為O(n3),故SGA算法的時(shí)間復(fù)雜度為O(n3).

3.5 迭代序?qū)?duì)換算法

針對(duì)SGA算法生成的解,可應(yīng)用序?qū)?duì)換算法進(jìn)行優(yōu)化[5].根據(jù)對(duì)換方向和后續(xù)操作起點(diǎn)的不同,對(duì)換可分為FSC,BSC,FSR和BSR四種.不同對(duì)換算法對(duì)相同解的優(yōu)化效果不相同,其中BSC算法對(duì)解的優(yōu)化效果最好[2].另外,實(shí)驗(yàn)發(fā)現(xiàn),在一定的迭代次數(shù)內(nèi),BSC算法能進(jìn)一步優(yōu)化解.因此,本文采用迭代序?qū)?duì)換算法優(yōu)化解,結(jié)束條件為臨時(shí)解πS不能再優(yōu)化或者迭代次數(shù)t超過10.

IBSC算法的具體描述如下:

1t=0,TCT=F(π);

2 Repeat

Flag=False;

Forp=nto 1

對(duì)任務(wù)πS,[p]調(diào)用最佳對(duì)換算法JBSP;

如果TCT>F(πS),則

TCT=F(πS),π=πS;

否則

Flag=True,Break;

t=t+1;

Until (Flag=True ort>10)

3 返回π.

IBSC算法的時(shí)間開銷主要在第2步,其時(shí)間復(fù)雜度為O(n2),故IBSC算法的時(shí)間復(fù)雜度為O(n2).

3.6 ISCH算法

求解最小化總完工時(shí)間的無等待流水作業(yè)調(diào)度問題的ISCH算法步驟如下:

① 參數(shù)初始化;

② 根據(jù)式(1)生成距離矩陣;

③ 調(diào)用ISG算法生成初始解;

④ 調(diào)用SGA算法構(gòu)造解;

⑤ 調(diào)用IBSC算法改進(jìn)解;

⑥ 根據(jù)式(2)計(jì)算解的目標(biāo)函數(shù)值.

ISCH算法的時(shí)間開銷主要在第②步和第④步.其中,第②步的時(shí)間復(fù)雜度是O(mn2),第④步的時(shí)間復(fù)雜度是O(n3),故ISCH算法的時(shí)間復(fù)雜度為max{O(mn2),O(n3)}.

4 算法性能測(cè)試

針對(duì)最小化總完工時(shí)間的無等待流水作業(yè)調(diào)度問題,將ISCH算法與BE算法[10]、PH1(p)算法[5]、FNM算法[4]和GA-VNS算法[8]進(jìn)行比較.同時(shí),為了公平全面地比較ISCH算法和GA-VNS算法,設(shè)計(jì)了如下2組實(shí)驗(yàn):①限定運(yùn)行時(shí)間的算法比較,即將GA-VNS算法在每個(gè)實(shí)例上的運(yùn)行時(shí)間近似等于ISCH算法的運(yùn)行時(shí)間,進(jìn)行算法比較;②不限定運(yùn)行時(shí)間的算法比較,即不限定GA-VNS算法在每個(gè)實(shí)例上的運(yùn)行時(shí)間,進(jìn)行算法比較.

所有算法都采用Java語言實(shí)現(xiàn),利用文獻(xiàn)[12]中的120個(gè)Benchmark實(shí)例進(jìn)行測(cè)試,運(yùn)行于Pentium 2.93 GHz,512 M內(nèi)存的PC機(jī)上.

算法性能指標(biāo)采用平均相對(duì)偏差,其計(jì)算公式為[2]

(8)

式中,N表示具有相同規(guī)模的實(shí)例個(gè)數(shù);Fz(H)表示采用算法H求解實(shí)例z得到的總完工時(shí)間;Bz為采用所有比較算法求解實(shí)例z得到的最小總完工時(shí)間．顯然,ARPD值越大,算法性能越差．

4.1 限定運(yùn)行時(shí)間的算法比較

在限定GA-VNS算法運(yùn)行時(shí)間的情況下,5種算法的運(yùn)行時(shí)間和性能分別見表1和表2.

表1 限定條件的運(yùn)行時(shí)間比較 s

由表1可以看出,BE算法的運(yùn)行時(shí)間最短,即使對(duì)于ta12組的實(shí)例,該算法的運(yùn)行時(shí)間也僅僅需要0.403 s.PH1(p)算法、FNM算法和ISCH算法中,ISCH算法的運(yùn)行時(shí)間最短,PH1(p) 算法次之,FNM算法最高,這是因?yàn)槟繕?biāo)增量法可大大降低ISCH算法的運(yùn)行時(shí)間．

表2 限定條件的ARPD比較 %

由表2可以看出,BE算法的性能明顯比其他算法差.FNM算法的平均性能優(yōu)于PH1(p)算法．當(dāng)任務(wù)數(shù)n<100時(shí),ISCH算法的性能比FNM算法差,但明顯優(yōu)于PH1(p) 算法;當(dāng)任務(wù)數(shù)n≥100時(shí),ISCH算法的性能最好,其平均ARPD值小于PH1(p) 算法和FNM算法.因此,隨著任務(wù)數(shù)n的增大,ISCH算法能在較短的時(shí)間內(nèi)得到更好的解.盡管在某些小規(guī)模實(shí)例(如ta03組和ta06組)上,ISCH算法的性能比GA-VNS算法差,但其平均ARPD值較GA-VNS算法提高0.99%(在問題規(guī)模較大時(shí),其目標(biāo)函數(shù)值較大,故對(duì)解的優(yōu)化效果很明顯),其主要原因是GA-VNS算法的運(yùn)行時(shí)間被限定,搜索空間縮小,故解的性能必然下降.

4.2 無運(yùn)行時(shí)間限定的算法比較

在不限定GA-VNS算法運(yùn)行時(shí)間的情況下,5種算法的運(yùn)行時(shí)間和性能分別見表3和表4.

表3 無限定條件的運(yùn)行時(shí)間比較 s

表4 無限定條件的ARPD比較 %

將表1和表3相比較,4種啟發(fā)式算法的運(yùn)行時(shí)間并沒有發(fā)生變化.由于GA-VNS算法的搜索范圍大大增加,故其需要的運(yùn)行時(shí)間遠(yuǎn)大于4種啟發(fā)式算法的時(shí)間.如當(dāng)n=500時(shí),GA-VNS算法的平均運(yùn)行時(shí)間約為10 237 s,而ISCH算法僅需不到80 s,前者約為后者的129倍.

由表4可知,無運(yùn)行時(shí)間限制時(shí),GA-VNS算法的性能最優(yōu),其平均ARPD值為0.532,高出ISCH算法約1.5%.但由表3可知,GA-VNS算法的運(yùn)行時(shí)間遠(yuǎn)大于ISCH算法的運(yùn)行時(shí)間.

因此,在實(shí)際的大規(guī)模調(diào)度問題中,如果只追求算法性能,可以采用GA-VNS算法;如果實(shí)時(shí)性要求很高,則可采用BE算法;如果同時(shí)兼顧實(shí)時(shí)性和性能,則可采用本文提出的ISCH算法.

4.3 任務(wù)數(shù)和機(jī)器數(shù)對(duì)算法的影響

限定運(yùn)行時(shí)間時(shí),算法的平均性能隨任務(wù)數(shù)和機(jī)器數(shù)的變化情況分別見表5和表6.

表5 不同任務(wù)數(shù)下算法平均ARPD值

表6 不同機(jī)器數(shù)下算法平均ARPD值

由表5可以看出,BE算法、FNM算法和GA-VNS算法的平均ARPD值隨著任務(wù)數(shù)n的增加出現(xiàn)一定的起伏,算法性能不穩(wěn)定.ISCH算法和PH1(p)算法的平均ARPD值均隨著任務(wù)數(shù)n的增加而逐漸降低,但I(xiàn)SCH算法的初始平均ARPD值優(yōu)于PH1(p)算法且下降更快.當(dāng)n>100時(shí),ISCH算法的平均ARPD值小于BE算法、FNM算法和GA-VNS算法.因此,隨著任務(wù)數(shù)n的增加,ISCH算法的性能越來越好.

由表6可以看出,隨著機(jī)器數(shù)m的增加,BE算法和FNM算法的平均ARPD值呈下降趨勢(shì),而GA-VNS算法、ISCH算法的平均ARPD值呈上升趨勢(shì),PH1(p) 算法的平均ARPD值起伏不大.總體而言,盡管隨機(jī)器數(shù)m的增加,ISCH算法的平均ARPD值在緩慢增大,其平均性能依然優(yōu)于其他算法,表現(xiàn)出穩(wěn)定的性能特性,因此ISCH算法適合于求解大規(guī)模流水調(diào)度問題.

5 結(jié)語

針對(duì)最小化總完工時(shí)間的無等待流水作業(yè)調(diào)度,本文提出了一種復(fù)合啟發(fā)式算法.首先,分析了2個(gè)任務(wù)之間的距離,推導(dǎo)出基本鄰域結(jié)構(gòu)操作的目標(biāo)增量性質(zhì);然后,構(gòu)造了基于插入-分段鄰域結(jié)構(gòu)和優(yōu)化方法,并提出了基于迭代對(duì)換的提高解方法.采用經(jīng)典Benchmark實(shí)例,將所提算法與目前經(jīng)典的啟發(fā)式算法和最新元啟發(fā)式算法進(jìn)行比較．結(jié)果表明,ISCH算法在實(shí)時(shí)性和性能2個(gè)方面均能兼顧,即在較短的時(shí)間內(nèi)能得到較好的解,適合于實(shí)時(shí)大規(guī)模無等待流水作業(yè)調(diào)度系統(tǒng).

)

[1]Laha D,Chakraborty U K.A constructive heuristic for minimizing makespan in no-wait flow shop scheduling[J].InternationalJournalofAdvancedManufacturingTechnology,2009,41(1/2): 97-109.

[2]Li X P,Wu C.Heuristic for no-wait flow shops with makespan minimization based on total idle-time increments[J].ScienceinChinaSeriesF:InformationSciences,2008,51(7): 896-909.

[3]Rahimi-Vahed A R,Javadi B,Rabbani M.A multi-objective scatter search for a bi-criteria no-wait flow shop scheduling problem[J].EngineeringOptimization,2008,40(4): 331-346.

[4]Aldowaisan T,Allahverdi A.New heuristics for m-machine no-wait flowshop to minimize total completion time[J].Omega,2004,32(5):345-352.

[5]Framinan J M,Nageno M S,Moccellin J V.An efficient heuristic for total flowtime minimization in no-wait flowshops[J].InternationalJournalofAdvancedManufacturingTechnology,2010,46(9/10/11/12): 1049-1057.

[6]Gao K Z,Pan Q K,Li J Q.Discrete harmony search algorithm for the no-wait flow shop scheduling problem with total flow time criterion[J].InternationalJournalofAdvancedManufacturingTechnology,2011,56(5/6/7/8): 683-692.

[7]Pan Q K.Tasgetiren M F,Liang Y C.A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem[J].Computers&OperationsResearch,2008,35(9): 2807-2839.

[8]Jarboui B,Eddaly M,Siarry P.A hybrid genetic algorithm for solving no-wait flow shop scheduling problems[J].InternationalJournalofAdvancedManufacturingTechnology,2011,54(9/10/11/12):1129-1143.

[9]Rajendran C,Chaudhuri D.Heuristic algorithms for continuous flow-shop problem[J].NavalResearchLogistics,1990,37(5): 695-705.

[10]Bertolissi E.Heuristic algorithm for scheduling in the no-wait flow-shop[J].JournalofMaterialsTechnology,2000,107(1/2/3):459-465.

[11]Nawaz M,Enscore E E,Ham I.A heuristic algorithm form-machinen-job flow-shop sequencing problem[J].Omega,1983,11(1):91-95.

[12]Taillard E.Benchmarks for basic scheduling problems[J].EuropeanJournalofOperationalResearch,1993,64(2): 278-285.