基于布谷鳥搜索算法求解流水車間調度

張珊靚+王慶喜

摘要：調度是研究資源如何配置問題的理論，流水車間問題是車間調度問題領域的一個子問題，是通過對制造過程作業計劃，以實現流水車間環境下生產過程的優化調度，其廣泛應用于實際生產，尤其適用于單件大批量生產背景的制造企業。該文主要研究的是使用布谷鳥搜索算法優化車間調度中的流水車間調度的問題。

關鍵詞：布谷鳥搜索算法；流程車間；調度

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）35-0104-02

流水車間調度問題是一個經典的理論問題，擁有簡潔的形式，廣泛的關聯性和高度的計算復雜度。該問題的簡潔性體現在，任務集合上的一個排列就代表了一個調度序列。而關聯性和復雜性體現在，該問題代表了一大類具有排列性質的問題，許多組合優化問題都可以歸約到它。在計算理論中，它是NP-難的。

1 布谷鳥搜索算法

布谷鳥搜索算法自從2009年問世以來廣泛醫用于多個領域，已經成功優化多種問題，其搜索能力和優化能力被大量證明，該算法的思想可以從如下代碼解釋。

for i=1：n，

nest（i，：）=Lb+（Ub-Lb）.*rand（size（Lb））；

end

fitness=10^10*ones（n，1）；

[fmin，bestnest，nest，fitness]=get_best_nest（nest，nest，fitness）；

N_iter=0；

while （fmin>Tol），

new_nest=get_cuckoos（nest，bestnest，Lb，Ub）；

[fnew，best，nest，fitness]=get_best_nest（nest，new_nest，fitness）； N_iter=N_iter+n；

new_nest=empty_nests（nest，Lb，Ub，pa） ；

[fnew，best，nest，fitness]=get_best_nest（nest，new_nest，fitness）； N_iter=N_iter+n；

if fnew

fmin=fnew；

bestnest=best；

end

end

2 流水車間問題求解

流水車間調度問題是典型的組合優化問題。假設有N個工件，每個工件都按相同的順序經過M臺機器加工，求解各工件的加工順序，使某種預先規定的目標函數達到最優。其最優時間求解在Matlab中的實現采用矩陣思想，主要代碼如下。

function [F， PI] = FSPFitness（ Problem， x ）

P = Problem'；

[M， N] = size（Problem）；

[aaa， ROV] = sort（x）；

C = zeros（N， M）；

C（ROV（1）， 1） = P（ROV（1）， 1）；

for i = 2：N

C（ROV（i）， 1） = C（ROV（i-1）， 1） + P（ROV（i）， 1）；

end

for k = 2：M

C（ROV（1）， k） = C（ROV（1）， k-1） + P（ROV（1）， k）；

end

for i = 2：N

for k = 2：M

C（ROV（i）， k） = max（C（ROV（i-1）， k）， C（ROV（i）， k-1）） + P（ROV（i）， k）；

end

end

F = C（ROV（N）， M）；

PI = ROV；

end

3 布谷鳥求解流水車間問題

在用布谷鳥求解流水車間調度問題時，經過隨機鍵編碼方式，布谷鳥找到的每個鳥巢代表了調度問題的一個解，主要代碼如下。

function [fmin，bestnest]=cuckoo_search_fsp（Problem，params）

[numMachines，numJobs] = size（Problem）；

if size（params） == [1， 3]

numNests = params（1）；

pa=params（3）；

MaxGeneration = params（2）；

else

numNests = 300；

pa=0.25；

MaxGeneration = 1000；

end

result = zeros（1， MaxGeneration）；

nest = rand（numNests， numJobs）；

fitness = 10e5*ones（1， numNests）；

[fmin，bestnest，nest，fitness]=get_best_nest（nest，nest，fitness，Problem）

for i=1：MaxGeneration，

new_nest=get_cuckoos（nest，bestnest）；

[fnew，best，nest，fitness]=get_best_nest（nest，new_nest，fitness，Problem）；

new_nest=empty_nests（nest，pa） ； [fnew，best，nest，fitness]=get_best_nest（nest，new_nest，fitness，Problem）；

if fnew

fmin=fnew；

bestnest=best；

end

result（i）=fmin；

%fprintf（'best：%f＼n'，fmin）；

end

plot（result）；

4 仿真測試

仿真測試的測試函數采用Car問題和Rec問題。為了獲得較好準確的結果，求解流水車間調度問題時獨立運行程序20詞，求出20詞中求得最優解的次數，然后求出尋優率，根據尋優率，對比多種算法的優劣。主要代碼

Car7=[692 310 832 630 258 147 255；

581 582 14 214 147 753 806；

475 475 785 578 852 2 699；

23 196 696 214 586 356 877；

158 325 530 785 325 565 412；

796 874 214 236 896 898 302；

542 205 578 963 325 800 120]'；

Problem = Car7；

BESTANSWER = 6590；

runTimes = 20；

for i=1：runTimes

subplot（2，1，1）；

hold on

[Best（i）， paixu] = cuckoo_search_fsp（Problem， [25， 500， 0.25]）；

hold off

subplot（2，1，2）；

xlim（[1，runTimes]）；

hold on

plot（Best）；

hold off

drawnow；

end

count = 0；

for i=1：runTimes

if Best（i） == BESTANSWER

count = count + 1；

end

end

為了驗證布谷鳥算法求解FSP的性能，對算法沒有采取改進策略，完全依靠算法自身進化機制尋優。選擇Car類基準測試問題進行仿真測試，并與螢火蟲算法在離散空間的優化性能進行對比。仿真測試的一組結果如圖1所示。

5 結論

本文將布谷鳥搜索算法這一優秀的元啟發式算法應用于流水車間調度問題領域。雖然流水車間調度問題是一個古老的課題，但由于它不可忽略的現實和理論意義，對該問題進一步探索守非常有意義的。本文針對求解以最小時間跨度的流水車間調度問題，具體設計布谷鳥算法，所做的工作有。求解質量是指，在給定的迭代次數內所求解的質量的好壞。本文基于該考慮，觀察和設計布谷鳥算法的各個組成要素，盡可能使算法能夠得到較優的調度。

參考文獻：

[1] 王慶喜， 趙珊. 基于改進布谷鳥搜索算法的工程設計優化[J]. 黑龍江大學自然科學學報， 2017， 345（2）：247-52.

[2] 陳超. 改進CS算法結合決策樹的云工作流調度[J]. 電子科技大學學報， 2016， 46（6）：974-980.

[3] 謝麗霞， 王志華. 基于布谷鳥搜索優化BP神經網絡的網絡安全態勢評估方法[J]. 計算機應用，2017， 37（7）：1926-1930.

[4] 王慶喜， 魏勝利. 基于混沌和非線性規劃的螢火蟲算法[J]. 科技通報， 2017， 33（5）：120-123.