求解作業(yè)車間調(diào)度問題的變鄰域動態(tài)煙花算法

錢 曉 雯

(蘇州衛(wèi)生職業(yè)技術(shù)學院 基礎部，江蘇 蘇州 215006； 蘇州大學 計算機科學與技術(shù)學院，江蘇 蘇州 215006)

0　引　言

作業(yè)車間調(diào)度問題(Job-Shop Scheduling Problem, JSP)具有不確定性、復雜性、多約束條件以及多資源相互協(xié)調(diào)等特點[1]，一直是機械加工制造、網(wǎng)絡通信、集成電路設計等諸多研究領域的數(shù)學難題[2]。如何在滿足多種約束條件的前提下，達到所需性能指標最優(yōu)，具有重要的理論意義和實際價值。

國內(nèi)外學者針對JSP問題的求解提出了許多行之有效的方法[3]。這些方法大致可分為精確計算、構(gòu)造式啟發(fā)算法和智能優(yōu)化算法。其中，智能優(yōu)化算法作為一種具有全局優(yōu)化性能、通用性強、且適合解決大規(guī)模問題的并行算法[4],近年來已成為解決JSP問題最為常見的方法。Heinonen等[5]提出采用蟻群算法和后處理階段的混合算法求解最小化完成時間的JSP問題，但是該算法容易陷入局部最優(yōu)，且計算復雜性較大。Chen等[6]提出利用基于改進的遺傳算法求解JSP問題，該算法在遺傳算法的基礎之上改進變異操作，引入交叉點數(shù)量的判斷條件，能在一定程度上提高算法性能，但是改進后的算法復雜難以理解，且計算時間開銷較大。楊小東等[7]提出一種結(jié)合帝國主義競爭算法和禁忌搜索算法的混合算法用于求解最小化最大完成時間的JSP問題，該算法能較好地兼顧全局最優(yōu)與局部最優(yōu)，但是算法收斂速度慢。姚遠遠等[8]提出布谷鳥算法求解JSP問題，但是該算法有效性不高，且魯棒性較差。煙花算法(Fireworks Algorithm, FWA)[9]作為智能優(yōu)化算法家族新成員，一經(jīng)提出便因其結(jié)構(gòu)簡單、性能優(yōu)越而受到廣泛關注[10-12]。但是，F(xiàn)WA并未考慮不同個體之間的相互聯(lián)系，使得算法容易陷入局部最優(yōu)。

本文提出一種基于變鄰域搜索的動態(tài)煙花算法(Dynamic Fireworks Algorithm base on Variable Neighborhood Search, DFWA-VNS)，并用于求解JSP問題。DFWA-VNS在FWA的基礎之上，引入變鄰域搜索方法，在多種鄰域結(jié)構(gòu)下按貢獻選擇不同的搜索方式，同時，對每次進化中，根據(jù)算法進化速度動態(tài)確定每次更新維數(shù)，以此提高JSP問題求解精度，并避免算法陷入早熟問題。

1　JSP的數(shù)學模型

JSD可描述為：給定m臺機器，n個作業(yè)，每個作業(yè)按指定的順序在m臺機器上依次進行，但必須滿足約束條件：① 預先設置每個工序的加工時間和加工機器；② 每個工序有且只能在1臺機器上加工1次；③ 不同作業(yè)之間無前后約束關系；④ 每道工序不能中斷；⑤ 每臺機器不能同時加工多個作業(yè)；⑥ 完工時間只考慮加工所需時間，不考慮開始前的布置時間和工序間的交接時間。

綜上，可將JSP問題轉(zhuǎn)換成數(shù)學模型。設工件j在機器k上的執(zhí)行時間為pj,k，工件j的第i個操作在機器k上的執(zhí)行完成時間為t(ji,k)，所有工件的排序為r(j1,j2,…,jn)，R為所有排序的集合。由于同一機器不能同時加工多個工件，所以機器k必須在執(zhí)行完操作ji-1之后才能進行操作ji，與此同時，操作ji必須完成上一機器k-1的操作，數(shù)學表達式為：

(1)

i=2,3,…,n；k=2,3,…,m

則所有工件的最大完工時間為：

tmax(r)=t(jn,m)

(2)

因此，最小化最大完工時間即為：

minf=min[tmax(r)]?r∈R

(3)

2　煙花算法

在FWA中，每個煙花均視為一個可行解，煙花爆炸產(chǎn)生火花的過程被視為其鄰域搜索過程，但是，每個煙花的爆炸半徑和爆炸產(chǎn)生的火花數(shù)均不同。適應度值差的煙花爆炸半徑較大，具有全局搜索能力；反之，適應值好的煙花爆炸半徑較小，具有局部搜索能力。在整個搜索過程中，煙花之間通過資源分配和信息交互推動算法尋優(yōu)過程，最終得到最優(yōu)解。

3　DFWA-VNS算法

3.1　變鄰域搜索

變鄰域搜索[13](Variable Neighborhood Search, VNS)是一種重要的元啟發(fā)式搜索算法，已廣泛應用于多個領域。VNS通過搜索狀態(tài)在給定的鄰域結(jié)構(gòu)集合中系統(tǒng)地變化鄰域結(jié)構(gòu)來拓展搜索范圍，從而提高算法的全局尋優(yōu)能力。本文引入3種領域結(jié)構(gòu)：① 交換。隨機交換工序執(zhí)行順序中的兩個不同工件的位置。② 插入。將隨機選擇的某一工件插入到工序中的一個隨機位置。③ 逆序。隨機選擇一段序列間的工件，并將工件逆序。通過該3種方式改變鄰域結(jié)構(gòu)，可有效避免JSP問題求解過程中陷入局部最優(yōu)困境。

3.2　DFWA-VNS算法

3.2.1動態(tài)煙花算法

每個煙花爆炸以后產(chǎn)生的火花總數(shù)為：

(4)

式中：i(i=1,2,…,n)表示煙花序號；ymax表示所有煙花對應的目標函數(shù)的最大值，ymax=max(f(xi))(i=1,2,…,n)；ξ表示一個極小量，防止式中出現(xiàn)除零錯誤；l表示所有煙花爆炸產(chǎn)生的火花總數(shù)。

煙花i(i=1,2,…,n)的爆炸半徑為：

(5)

式中：ymin表示所有煙花對應的目標函數(shù)的最小值，且ymin=min(f(xi))(i=1,2,…,n)；Amax表示最大爆炸半徑。

在進化過程中，多樣性是保證算法搜索范圍達到全局最優(yōu)的重要性能。為避免算法性能優(yōu)秀的個體對子代影響過大，導致種群多樣性減弱甚至喪失，需對煙花總數(shù)si進行約束：

(6)

(7)

(8)

通過式(7)或式(8)產(chǎn)生新的位置如果超出了搜索范圍，則需要采用映射規(guī)則使其返回搜索空間內(nèi)。映射規(guī)則如下式：

(9)

但是，在進行位置更新時，需要更新的維度z難以確定。如果z過大，將使得群體多樣性減弱，容易陷入局部最優(yōu)；反之，如果z過小，將減慢優(yōu)化速度，較低算法收斂能力。因此，本文引入動態(tài)更新策略。

定義煙花種群的進化速度為v，在第t次迭代計算時，將前t-1次迭代計算中的最優(yōu)值進行線性擬合，得到擬合函數(shù)：

(10)

通過進化速度v進而確定需更新維度z的大小

(11)

式中：μ,λ∈(0,1)為調(diào)整因子；v0為速度閾值，需初始時刻設定。通過z的動態(tài)調(diào)整，加快算法收斂速度，同時增強全局尋優(yōu)能力。

3.2.2DFWA-VNS算法步驟

(1) 初始化相關參數(shù)，生產(chǎn)n個初始煙花。

(2)n個煙花發(fā)生爆炸，計算每個煙花的爆炸半徑和火花個數(shù)。

(3) 根據(jù)爆炸半徑和火花個數(shù)生產(chǎn)爆炸火花和高斯變異火花。

(4) 計算進化速度并根據(jù)進化速度動態(tài)調(diào)整更新維度z。

(5) 根據(jù)鄰域變化規(guī)則調(diào)整搜索鄰域。

(6) 選擇下一次迭代計算的父代煙花。

(7) 判斷是否滿足終止條件。若滿足則輸出最優(yōu)值，并停止計算；否則返回第(2)步，進入下一次迭代計算。

4　實驗驗證

為驗證DFWA-VNS算法的有效性，選取兩類經(jīng)典的JSP算例[14]：FT類，包括FT06、FT10和FT20；LA類，包括LA05、LA25和LA40。共6種典型問題作為測試算例。并與粒子群算法[15]、遺傳算法、FWA算法[9]進行對比試驗。4種算法種群規(guī)模均為30，迭代計算100次，對每一個算例獨立計算20次，取平均值作比較。計算結(jié)果見表1，其中：C*表示理論最優(yōu)解；Aavg表示計算所得平均值；tavg表示平均收斂時間。

由表1可知，本文所提算法DFWA-VNS能計算得到理想結(jié)果，同時在每一個算例計算時，均能快速收斂。在求解輕量級問題時，F(xiàn)WA性能同樣較優(yōu)，但是，針對大規(guī)模問題的求解時，計算結(jié)果并不太理想，容易早熟，領域并未充分搜索。DFWA-VNS算法具有很好的搜索質(zhì)量，在多次計算過程中均能接近理論最優(yōu)值，表明該算法魯棒性較好。DFWA-VNS引入動態(tài)調(diào)整策略，使得算法可以根據(jù)進化狀態(tài)調(diào)整需更新維度，加快收斂速度，同時動態(tài)調(diào)整策略的引入也是算法具有較優(yōu)全局尋優(yōu)能力的重要原因之一。

表1　計算結(jié)果

5　結(jié)　語

本文提出了一種求解JSP問題的變鄰域動態(tài)煙花算法，該算法通過變鄰域搜索改進煙花算法的搜索方式，加強每一次迭代計算過程中個體之間的相互聯(lián)系與相互學習，增強了算法的全局尋優(yōu)能力。同時，引入進化速度概念，并利用進化速度動態(tài)調(diào)整每一次迭代計算需要更新的維度，避免算法陷入局部最優(yōu)，同時加快算法收斂速度。通過對6個經(jīng)典算例的求解，驗證了DFWA-VNS算法的有效性。

參考文獻(References)：

[1]Jain A S, Meeran S. Deterministic job-shop scheduling: Past, present and future[J]. European Journal of Operational Research, 1999, 113(2):390-434.

[2]Tan C J, Neoh S C, Lim C P,etal. Application of an evolutionary algorithm-based ensemble model to job-shop scheduling[J]. Journal of Intelligent Manufacturing, 2017，27:1-12.

[3]趙詩奎, 王林瑞, 石飛. 作業(yè)車間調(diào)度問題綜述[J]. 濟南大學學報(自然科學版), 2016(1):74-80.

[4]Kim H C, Boo C J. Intelligent optimization algorithm approach to image reconstruction in electrical impedance tomography[C]//Advances in Natural Computation. Springer Berlin Heidelberg, 2006:856-859.

[5]Heinonen J, Pettersson F. Hybrid ant colony optimization and visibility studies applied to a job-shop scheduling problem[J]. Applied Mathematics & Computation, 2007, 187(2): 989-998.

[6]Chen M, Li J L. Genetic algorithm combined with gradient information for flexible job-shop scheduling problem with different varieties and small batches[C]//MATEC Web of Conferences. EDP Sciences, 2017, 95: 10001.

[7]楊小東, 康雁, 柳青,等. 求解作業(yè)車間調(diào)度問題的混合帝國主義競爭算法[J]. 計算機應用, 2017, 7(2):517-522.

[8]姚遠遠, 葉春明. 作業(yè)車間調(diào)度問題的布谷鳥搜索算法求解[J]. 計算機工程與應用, 2015, 51(5):255-260.

[9]Tan Y, Zhu Y. Fireworks algorithm for optimization[C]// International Conference on Advances in Swarm Intelligence. Springer-Verlag, 2010:355-364.

[10]Gao H, Diao M. Cultural firework algorithm and its application for digital filters design[J]. International Journal of Modelling, Identification and Control, 2011, 14(4): 324-331.

[11]Rahmani A, Amine A, Hamou R M,etal. Privacy preserving through fireworks algorithm based model for image perturbation in big data[J]. International Journal of Swarm Intelligence Research (IJSIR), 2015, 6(3): 41-58.

[12]朱曉東, 劉沖, 郭雅默. 基于煙花算法與差分進化算法的模糊分類系統(tǒng)設計[J]. 鄭州大學學報(工學版), 2015, 36(6):47-51.

[14]王成龍, 李誠, 馮毅萍,等. 作業(yè)車間調(diào)度規(guī)則的挖掘方法研究[J]. 浙江大學學報(工學版), 2015, 49(3):421-429.

[15]Kennedy J, Eberhart R. Particle swarm optimization[C]// IEEE International Conference on Neural Networks, 1995. Proceedings. IEEE Xplore, 1995:1942-1948.