改進(jìn)布谷鳥(niǎo)搜索算法求解零空閑流水線調(diào)度問(wèn)題

彭勇 鄭慧君

摘? 要：本文針對(duì)零空閑流水線調(diào)度問(wèn)題，提出了一種基于自適應(yīng)步長(zhǎng)和發(fā)現(xiàn)概率的改進(jìn)布谷鳥(niǎo)搜索算法，建立了以工件的最大完工時(shí)間為目標(biāo)的算法模型。最后在若干Taillard Benchmark問(wèn)題上的仿真實(shí)驗(yàn)表明了改進(jìn)布谷鳥(niǎo)搜索算法解決零空閑流水線調(diào)度問(wèn)題的有效性。

關(guān)鍵詞：零空閑流水線調(diào)度;布谷鳥(niǎo)算法;最大完工時(shí)間;發(fā)現(xiàn)概率

中圖分類號(hào)：TP181;TP301.6? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2019）24-0020-03

Abstract：In this paper，an improved cuckoo search algorithm based on adaptive step size and discovery probability is proposed for no-idle flow shop scheduling，and an algorithm model aiming at the maximum completion time of makespan is established. Finally，simulation experiments on several Taillard Benchmark problems show the effectiveness of the improved cuckoo search algorithm in solving the no-idle flow shop scheduling problem.

Keywords：no-idle flow shop scheduling;cuckoo search;makespan;discovery probability

0? 引? 言

零空閑流水線調(diào)度（No-Idle Flow Shop，NIFS）問(wèn)題是一類典型的調(diào)度問(wèn)題，不但具有重要的理論價(jià)值，而且具有實(shí)際意義[1]。文獻(xiàn)[2]提出了解決該問(wèn)題的一種離散果蠅優(yōu)化算法，文獻(xiàn)[3]提出了一種解決NIFS問(wèn)題的粒子群優(yōu)化算法。

在基于群體智能的算法中，布谷鳥(niǎo)搜索算法（Cuckoo Search，CS）以較少參數(shù)和較好的魯棒性，成功用于多個(gè)領(lǐng)域[4，5]。因而，針對(duì)NIFS問(wèn)題，本文將會(huì)在CS的基礎(chǔ)上，對(duì)其步長(zhǎng)、發(fā)現(xiàn)概率進(jìn)行相應(yīng)的改進(jìn)，提出一種新的改進(jìn)布谷鳥(niǎo)搜索算法（Improved Cuckoo Search，ICS），以期能解決NIFS問(wèn)題。

1? 零空閑流水線調(diào)度問(wèn)題的數(shù)學(xué)模型

零空閑流水線調(diào)度問(wèn)題的一般描述為：n個(gè)工件{J1，J2，…，Jn}在m臺(tái)機(jī)器{M1，M2，…，Mm}上進(jìn)行流水加工，每個(gè)工件在機(jī)器上的加工順序相同，每臺(tái)機(jī)器加工的各工件的順序相同，同時(shí)約定每個(gè)工件在每臺(tái)機(jī)器上只加工一次，而在同一機(jī)器上加工的相鄰工件之間沒(méi)有等待時(shí)間，且機(jī)器之間存在無(wú)限緩沖區(qū)。ti，j為工件Ji在機(jī)器Mj上的加工時(shí)間;Ck，j為在機(jī)器Mj上加工的第k個(gè)工件的完工時(shí)間;R為工件排列形成的序列;并令決策變量為：

約束條件（3）和（4）保證了每個(gè)工件都會(huì)在排列R中出現(xiàn)且僅出現(xiàn)一次;約束條件（5）給出了第一個(gè)加工的工件在第一臺(tái)機(jī)器上的完成時(shí)間;約束條件（6）和（7）保證了同一臺(tái)機(jī)器上加工的相鄰兩工件和間的完工時(shí)間的關(guān)系，表明了同一時(shí)間在同一臺(tái)機(jī)器上只能加工一個(gè)工件，同時(shí)用等號(hào)連接保證了機(jī)器上相鄰兩工序間無(wú)時(shí)間間隔，即保證了機(jī)器的無(wú)間斷運(yùn)作。

由于零空閑流水線調(diào)度問(wèn)題的機(jī)器不允許空閑，其最大完成時(shí)間的算法將不同于置換流水線調(diào)度問(wèn)題的算法，研究中引入了一個(gè)中間變量——最早開(kāi)工時(shí)間來(lái)輔助計(jì)算各工件的最大完成時(shí)間。

最大完成時(shí)間的計(jì)算方法：

假設(shè)工件加工的順序?yàn)镽={R（1），R（2），…，R（n）}，tR（i），j表示R（i）位置上的工件在機(jī)器j上的工序作業(yè)時(shí)間，Ej，j+1為相鄰的機(jī)器j和j+1之間的開(kāi)工時(shí)間差，那么相鄰機(jī)器間的開(kāi)工時(shí)間差可按下列公式進(jìn)行計(jì)算：

工序R的最大完成時(shí)間的計(jì)算過(guò)程圖如圖1所示。

2? 改進(jìn)布谷鳥(niǎo)搜索算法解決NIFS問(wèn)題

2.1? 標(biāo)準(zhǔn)布谷鳥(niǎo)算法

布谷鳥(niǎo)搜索算法是一種模仿布谷鳥(niǎo)尋覓窩巢產(chǎn)蛋行為的啟發(fā)式智能優(yōu)化算法。標(biāo)準(zhǔn)布谷鳥(niǎo)算法主要思想是通過(guò)Lévy飛行路徑產(chǎn)生候選鳥(niǎo)窩以及采用精英保留策略更新當(dāng)前鳥(niǎo)窩位置，最終使鳥(niǎo)窩位置能夠達(dá)到或接近全局最優(yōu)解。根據(jù)文獻(xiàn)[6]，布谷鳥(niǎo)尋窩的路徑和位置更新公式如下：

在標(biāo)準(zhǔn)的多目標(biāo)布谷鳥(niǎo)算法中，Lévy飛行的步長(zhǎng)控制量?0為固定值，原種群經(jīng)連續(xù)跳躍，隨機(jī)游走后得到新種群，然后以發(fā)現(xiàn)概率pα放棄一些較差的個(gè)體并隨機(jī)生成新的解來(lái)補(bǔ)充到新種群，這樣不能保證算法在較低的迭代次數(shù)下的收斂性和尋優(yōu)精度。

2.2? 改進(jìn)布谷鳥(niǎo)搜索算法

由于布谷鳥(niǎo)是采用Lévy飛行模式在搜索空間隨機(jī)搜索的，其搜索步長(zhǎng)和方向都是高度隨機(jī)的，從一個(gè)區(qū)域跳躍到另一個(gè)區(qū)域也是隨機(jī)的，這種模式對(duì)早期的全局尋優(yōu)搜索無(wú)疑是有利的，可以較快接近全局最優(yōu)解，但隨著CS算法多次迭代后，后期全局最優(yōu)附近的局部尋優(yōu)會(huì)因Lévy飛行模式跳躍性較大，造成鳥(niǎo)巢附近的局部最優(yōu)信息得不到利用，因而后期收斂速度和精度反而弱化，為提高CS算法的收斂速度和精度，必須隨著算法的動(dòng)態(tài)變化而調(diào)整步長(zhǎng)因子和發(fā)現(xiàn)概率[7]。

其中，pi為第i代發(fā)現(xiàn)概率，pmin是最小發(fā)現(xiàn)概率，pmax是最大發(fā)現(xiàn)概率，iter是當(dāng)前代數(shù)、maxiter是最大代數(shù)，?i是第i代步長(zhǎng)因子，?min是最小步長(zhǎng)因子，?max是最長(zhǎng)步長(zhǎng)因子。

3? 仿真實(shí)驗(yàn)及結(jié)果分析

為了檢驗(yàn)改進(jìn)布谷鳥(niǎo)算法求解零空閑流水線問(wèn)題的效果，我們采用Taillard Benchmark中的不同規(guī)模的算例進(jìn)行了試驗(yàn)，采用文獻(xiàn)[8]提出的遺傳算法（GA）以及本文提出的標(biāo)準(zhǔn)布谷鳥(niǎo)算法（CS）和改進(jìn)布谷鳥(niǎo)算法（ICS）對(duì)每個(gè)算例仿真5次，計(jì)算平均相對(duì)偏差（PRD）和平均方差（SD）。

3.1? 實(shí)驗(yàn)環(huán)境

算法采用C++編程實(shí)現(xiàn)，測(cè)試的平臺(tái)為Windows 7，機(jī)器的主頻為3.60GHz，內(nèi)存為8GB。

3.2? 參數(shù)設(shè)置

設(shè)置種群的大小為30，pmin=0.005，pmax=1，iter是當(dāng)前代數(shù)、maxiter=200，?min=0.05，?max=0.5。

3.3? 結(jié)果分析

3.3.1? 平均偏差和平均均方差分析

不同算法計(jì)算結(jié)果如表1所示，從表1可以看出：

（1）CS算法所得的平均偏差和平均均方差略小于GA算法，表明CS算法在解的質(zhì)量上優(yōu)于GA算法;

（2）ICS算法所得的平均偏差和平均均方差小于CS算法，表明本文采取的提高算法性能的措施是有效的。

3.3.2? 最大完工時(shí)間分析

不同算法最大完工時(shí)間如表2所示，從表2中可清晰看出，ICS算法得到的不同規(guī)模算例的最大完工時(shí)間均優(yōu)于CS算法。在最好情況下，ICS算法性能可提高7.73%，其平均最大完工時(shí)間提高了6.88%，說(shuō)明ICS算法優(yōu)于CS算法，我們提出的改進(jìn)是有效的。

4? 結(jié)? 論

本文提出了一種改進(jìn)布谷鳥(niǎo)算法，該算法采用自適應(yīng)的步長(zhǎng)因子和發(fā)現(xiàn)概率，并運(yùn)用此算法于零空閑流水線調(diào)度問(wèn)題中。仿真實(shí)驗(yàn)表明，該算法有助于改善解的質(zhì)量和提高收斂速度，對(duì)解決流水線車間調(diào)度及自動(dòng)化工程等問(wèn)題具有較高的實(shí)用價(jià)值。

參考文獻(xiàn)：

[1] 齊學(xué)梅，王宏濤，楊潔，等.量子螢火蟲(chóng)算法及在無(wú)等待流水調(diào)度上的應(yīng)用 [J].信息與控制，2016，45（2）：211-217.

[2] 張其亮，俞祚明.基于優(yōu)勢(shì)種群的離散果蠅優(yōu)化算法求解無(wú)等待流水車間調(diào)度問(wèn)題 [J].計(jì)算機(jī)集成制造系統(tǒng)，2017，23（3）：609-615.

[3] 張其亮，陳永生.求解雙向無(wú)等待混合流水車間調(diào)度問(wèn)題的粒子群優(yōu)化算法 [J].計(jì)算機(jī)集成制造系統(tǒng)，2013，19（10）：2503-2509.

[4] YANG X S，DEB S.Cuckoo search via levy flights [C]//Proceedings of the World Congress on Nature & Biologically Inspired Computing，IEEE Publications，USA，2009：210-214.

[5] 黃辰，費(fèi)繼友，王麗穎，等.基于多策略差分布谷鳥(niǎo)算法的粒子濾波方法 [J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2018，49（4）：265-272.

[6] 董崇杰，劉毅，彭勇.改進(jìn)布谷鳥(niǎo)算法在人群疏散多目標(biāo)優(yōu)化中的應(yīng)用 [J].系統(tǒng)仿真學(xué)報(bào)，2016，28（5）：1063-1069.

[7] LI R Y，DAI R W.Adaptive Step-size Cuckoo Search Algorithm [J]. Computer Science，2017，44（5）：235-240.

[8] 劉勝軍.混合流水線多目標(biāo)調(diào)度優(yōu)化研究 [D].淄博：山東理工大學(xué)，2016.

作者簡(jiǎn)介：彭勇（1976-），男，漢族，湖北黃岡人，碩士，副教授，研究方向：網(wǎng)絡(luò)安全，智能計(jì)算;鄭慧君（1985-），男，漢族，湖北孝感人，碩士，講師，研究方向：控制理論及計(jì)算機(jī)應(yīng)用。