李亞志 朱 夏

(東南大學計算機科學與工程學院,南京 211189)

(東南大學計算機網(wǎng)絡與信息集成教育部重點實驗室,南京 211189)

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

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

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

1 問題描述

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

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

(1)

式中,

(2)

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

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

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

(3)

2 基本性質(zhì)

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

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

(4)

式中，

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

證明解π′的總完工時間為

(5)

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

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

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

證畢．

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

(6)

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

(7)

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

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

3 ISCH算法

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

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

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

1 Temp=∞,Pos=-1;

2 Forp=0 ton

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

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

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

4 返回π.

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

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

3.2 初始解生成算法

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

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

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

1 令n為子解σ的長度;

2 Forp=1 ton

如果σ[p]≠j,則

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

3 返回σ.

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

3.4 構(gòu)造解算法

構(gòu)造解算法(SGA)用于構(gòu)造生成新的解．本文采用NEH算法思想[11],設計SGA算法.其基本思想為:從初始解Q中選取1個未排序任務插入到當前解πC的最佳位置,采用MLO算法對左、右2個子解πLC和πRC分別進行移位局部優(yōu)化;重復上述過程直到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算法的時間開銷主要在第2步,其最壞時間復雜度為O(n3),故SGA算法的時間復雜度為O(n3).

3.5 迭代序?qū)Q算法

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

IBSC算法的具體描述如下:

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

2 Repeat

Flag=False;

Forp=nto 1

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

如果TCT>F(πS),則

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

否則

Flag=True,Break;

t=t+1;

Until (Flag=True ort>10)

3 返回π.

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

3.6 ISCH算法

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

① 參數(shù)初始化;

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

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

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

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

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

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

4 算法性能測試

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

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

算法性能指標采用平均相對偏差,其計算公式為[2]

(8)

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

4.1 限定運行時間的算法比較

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

表1 限定條件的運行時間比較 s

由表1可以看出,BE算法的運行時間最短,即使對于ta12組的實例,該算法的運行時間也僅僅需要0.403 s.PH1(p)算法、FNM算法和ISCH算法中,ISCH算法的運行時間最短,PH1(p) 算法次之,FNM算法最高,這是因為目標增量法可大大降低ISCH算法的運行時間．

表2 限定條件的ARPD比較 %

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

4.2 無運行時間限定的算法比較

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

表3 無限定條件的運行時間比較 s

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

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

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

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

4.3 任務數(shù)和機器數(shù)對算法的影響

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

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

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

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

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

5 結(jié)語

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