錢 曉 雯

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

0　引　言

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

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

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

1　JSP的數(shù)學(xué)模型

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

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

(1)

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

則所有工件的最大完工時(shí)間為：

tmax(r)=t(jn,m)

(2)

因此，最小化最大完工時(shí)間即為：

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

(3)

2　煙花算法

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

3　DFWA-VNS算法

3.1　變鄰域搜索

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

3.2　DFWA-VNS算法

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

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

(4)

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

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

(5)

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

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

(6)

(7)

(8)

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

(9)

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

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

(10)

通過(guò)進(jìn)化速度v進(jìn)而確定需更新維度z的大小

(11)

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

3.2.2DFWA-VNS算法步驟

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

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

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

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

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

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

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

4　實(shí)驗(yàn)驗(yàn)證

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

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

表1　計(jì)算結(jié)果

5　結(jié)　語(yǔ)

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

參考文獻(xiàn)(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]趙詩(shī)奎, 王林瑞, 石飛. 作業(yè)車間調(diào)度問(wèn)題綜述[J]. 濟(jì)南大學(xué)學(xué)報(bào)(自然科學(xué)版), 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)度問(wèn)題的混合帝國(guó)主義競(jìng)爭(zhēng)算法[J]. 計(jì)算機(jī)應(yīng)用, 2017, 7(2):517-522.

[8]姚遠(yuǎn)遠(yuǎn), 葉春明. 作業(yè)車間調(diào)度問(wèn)題的布谷鳥(niǎo)搜索算法求解[J]. 計(jì)算機(jī)工程與應(yīng)用, 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]朱曉東, 劉沖, 郭雅默. 基于煙花算法與差分進(jìn)化算法的模糊分類系統(tǒng)設(shè)計(jì)[J]. 鄭州大學(xué)學(xué)報(bào)(工學(xué)版), 2015, 36(6):47-51.

[14]王成龍, 李誠(chéng), 馮毅萍,等. 作業(yè)車間調(diào)度規(guī)則的挖掘方法研究[J]. 浙江大學(xué)學(xué)報(bào)(工學(xué)版), 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.