基于改進(jìn)的布谷鳥算法求解流水車間調(diào)度問題

高楊 云曉燕

摘 ?要：針對基本的布谷鳥算法在求解流水車間調(diào)度問題時(shí)存在搜索能力差、收斂速度慢的缺點(diǎn)，提出了一種高斯擾動(dòng)的布谷鳥搜索算法（GCS）。該算法不僅增加了鳥窩移動(dòng)的活力，還改善了搜索能力差的情況。仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)的布谷鳥算法在求解流水車間調(diào)度問題上具有良好的優(yōu)化性能，要優(yōu)于基本的布谷鳥算法。

關(guān)鍵詞：流水車間調(diào)度問題;高斯擾動(dòng);搜索速度

中圖分類號(hào)：TP18;TB497 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2019）13-0018-03

Solving Flow Shop Scheduling Problem Based on Improved Cuckoo Algorithms

GAO Yang，YUN Xiaoyan

（School of Software，Liaoning University of Science and Technology，Anshan ?114051，China）

Abstract：Aiming at the shortcomings of the basic cuckoo algorithm in solving flow shop scheduling problems，such as poor search ability and slow convergence speed，a new cuckoo search algorithm based on Gauss perturbation （GCS） is proposed. This algorithm not only increases the vitality of birds nest movement，but also improves the poor search ability. The simulation results show that the improved cuckoo algorithm has good optimization performance in solving flow shop scheduling problems，and is superior to the basic cuckoo algorithm.

Keywords：flow shop scheduling problem;Gauss perturbation;search speed

0 ?引 ?言

隨著世界各地的經(jīng)濟(jì)與技術(shù)的發(fā)展，城市整體規(guī)模不斷擴(kuò)大，我國成為制造業(yè)大國，產(chǎn)品需求量非常大。因此流水車間調(diào)度問題（Flow Shop Scheduling Problem，簡稱為FSSP）在先進(jìn)制造業(yè)中受到了廣泛的關(guān)注。

流水車間調(diào)度問題在車間生產(chǎn)中是極其常見的問題，也一直被認(rèn)為是NP-hard問題。在求解流水車間調(diào)度問題上不但有通過啟發(fā)式來解決的，另外還有通過仿生智能優(yōu)化方式或群智能算法來解決的。上世紀(jì)70年代—90年代，蟻群算法、禁忌算法、遺傳算法、粒子群算法、分布估計(jì)算法、螢火蟲算法、貪婪算法[1-8]等一些智能優(yōu)化算法逐漸被科學(xué)家提出并在實(shí)際的工程領(lǐng)域內(nèi)取得了很大的成功。

本文針對流水車間調(diào)度的問題，提出了一種改進(jìn)的布谷鳥算法。該算法與高斯擾動(dòng)相結(jié)合，進(jìn)而提高了搜索性能，實(shí)驗(yàn)結(jié)果表明該算法與基本的布谷鳥算法相比，在求解流水車間調(diào)度問題上得到了很好的改良。

1 ?FSSP問題的數(shù)學(xué)模型

流水車間調(diào)度問題是一個(gè)加工資源分配的問題，它主要是在滿足某些加工機(jī)器、完工時(shí)間、資源配置等約束條件下，對車間的任務(wù)進(jìn)行最佳分配。在滿足一定的約束條件下，流水車間調(diào)度問題可描述為：一個(gè)加工系統(tǒng)中有n個(gè)工件要在m臺(tái)機(jī)器上加工，每個(gè)工件包含a道工序，工件的加工順序是一定的，每道工序在不同機(jī)器上加工。假設(shè)工件i在機(jī)器x上的加工時(shí)間確定，設(shè)加工的時(shí)間為tj（i=1，2，…，n;j=1，2，…，n）。該問題的主要目的是n個(gè)工件在每臺(tái)機(jī)器上的加工順序一定時(shí)，使得最小化最大完工時(shí)間[9]。在上一個(gè)假設(shè)成立的前提下，流水車間還可描述為：

（1）每個(gè)工件在每臺(tái)加工機(jī)器上的加工順序一定;

（2）每個(gè)工件在同一時(shí)間時(shí)只能在一臺(tái)機(jī)器上加工;

（3）每臺(tái)機(jī)器在同一時(shí)間時(shí)只能加工一個(gè)工件;

（4）工件工序的就緒時(shí)間與順序無關(guān)，且包含在總加工時(shí)間內(nèi)。

令C（ji，k）代表工件ji在機(jī)器k上完成工作時(shí)所用的時(shí)間，每個(gè)工件工作的順序?yàn)椋╦1，j2，…，jm），則n個(gè)工件在m臺(tái)機(jī)器上完成工作時(shí)所用的時(shí)間為：

2 ?基本布谷鳥算法

布谷鳥搜索（Cuckoo Search，CS）算法是由Xin-She Yang和Suash Deb開發(fā)的一種新型元啟發(fā)式搜索算法，是模擬布谷鳥繁衍后代所提出一種新型群智能優(yōu)化算法[11]。布谷鳥的繁殖策略就是找到和它們能產(chǎn)出相似的卵的鳥巢并將它們的蛋放入這個(gè)鳥巢里，同時(shí)避免這個(gè)鳥發(fā)現(xiàn)，它們也會(huì)移走寄主巢中的一個(gè)或多個(gè)蛋，保持鳥巢內(nèi)的蛋數(shù)目不變，這樣增加了自己蛋的孵化概率。如果寄主發(fā)現(xiàn)了該行為，寄主就會(huì)扔出外來蛋或是尋找新地方來搭建自己的鳥窩。CS算法就是通過模擬布谷鳥尋找適合孵化自己下一代鳥巢的方式來尋找最優(yōu)值。為了模擬布谷鳥的繁衍機(jī)制，Yang等在文獻(xiàn)中設(shè)定了3種理想狀態(tài)[11]：

（1）每只布谷鳥一次只產(chǎn)一枚卵，并隨機(jī)找到一個(gè)鳥窩來孵化;

（2）在隨機(jī)選擇的這些窩的過程當(dāng)中，選擇最好的鳥窩將會(huì)保存到下一代;

（3）選擇的鳥窩數(shù)量n是一定的，設(shè)寄主發(fā)現(xiàn)外來卵的概率是Pa，Pa∈[0，1]，倘若寄主發(fā)現(xiàn)了鳥窩中有外來的蛋，它們就會(huì)放棄自己現(xiàn)有的鳥窩另尋地方搭建自己新窩。

在上文的三個(gè)理想狀態(tài)基礎(chǔ)上，參考布谷鳥孵化鳥蛋的過程，布谷鳥尋巢的位置更新公式如下：

其中a為步長的大小，并且一般情況下a=1。⊕為點(diǎn)對點(diǎn)乘法。Levy（λ）是隨機(jī)搜索的路徑，并且a服從Levy分布。Levy（λ）～u=t-λ，（1<λ≤3）。xi（t）代表第t代鳥窩在第i個(gè)鳥窩的位置。隨機(jī)產(chǎn)生一個(gè)數(shù)Ra，Ra與Pa進(jìn)行數(shù)值比較，若Ra>Pa，則對xi（t+1）進(jìn)行隨機(jī)改變鳥巢位置，獲得一組新的鳥巢。否則不變。比較出新鳥窩位置與當(dāng)前鳥窩位置哪個(gè)是最優(yōu)解，并保留這個(gè)最優(yōu)解。

3 ?求解流水車間的GCS算法思想

GCS算法是在CS算法的基礎(chǔ)上加了個(gè)高斯擾動(dòng)，更加快速地找到了更優(yōu)的鳥窩位置。若CS算法在第t次循環(huán)時(shí)找到了一組較優(yōu)的鳥窩的位置為：xi（t）i=1，2，…，n。而這個(gè)GCS算法就是在CS算法執(zhí)行第t次循環(huán)時(shí)加入高斯擾動(dòng)，不讓它執(zhí)行下一次循環(huán)，而是進(jìn)一步搜尋。設(shè)矩陣Pt=[x1（t），x2（t），x3（t），…，xn（t）]T，令Pt為m*n階矩陣。則GCS為Pt′=Pt+a⊕β。其中β為m*n階矩陣，⊕為點(diǎn)對點(diǎn)乘法，因?yàn)棣碌娜≈捣秶容^大，所以設(shè)a=1/4來控制β的取值范圍，進(jìn)而適當(dāng)?shù)卦龃罅锁B窩移動(dòng)的活力，經(jīng)過高斯擾動(dòng)得到了一個(gè)Pt′，讓它與Pt進(jìn)行比較，得到更優(yōu)的位置，再繼續(xù)進(jìn)行GCS算法，得到下一個(gè)更優(yōu)的位置Pt″。

4 ?GCS算法具體實(shí)施步驟

Step1：初始化參數(shù)，隨機(jī)產(chǎn)生宿主鳥窩的個(gè)數(shù)為n，外來蛋發(fā)現(xiàn)的概率為Pa，寄生鳥窩的維度為m，初始化鳥窩的位置。

Step2：依照測試函數(shù)計(jì)算出當(dāng)前最優(yōu)鳥窩的位置Xj（0）j ∈{1，2，…，n}和最優(yōu)值Fmin。

Step3：保留上一代最優(yōu)鳥窩的位置，并操作Step2對剩余鳥窩的位置進(jìn)行更新，獲得最新的一組鳥窩位置，并對這組鳥窩進(jìn)行測試，將最優(yōu)鳥窩位置與上一代鳥窩位置進(jìn)行比較，得出一組最優(yōu)的位置來替代之前的鳥窩位置，令最新的一組鳥窩位置為Kt=[x1（t），x2（t），x3（t），…，xn（t）]T。

Step4：在最新的一組鳥窩位置中，用服從隨機(jī)分布的r∈[0，1]與Pa進(jìn)行比較。若r>Pa，則保留Kt中發(fā)現(xiàn)幾率最小的鳥窩位置，并對剩余鳥窩的位置進(jìn)行隨機(jī)改變，獲得一組新的鳥窩位置Pt。

Step5：對Pt加入高斯擾動(dòng)，又得到一組鳥窩的位置Pt′，與Pt進(jìn)行比較得出最優(yōu)的一組鳥窩位置，讓測試值中最好的替換之前的鳥窩位置，令現(xiàn)在最優(yōu)的一組鳥窩位置為Pt″，并將Pt″賦值給Pt，以便更好地進(jìn)入下一次循環(huán)。

Step6：對Pt連續(xù)執(zhí)行Step4的步驟，在Pt中找到最優(yōu)的鳥窩位置和最優(yōu)解為Fmin，并且判斷Fmin是否達(dá)到了算法的終止條件，倘若達(dá)到，則輸出最優(yōu)位置和最優(yōu)值，不然連續(xù)執(zhí)行這個(gè)Step3。

5 ?仿真實(shí)例

為了進(jìn)一步測試GCS算法的搜索性能，本文中選用了Benchmarks測試函數(shù)集中的Sphere函數(shù)、Rastrigin函數(shù)進(jìn)行測試，用于測試GCS算法的函數(shù)參數(shù)如表1所示。首先設(shè)鳥窩數(shù)量n=20，維度為10，并且最大迭代次數(shù)為4000，若迭代次數(shù)大于4000認(rèn)為尋優(yōu)失敗。測試函數(shù)如下：

6 ?結(jié) ?論

本文的目的是最小化最大完成時(shí)間，在基本布谷鳥算法迭代的過程當(dāng)中對更新后的鳥窩位置加入高斯擾動(dòng)，擴(kuò)大了搜索范圍，增加了鳥窩位置變化的多樣性。與基本布谷鳥算法尋優(yōu)結(jié)果比較，得出改良后的布谷鳥算法搜索性能更好，證明了該算法在求解流水車間調(diào)度的問題中是有效的。

參考文獻(xiàn)：

[1] 劉延風(fēng)，劉三陽.多構(gòu)造蟻群優(yōu)化求解置換流水車間調(diào)度問題 [J].計(jì)算機(jī)科學(xué)，2010，37（1）：222-224.

[2] 屈國強(qiáng)，周永良.蟻群優(yōu)化結(jié)合變鄰域搜索求解NWFS調(diào)度問題 [J].計(jì)算機(jī)工程與應(yīng)用，2012，48（16）：216-219+248.

[3] 張建萍，張武貞.基于改進(jìn)的禁忌搜索算法求解車間作業(yè)調(diào)度問題 [J].信息技術(shù)與信息化，2011（3）：77-80.

[4] 姚嫣菲.基于改進(jìn)遺傳算法的車間作業(yè)調(diào)度問題研究 [D].杭州：浙江大學(xué)，2011.

[5] 王凌，劉波.微粒群優(yōu)化與調(diào)度算法 [M].北京：清華大學(xué)出版社，2008：114-137.

[6] 王軒，李元香.分布估計(jì)算法在車間調(diào)度問題中的應(yīng)用研究 [D].青島：中國石油大學(xué)（華東），2012.

[7] 李永林，葉春明.基于螢火蟲算法的零等待流水線調(diào)度優(yōu)化 [J].機(jī)械設(shè)計(jì)與研究.2013，29（6）：50-54.

[8] Pan Q K，Wang L，Zhao B H . An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion [J].The International Journal of Advanced Manufacturing Technology，2008，38（7-8）：778-786.

[9] 肖輝輝，段艷明.基于差分進(jìn)化的布谷鳥搜索算法 [J].計(jì)算機(jī)應(yīng)用，2014，34（6）：1631-1635+1640.

[10] Yang X S，Deb S . Cuckoo Search via Levy Flights [J].Mathematics，2010：210-214.

作者簡介：高楊（1997-），女，漢族，遼寧朝陽人，本科在讀，研究方向：軟件工程。