彭勇 鄭慧君

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

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

中圖分類號：TP181;TP301.6? ? ? 文獻標識碼：A 文章編號：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）問題是一類典型的調(diào)度問題，不但具有重要的理論價值，而且具有實際意義[1]。文獻[2]提出了解決該問題的一種離散果蠅優(yōu)化算法，文獻[3]提出了一種解決NIFS問題的粒子群優(yōu)化算法。

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

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

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

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

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

最大完成時間的計算方法：

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

工序R的最大完成時間的計算過程圖如圖1所示。

2? 改進布谷鳥搜索算法解決NIFS問題

2.1? 標準布谷鳥算法

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

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

2.2? 改進布谷鳥搜索算法

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

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

3? 仿真實驗及結(jié)果分析

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

3.1? 實驗環(huán)境

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

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

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

3.3? 結(jié)果分析

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

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

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

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

3.3.2? 最大完工時間分析

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

4? 結(jié)? 論

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

參考文獻：

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

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

[3] 張其亮，陳永生.求解雙向無等待混合流水車間調(diào)度問題的粒子群優(yōu)化算法 [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] 黃辰，費繼友，王麗穎，等.基于多策略差分布谷鳥算法的粒子濾波方法 [J].農(nóng)業(yè)機械學報，2018，49（4）：265-272.

[6] 董崇杰，劉毅，彭勇.改進布谷鳥算法在人群疏散多目標優(yōu)化中的應用 [J].系統(tǒng)仿真學報，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] 劉勝軍.混合流水線多目標調(diào)度優(yōu)化研究 [D].淄博：山東理工大學，2016.

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