張珊靚+王慶喜

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

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

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

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

1 布谷鳥搜索算法

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

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 流水車間問題求解

流水車間調度問題是典型的組合優(yōu)化問題。假設有N個工件，每個工件都按相同的順序經過M臺機器加工，求解各工件的加工順序，使某種預先規(guī)定的目標函數達到最優(yōu)。其最優(yōu)時間求解在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詞中求得最優(yōu)解的次數，然后求出尋優(yōu)率，根據尋優(yōu)率，對比多種算法的優(yōu)劣。主要代碼

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的性能，對算法沒有采取改進策略，完全依靠算法自身進化機制尋優(yōu)。選擇Car類基準測試問題進行仿真測試，并與螢火蟲算法在離散空間的優(yōu)化性能進行對比。仿真測試的一組結果如圖1所示。

5 結論

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

參考文獻：

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

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

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

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