基于插入-分段的無等待流水作業調度復合啟發式算法

李亞志 朱 夏

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

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

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

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

元啟發式算法隨著任務數n 的增加，其運行時間會越來越長，難以適用于實時性要求高的大規模無等待流水作業調度問題.在啟發式算法中，鄰域結構的設計是提高算法性能的關鍵.鑒于此，本文構造了一個基于插入-分段的鄰域結構，提出了一種基于插入-分段的復合啟發式算法(ISCH)，同時采用文獻［2］提出的目標增量法來評價新構造的解，降低算法運行時間.

1 問題描述

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

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

式中，

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

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

2 基本性質

啟發式算法的基本思想是搜索.常用的基本鄰域結構操作主要有3 種:插入、移位和對換.根據無等待流水作業調度的解中任務距離的獨立性和式(1)，應用目標增量法［2］，對這3 種基本操作的性質進行分析.

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

式中，

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

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

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

證畢.

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

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

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

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

3 ISCH 算法

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

3.1 基本鄰域結構的最佳操作

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

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

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

3.2 初始解生成算法

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

3.3 移位局部優化算法

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

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

3.4 構造解算法

構造解算法(SGA)用于構造生成新的解.本文采用NEH 算法思想［11］，設計SGA 算法.其基本思想為:從初始解Q 中選取1 個未排序任務插入到當前解πC的最佳位置，采用MLO 算法對左、右2個子解πLC和πRC分別進行移位局部優化;重復上述過程直到Q 為空.

SGA 算法的具體描述如下:

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

3.5 迭代序對對換算法

針對SGA 算法生成的解，可應用序對對換算法進行優化［5］.根據對換方向和后續操作起點的不同，對換可分為FSC，BSC，FSR 和BSR 四種.不同對換算法對相同解的優化效果不相同，其中BSC 算法對解的優化效果最好［2］.另外，實驗發現，在一定的迭代次數內，BSC 算法能進一步優化解.因此，本文采用迭代序對對換算法優化解，結束條件為臨時解πS不能再優化或者迭代次數t 超過10.

IBSC 算法的具體描述如下:

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

3.6 ISCH 算法

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

①參數初始化;

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

③調用ISG 算法生成初始解;

④調用SGA 算法構造解;

⑤調用IBSC 算法改進解;

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

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

4 算法性能測試

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

所有算法都采用Java 語言實現，利用文獻［12］中的120 個Benchmark 實例進行測試，運行于Pentium 2.93 GHz，512 M 內存的PC 機上.

算法性能指標采用平均相對偏差，其計算公式為［2］

式中，N 表示具有相同規模的實例個數;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 算法的平均性能優于PH1(p)算法.當任務數n ＜100 時，ISCH 算法的性能比FNM 算法差，但明顯優于PH1(p)算法;當任務數n≥100時，ISCH 算法的性能最好，其平均ARPD 值小于PH1(p)算法和FNM 算法.因此，隨著任務數n的增大，ISCH 算法能在較短的時間內得到更好的解.盡管在某些小規模實例(如ta03 組和ta06 組)上，ISCH 算法的性能比GA-VNS 算法差，但其平均ARPD 值較GA-VNS 算法提高0.99%(在問題規模較大時，其目標函數值較大，故對解的優化效果很明顯)，其主要原因是GA-VNS 算法的運行時間被限定，搜索空間縮小，故解的性能必然下降.

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

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

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

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

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

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

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

4.3 任務數和機器數對算法的影響

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

表5 不同任務數下算法平均ARPD 值

表6 不同機器數下算法平均ARPD 值

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

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

5 結語

針對最小化總完工時間的無等待流水作業調度，本文提出了一種復合啟發式算法.首先，分析了2 個任務之間的距離，推導出基本鄰域結構操作的目標增量性質;然后，構造了基于插入-分段鄰域結構和優化方法，并提出了基于迭代對換的提高解方法.采用經典Benchmark 實例，將所提算法與目前經典的啟發式算法和最新元啟發式算法進行比較.結果表明，ISCH 算法在實時性和性能2 個方面均能兼顧，即在較短的時間內能得到較好的解，適合于實時大規模無等待流水作業調度系統.

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.