基于布谷鳥搜索算法求解流水車間調(diào)度

張珊靚+王慶喜

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

關(guān)鍵詞：布谷鳥搜索算法；流程車間；調(diào)度

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）35-0104-02

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

1 布谷鳥搜索算法

布谷鳥搜索算法自從2009年問世以來廣泛醫(yī)用于多個(gè)領(lǐng)域，已經(jīng)成功優(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 流水車間問題求解

流水車間調(diào)度問題是典型的組合優(yōu)化問題。假設(shè)有N個(gè)工件，每個(gè)工件都按相同的順序經(jīng)過M臺(tái)機(jī)器加工，求解各工件的加工順序，使某種預(yù)先規(guī)定的目標(biāo)函數(shù)達(dá)到最優(yōu)。其最優(yōu)時(shí)間求解在Matlab中的實(shí)現(xiàn)采用矩陣思想，主要代碼如下。

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

在用布谷鳥求解流水車間調(diào)度問題時(shí)，經(jīng)過隨機(jī)鍵編碼方式，布谷鳥找到的每個(gè)鳥巢代表了調(diào)度問題的一個(gè)解，主要代碼如下。

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 仿真測試

仿真測試的測試函數(shù)采用Car問題和Rec問題。為了獲得較好準(zhǔn)確的結(jié)果，求解流水車間調(diào)度問題時(shí)獨(dú)立運(yùn)行程序20詞，求出20詞中求得最優(yōu)解的次數(shù)，然后求出尋優(yōu)率，根據(jù)尋優(yōu)率，對(duì)比多種算法的優(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

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

5 結(jié)論

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

參考文獻(xiàn)：

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

[2] 陳超. 改進(jìn)CS算法結(jié)合決策樹的云工作流調(diào)度[J]. 電子科技大學(xué)學(xué)報(bào)， 2016， 46（6）：974-980.

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

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