求解置換流水車間調(diào)度問題的布谷鳥算法

劉長(zhǎng)平， 葉春明

（1.上海理工大學(xué) 管理學(xué)院，上海 200093；2.淮陰工學(xué)院 經(jīng)濟(jì)管理學(xué)院，淮安 223001）

置換流水車間調(diào)度問題（permutation flow shop scheduling problem，PFSP）是在流水車間調(diào)度問題約束的基礎(chǔ)上，進(jìn)一步增加所有工件在任一臺(tái)機(jī)器上的加工順序均相同的約束后形成的生產(chǎn)調(diào)度問題，對(duì)PFSP的調(diào)度優(yōu)化可有效提高企業(yè)生產(chǎn)效益，但Garey等［1］早已證明機(jī)器數(shù)大于等于3的PFSP屬于NP完全問題，尚無多項(xiàng)式計(jì)算復(fù)雜性的全局優(yōu)化算法.因此，針對(duì)PFSP研究和開發(fā)高效的優(yōu)化技術(shù)具有重要的實(shí)際意義和工程價(jià)值.綜合現(xiàn)有文獻(xiàn)，求解PFSP的方法主要有經(jīng)典算法、構(gòu)造型算法和智能優(yōu)化算法.其中，經(jīng)典算法（如分支定界法、動(dòng)態(tài)規(guī)劃法等）可求得問題的精確解，但受問題規(guī)模和計(jì)算復(fù)雜性的限制，只適于求解小規(guī)模問題.構(gòu)造型算法（如NEH法、Rajendran法等）能夠快速建立問題的調(diào)度解，但構(gòu)造復(fù)雜，且通常解的質(zhì)量較差，主要用于求解雙機(jī)和三機(jī)PFSP.智能優(yōu)化算法（如遺傳算法［2］、蟻群算法［3］、粒子群算法［4］、蜂群算法［5］以及各種混合算法等）通過對(duì)鄰域的不斷搜索和當(dāng)前解的持續(xù)改進(jìn)，能夠在可接受時(shí)間內(nèi)以較大概率獲得最優(yōu)解或滿意解，取得了較好的優(yōu)化效果，在求解各種生產(chǎn)調(diào)度問題中獲得了廣泛應(yīng)用.布谷鳥算法（cuckoo search，CS）是模擬自然界中布谷鳥寄生孵育雛鳥的生物行為發(fā)展而來的一種群智能優(yōu)化算法，由Yang等［6］提出.該算法模型簡(jiǎn)單、可調(diào)參數(shù)少、收斂速度快，目前僅在函數(shù)優(yōu)化領(lǐng)域得到應(yīng)用［7－8］，在組合優(yōu)化領(lǐng)域的特性和應(yīng)用尚未進(jìn)行研究.基于布谷鳥算法的優(yōu)化機(jī)理和特點(diǎn)，針對(duì)置換流水車間調(diào)度問題的結(jié)構(gòu)特性，本文應(yīng)用該算法對(duì)置換流水車間調(diào)度問題進(jìn)行求解，對(duì)其在組合優(yōu)化領(lǐng)域的優(yōu)化性能進(jìn)行評(píng)估.仿真實(shí)驗(yàn)表明了該算法在離散空間也具有良好的進(jìn)化機(jī)制，有利于拓展到對(duì)其它組合優(yōu)化問題的求解.

1 置換流水車間調(diào)度問題描述

如果考核的調(diào)度指標(biāo)為最大完工時(shí)間，此類PFSP用調(diào)度三元法可表示為其中，F(xiàn)m為m臺(tái)機(jī)器的流水車間調(diào)度；prmu表明所有工件在任一臺(tái)機(jī)器上的加工順序均相同；Cmax為最大完工時(shí)間.數(shù)學(xué)描述為［9］：令tjk，i表示工件jk在機(jī)器i上的加工時(shí)間（假設(shè)各工件的加工準(zhǔn)備時(shí)間已包含在加工時(shí)間內(nèi)），Cjk，i表示工件jk在機(jī)器i上的完工時(shí)間為所有排序的集合，加工過程滿足不可中斷約束、機(jī)器唯一性約束和工件唯一性約束，假設(shè)各工件按照機(jī)器1到m的順序進(jìn)行加工，則工件在各機(jī)器上的完工時(shí)間可以通過遞歸方程計(jì)算

其中，式（1）～式（3）為計(jì)算完工時(shí)間的遞歸方程，式（4）為最大完工時(shí)間，式（5）為最小化最大完工時(shí)間所對(duì)應(yīng)的調(diào)度方案，n表示工件數(shù).

2 布谷鳥算法的優(yōu)化機(jī)理

2.1 算法仿生原理

布谷鳥是典型的巢寄生鳥類，其巢寄生行為表現(xiàn)在：a.布谷鳥自己不筑巢也不孵卵，將卵寄生在宿主的鳥巢里，讓其替自己孵化養(yǎng)育；b.布谷鳥在繁殖期尋找與孵化期和育雛期相似、雛鳥食性基本相同、卵形與顏色易仿的宿主；c.寄生時(shí)間上，布谷鳥多在宿主開始孵卵之前，乘宿主離巢外出時(shí)快速寄生產(chǎn)卵.宿主如果發(fā)現(xiàn)巢中的卵不是自己所產(chǎn)，會(huì)將“外來者”扔出或者棄巢另建新窩.因此，布谷鳥后代只能以一定概率得以孵化存活，概率大小取決于所選寄生鳥巢的狀況.如果所選寄生宿主的卵形與顏色相近、孵化期和育雛期相似、雛鳥食性基本相同，則后代被孵化并得以存活的可能性就大些；反之，就小一些.

布谷鳥算法是模擬自然界中布谷鳥寄生孵育雛鳥的生物行為構(gòu)造出的隨機(jī)搜索算法，體現(xiàn)了自然的擇優(yōu)機(jī)制.其仿生原理是：將布谷鳥所選宿主鳥巢映射為搜索空間中的點(diǎn)，將搜索和優(yōu)化過程模擬成布谷鳥搜尋和選擇鳥巢的過程，用宿主鳥巢所處位置的優(yōu)劣來代表孵育環(huán)境的好壞，進(jìn)而代表待求解問題的適應(yīng)度.將宿主鳥巢的擇優(yōu)過程類比為搜索和優(yōu)化過程中用好的可行解取代較差可行解的迭代過程.和真實(shí)的寄生孵育行為相比，算法中做了一些假設(shè)：假設(shè)宿主鳥巢的數(shù)量是固定的，并且布谷鳥在一巢只產(chǎn)一卵；宿主鳥巢位置越好，布谷鳥后代孵化存活的幾率越大.

2.2 算法的數(shù)學(xué)模型

布谷鳥寄生孵育雛鳥的生物行為可以用如下過程［6－7］進(jìn)行模擬：

定義1 布谷鳥選擇宿主鳥巢的位置更新式為

定義2 宿主發(fā)現(xiàn)“外來者”的概率為Pa，Pa大則布谷鳥后代孵化存活的概率小，反之則大.

算法實(shí)現(xiàn)優(yōu)化的過程是：布谷鳥首先在解空間內(nèi)隨機(jī)選擇一定數(shù)量的鳥巢并產(chǎn)卵，評(píng)估鳥巢優(yōu)劣，找出當(dāng)前最好的鳥巢，然后按照式（6）選擇新的鳥巢產(chǎn)卵（保留當(dāng)前最好鳥巢）.宿主若發(fā)現(xiàn)（概率為Pa）自己鳥巢中有“外來者”則放棄該鳥巢另建新巢，否則就接受更新位置后的鳥巢.布谷鳥對(duì)更新后的鳥巢進(jìn)行評(píng)估，找出最佳鳥巢，若更優(yōu)，則在當(dāng)前最佳鳥巢中產(chǎn)卵.這樣通過多次搜索和選擇后，布谷鳥可以找到最好的鳥巢（最優(yōu)位置），從而保證后代得以孵化存活.

3 置換流水車間調(diào)度問題求解

3.1 種群編碼方式

PFSP屬于典型的組合優(yōu)化問題，應(yīng)用布谷鳥算法求解PFSP首先需要構(gòu)造合理的編碼方式來表示調(diào)度問題的解.針對(duì)PFSP的特性，本文采用基于最小位置值規(guī)則的隨機(jī)鍵編碼方式［10］，將布谷鳥選擇宿主鳥巢的一個(gè)連續(xù)位置向量Xi＝［xi，1，xi，2，…，xi，n］轉(zhuǎn)換為機(jī)器上一個(gè)工件的加工順序π＝（j1，j2，…，jn），從而可以計(jì)算鳥巢位置所對(duì)應(yīng)調(diào)度解的適應(yīng)度值.這種編碼方式，保證了Xi→π得到的調(diào)度解均是可行解，同時(shí)無需修改布谷鳥算法的進(jìn)化操作.

3.2 算法流程

綜上所述，求解置換流水車間調(diào)度問題的布谷鳥算法流程如下：

a.初始化算法基本參數(shù)，布谷鳥選擇宿主鳥巢數(shù)目m，發(fā)現(xiàn)概率Pa，步長(zhǎng)因子α，搜索精度ε或最大搜索次數(shù)maxT；

b.布谷鳥隨機(jī)選擇鳥巢位置xi（i＝1，…，m），按照編碼方式轉(zhuǎn)換為工件加工順序，計(jì)算各鳥巢適應(yīng)度，找出當(dāng)中前最佳鳥巢位置x＊；

c.根據(jù)式（6）更新鳥巢的空間位置xi；

d.產(chǎn)生隨機(jī)數(shù)rand1，若rand1＞Pa，宿主放棄自己的鳥巢另建新巢，否則接受更新位置后的鳥巢；

e.對(duì)全部鳥巢進(jìn)行評(píng)估，找出當(dāng)前最佳鳥巢及所處位置，若優(yōu)于以往最佳鳥巢則替換；

f.當(dāng)滿足搜索精度或達(dá)到最大搜索次數(shù)轉(zhuǎn)g，否則轉(zhuǎn)c，進(jìn)行下一輪搜索；

g.輸出最優(yōu)值和對(duì)應(yīng)調(diào)度方案.

算法的時(shí)間復(fù)雜度為O（mmaxT）.

4 仿真實(shí)驗(yàn)與分析

為了驗(yàn)證布谷鳥算法求解PFSP的性能，對(duì)算法沒有采用任何改進(jìn)策略，完全依靠算法自身進(jìn)化機(jī)制來尋優(yōu).選擇Car類［11］基準(zhǔn)測(cè)試問題進(jìn)行仿真測(cè)試，并與螢火蟲算法（firefly algorithm，F(xiàn)A）［12］、粒子群算法（particle swarm optimization，PSO）［13］在離散空間的優(yōu)化性能進(jìn)行對(duì)比.

仿真環(huán)境：Windows XP操作系統(tǒng)，MATLAB R2010a編譯軟件，處理器主頻2.4GHz，內(nèi)存2GB.

算法參數(shù)設(shè)置為布谷鳥算法：發(fā)現(xiàn)概率Pa＝0.75，步長(zhǎng)因子α＝1.0.螢火蟲算法：光強(qiáng)吸收系數(shù)γ＝1.0，最大吸引度β0＝1.0，步長(zhǎng)因子α＝0.2.粒子群算法：采用線性減少的慣性權(quán)重Wmax＝0.9，Wmin＝0.4.學(xué)習(xí)因子：C1＝C2＝1.4 962.這3種算法中群體數(shù)m＝25，最大搜索次數(shù)maxT＝500，每種算法獨(dú)立運(yùn)行10次，p代表測(cè)試問題類型，C＊表示對(duì)應(yīng)調(diào)度問題的最小化完工時(shí)間，測(cè)試結(jié)果如表1所示.

表1 3種算法仿真測(cè)試結(jié)果Tab.1 Results of simulation tests for three algorithms

為對(duì)比算法的性能，采用了尋優(yōu)成功率（success rate，SR）、最優(yōu)相對(duì)誤差（best relative error，BRE）、平均相對(duì)誤差（average relative error，ARE）、最差相對(duì)誤差（worst relative error，WRE）4項(xiàng)指標(biāo)進(jìn)行衡量.從測(cè)試結(jié)果可以看出，對(duì)于上述測(cè)試問題，CS均能找到已知下界值而且尋優(yōu)成功率高于對(duì)應(yīng)的FA和PSO算法，反映出CS具有良好的全局收斂性.從ARE和BRE指標(biāo)來看，CS所求得調(diào)度解的質(zhì)量遠(yuǎn)高于FA和PSO算法，顯示出CS在離散空間具有優(yōu)良的進(jìn)化機(jī)制，而且CS求得ARE和BRE的值很小，表明CS算法對(duì)初始值具有較強(qiáng)的魯棒性.從測(cè)試尋優(yōu)曲線可以直觀看出，對(duì)于Car3、Car5問題，F(xiàn)A與PSO均出現(xiàn)了早熟收斂，而CS收斂速度和收斂精度均高于對(duì)比算法，限于篇幅，只列出了有代表性的兩幅圖（如圖1和圖2所示）.

圖1 Car3問題尋優(yōu)進(jìn)化曲線Fig.1 Optimization curve of Car3problem

圖2 Car5問題尋優(yōu)進(jìn)化曲線Fig.2 Optimization curve of Car5problem

5 結(jié)束語

布谷鳥算法通過模擬自然界中布谷鳥寄生孵育雛鳥的生物學(xué)特性，利用進(jìn)化方式來實(shí)現(xiàn)多智能體的行為以達(dá)到優(yōu)化目的，體現(xiàn)了自然選擇的擇優(yōu)機(jī)制.本文針對(duì)最小化最大完工時(shí)間的置換流水車間調(diào)度問題，應(yīng)用布谷鳥算法進(jìn)行求解，測(cè)試和對(duì)比結(jié)果驗(yàn)證了該算法求解置換流水車間調(diào)度問題的有效性和優(yōu)越性，在生產(chǎn)調(diào)度優(yōu)化領(lǐng)域展現(xiàn)出良好的應(yīng)用前景.

［1］Garey M R，Johnson D S，Sethi R.The complexity of flow shop and job shop scheduling［J］.Mathematics of Operations Research，1976，1（2）：117－129.

［2］朱夏，李小平，王茜.基于總空閑時(shí)間增量的無等待流水調(diào)度混合遺傳算法［J］.計(jì)算機(jī)研究與發(fā)展，2011，48（3）：455－463.

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

［4］田野，劉大有.求解流水車間調(diào)度問題的混合粒子群算法［J］.電子學(xué)報(bào)，2011，39（5）：1087－1093.

［5］李修琳，魯建廈，柴國(guó)鐘，等.混合蜂群算法求解柔性作業(yè)車間調(diào)度問題［J］.計(jì)算機(jī)集成制造系統(tǒng)，2011，17（7）：1495－1500.

［6］Yang X S，Deb S.Cuckoo search via Lévy flights［C］∥Proceedings of World Congress on Nature ＆Biologically Inspired Computing（NaBIC2009），India：IEEE Publications，2009：210－214.

［7］Yang X S，Deb S.Engineering optimization by cuckoo search［J］.International Journal of Mathematical Modelling and Numerical Optimisation，2010，1（4）：330－343.

［8］王凡，賀興時(shí)，王燕.基于高斯擾動(dòng)的布谷鳥搜索算法［J］.西安工程大學(xué)學(xué)報(bào)，2011，25（4）：565－569.

［9］Michael P.調(diào)度：原理、算法和系統(tǒng)［M］.2版.北京：清華大學(xué)出版社，2007.

［10］Tasgetren M F，Sevkli M，Liang Y C，et al.Particle swarm optimization algorithm for permutation flowshop sequencing problem［J］.Lecture Notes in Computer Science，2004，3172：382－389.

［11］Carlier J.Scheduling with disjunctive constraints［J］.Operations Research，1978，12（4）：333－350.

［12］劉長(zhǎng)平，葉春明.一種新穎的仿生群智能優(yōu)化算法：螢火蟲算法［J］.計(jì)算機(jī)應(yīng)用研究，2011，28（9）：3295－3297.

［13］Shi Y，Eberhart R.A Modified Particle Swarm Optimizer［C］∥Proceedings of IEEE International Conference on Evolutionary Computation，Anchorage：IEEE Publications，1998：69－73.