基于插入-分段的無等待流水作業(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)以及制品庫(kù)存的最小化.該問題在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ì)越來越長(zhǎng)，難以適用于實(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í)間，即

式中，

根據(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è)解π*，使得

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 為

式中，

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

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

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

證畢.

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

定理3 若將解π中分別位于位置p 和q 的任務(wù)π［p］和π［q］(1 ≤p ＜q ≤n)交換，則對(duì)換目標(biāo)增量ΔS 為

定理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).該算法的具體描述如下:

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 移位局部?jī)?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)系被改變，因此可采用移位局部?jī)?yōu)化算法(MLO)，對(duì)子解σ 進(jìn)行優(yōu)化.MLO 算法的具體描述如下:

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)行移位局部?jī)?yōu)化;重復(fù)上述過程直到Q 為空.

SGA 算法的具體描述如下:

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，F(xiàn)SR 和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 算法的具體描述如下:

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í)間的算法比較，即不限定GAVNS 算法在每個(gè)實(shí)例上的運(yùn)行時(shí)間，進(jìn)行算法比較.

所有算法都采用Java 語(yǔ)言實(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］

式中，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)算法次之，F(xiàn)NM 算法最高，這是因?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 算法和GAVNS 算法的平均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é)語(yǔ)

針對(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).

References)

［1］Laha D，Chakraborty U K.A constructive heuristic for minimizing makespan in no-wait flow shop scheduling［J］.International Journal of Advanced Manufacturing Technology，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］.Science in China Series F:Information Sciences，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］.Engineering Optimization，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］.International Journal of Advanced Manufacturing Technology，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］.International Journal of Advanced Manufacturing Technology，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 ＆Operations Research，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］.International Journal of Advanced Manufacturing Technology，2011，54(9/10/11/12):1129-1143.

［9］Rajendran C，Chaudhuri D.Heuristic algorithms for continuous flow-shop problem［J］.Naval Research Logistics，1990，37(5):695-705.

［10］Bertolissi E.Heuristic algorithm for scheduling in the no-wait flow-shop［J］.Journal of Materials Technology，2000，107(1/2/3):459-465.

［11］Nawaz M，Enscore E E，Ham I.A heuristic algorithm for m-machine n-job flow-shop sequencing problem［J］.Omega，1983，11(1):91-95.

［12］Taillard E.Benchmarks for basic scheduling problems［J］.European Journal of Operational Research，1993，64(2):278-285.