高楊 云曉燕

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

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

中圖分類號：TP18;TB497 ? ? 文獻標識碼：A 文章編號：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)濟與技術(shù)的發(fā)展，城市整體規(guī)模不斷擴大，我國成為制造業(yè)大國，產(chǎn)品需求量非常大。因此流水車間調(diào)度問題（Flow Shop Scheduling Problem，簡稱為FSSP）在先進制造業(yè)中受到了廣泛的關(guān)注。

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

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

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

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

（1）每個工件在每臺加工機器上的加工順序一定;

（2）每個工件在同一時間時只能在一臺機器上加工;

（3）每臺機器在同一時間時只能加工一個工件;

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

令C（ji，k）代表工件ji在機器k上完成工作時所用的時間，每個工件工作的順序為（j1，j2，…，jm），則n個工件在m臺機器上完成工作時所用的時間為：

2 ?基本布谷鳥算法

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

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

（2）在隨機選擇的這些窩的過程當中，選擇最好的鳥窩將會保存到下一代;

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

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

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

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

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

4 ?GCS算法具體實施步驟

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

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

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

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

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

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

5 ?仿真實例

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

6 ?結(jié) ?論

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

參考文獻：

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

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

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

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

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

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

[7] 李永林，葉春明.基于螢火蟲算法的零等待流水線調(diào)度優(yōu)化 [J].機械設(shè)計與研究.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].計算機應(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-），女，漢族，遼寧朝陽人，本科在讀，研究方向：軟件工程。