基于離散候鳥(niǎo)遷徙優(yōu)化算法的置換流水車間調(diào)度問(wèn)題

張素君,　顧幸生

(1.河南科技學(xué)院機(jī)電學(xué)院,河南 新鄉(xiāng) 453003; 2.華東理工大學(xué)化工過(guò)程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,上海 200237)

?

基于離散候鳥(niǎo)遷徙優(yōu)化算法的置換流水車間調(diào)度問(wèn)題

張素君1,2,顧幸生2

(1.河南科技學(xué)院機(jī)電學(xué)院,河南 新鄉(xiāng) 453003; 2.華東理工大學(xué)化工過(guò)程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,上海 200237)

針對(duì)置換流水車間調(diào)度問(wèn)題,以最小化最大完成時(shí)間為調(diào)度目標(biāo),提出了一種離散候鳥(niǎo)遷徙優(yōu)化(Discrete Migrating Birds Optimization,DMBO)調(diào)度算法。采用NEH產(chǎn)生一個(gè)調(diào)度可行解,其余個(gè)體隨機(jī)產(chǎn)生,保證了種群的質(zhì)量和多樣性,初始化鳥(niǎo)群按優(yōu)化目標(biāo)值升序排成倒V字形。領(lǐng)飛鳥(niǎo)通過(guò)優(yōu)化插入加優(yōu)化交換產(chǎn)生的鄰域解進(jìn)化,而通過(guò)混合策略獲得跟飛鳥(niǎo)的鄰域解。跟飛鳥(niǎo)通過(guò)其鄰域解和前面?zhèn)€體未使用的、較好的鄰域解進(jìn)化,這種進(jìn)化機(jī)制是獨(dú)一無(wú)二的。最后,采用局部搜索算法進(jìn)一步優(yōu)化種群。仿真實(shí)驗(yàn)中使用正交設(shè)計(jì)方法調(diào)節(jié)算法參數(shù),通過(guò)求解Car 和Rec標(biāo)準(zhǔn)算例,驗(yàn)證了算法的有效性。

置換流水車間調(diào)度問(wèn)題; 離散候鳥(niǎo)遷徙優(yōu)化算法; 破壞重建; 優(yōu)化插入加優(yōu)化交換操作

流水車間調(diào)度問(wèn)題已經(jīng)被研究了六十多年,尤其是優(yōu)化目標(biāo)為最小化最大完成時(shí)間的流水車間調(diào)度問(wèn)題更是吸引了很多學(xué)者的關(guān)注。該問(wèn)題能吸引這么多學(xué)者關(guān)注是因?yàn)樗趯?shí)際生產(chǎn)生活中的廣泛應(yīng)用,多數(shù)的制造業(yè)加工過(guò)程都可以建模為流水車間調(diào)度問(wèn)題[1],并且已經(jīng)被證明是NP難問(wèn)題[2]。置換流水車間調(diào)度問(wèn)題(Permutation Flow Shop Scheduling Problem,PFSP)可以描述為n個(gè)工件在m臺(tái)機(jī)器上按照相同順序加工的過(guò)程。求解該問(wèn)題的方法很多,采用精確算法優(yōu)化大規(guī)模問(wèn)題計(jì)算時(shí)間較長(zhǎng),甚至得不到最優(yōu)解,后來(lái)學(xué)者提出一些啟發(fā)式算法[3-4],通過(guò)一步或者三步構(gòu)造調(diào)度解。一步算法是直接根據(jù)經(jīng)驗(yàn)構(gòu)造,三步操作是產(chǎn)生排序、調(diào)度解的構(gòu)造、調(diào)度解的改進(jìn)。為了提高構(gòu)造解的質(zhì)量還提出了混合啟發(fā)式算法[5],它混和了多種啟發(fā)式算法。啟發(fā)式算法和混合啟發(fā)式算法的共同點(diǎn)是能夠在有限的時(shí)間內(nèi)構(gòu)造出調(diào)度解,但不能保證調(diào)度解的質(zhì)量。為了平衡調(diào)度解的質(zhì)量和時(shí)間成本,近年來(lái),各類智能優(yōu)化算法也廣泛地應(yīng)用于求解置換流水車間調(diào)度問(wèn)題,它可以彌補(bǔ)精確算法和啟發(fā)式算法的不足。其中遺傳算法[6]、模擬退火算法[7]、粒子群算法[8-10]、差分進(jìn)化算法[11]、人工蜂群算法[12]、果蠅優(yōu)化算法[13]及這些算法的改進(jìn)、混合等已經(jīng)被成功應(yīng)用于置換流水車間調(diào)度問(wèn)題。

Duman[14]在2012年提出了一種智能優(yōu)化算法——候鳥(niǎo)遷徙優(yōu)化 (Migrating Birds Optimization,MBO) 算法,并應(yīng)用于二次分配問(wèn)題。該算法模擬候鳥(niǎo)遷徙時(shí)采用倒V字形編隊(duì)飛行可以節(jié)省能量的思想實(shí)現(xiàn)優(yōu)化。該算法已成功應(yīng)用在混合流水車間調(diào)度[15]和信用卡欺詐檢測(cè)[16]等優(yōu)化問(wèn)題中,是一種新穎的群智能算法。由于它提出的時(shí)間較短并且有較好的優(yōu)化性能,相關(guān)的研究在國(guó)內(nèi)還比較少,在各個(gè)領(lǐng)域的應(yīng)用還具有較大的研究空間。本文針對(duì)置換流水車間調(diào)度問(wèn)題提出了離散候鳥(niǎo)遷徙算法。

1　置換流水車間調(diào)度問(wèn)題

把n個(gè)工件在m臺(tái)機(jī)器上按照相同的順序加工的調(diào)度問(wèn)題稱為置換流水車間調(diào)度問(wèn)題。n個(gè)工件中每一個(gè)工件必須在每臺(tái)機(jī)器上進(jìn)行加工,即每個(gè)工件有m個(gè)加工步驟,分別在m臺(tái)機(jī)器上完成,并且不同的工件在機(jī)器上的加工順序相同。置換流水車間調(diào)度問(wèn)題的求解是找到較好的工件加工順序(調(diào)度解),使某個(gè)優(yōu)化指標(biāo)的目標(biāo)值在所有可行的調(diào)度解中最小。

式中Pπ(i),j,Cπ(i),j分別表示工件π(i)在機(jī)器j上的加工時(shí)間和加工完成時(shí)間。式(1)表示第1個(gè)工件在第1臺(tái)機(jī)器上的加工完成時(shí)間C(π(1),1)等于它的加工時(shí)間Pπ(1),1;式(2)表示某一工件π(i)在第1臺(tái)機(jī)器上的加工完成時(shí)間等于前一個(gè)工件π(i-1)在第1臺(tái)機(jī)器上的加工完成時(shí)間加上該工件在第1臺(tái)機(jī)器上的加工時(shí)間;式(3)描述了第1個(gè)工件π(1)在第j臺(tái)機(jī)器上的加工完成時(shí)間;式(4)給出工件π(i)(i∈{2,3,…,n})在機(jī)器j(j∈{2,3,…,m})上的加工完成時(shí)間,當(dāng)i=n,j=m時(shí)求得C(π(n),m)即為該調(diào)度解π的最大完成時(shí)間Cmax(π)。依據(jù)上述方法求出集合Π中所有調(diào)度解的最大完成時(shí)間,找到完成時(shí)間最小的調(diào)度解π*。

2　基本候鳥(niǎo)遷徙優(yōu)化(MBO)算法

受候鳥(niǎo)遷徙時(shí)排成倒V字形這一自然現(xiàn)象啟發(fā)Duman提出了候鳥(niǎo)遷徙優(yōu)化 (MBO)[14]算法。經(jīng)過(guò)分析,排成倒V字形的原因一是因?yàn)楣?jié)省能量,二是鳥(niǎo)群之間的視覺(jué)關(guān)系以及避免相互碰撞。生物學(xué)家研究表明,影響節(jié)省能量程度的參數(shù)主要有兩個(gè):鳥(niǎo)群中每只鳥(niǎo)與前一只鳥(niǎo)翅尖之間的橫向距離,它決定了V字形的開(kāi)度;另一個(gè)參數(shù)為候鳥(niǎo)中鳥(niǎo)之間的縱向距離。算法中鳥(niǎo)群中的每只鳥(niǎo)對(duì)應(yīng)優(yōu)化問(wèn)題的一個(gè)解,每個(gè)解都可以得益于前面?zhèn)€體。算法開(kāi)始于倒V字形的一種隨機(jī)排列,其中第1個(gè)解對(duì)應(yīng)領(lǐng)飛鳥(niǎo),其余的排在兩邊的是跟飛鳥(niǎo),進(jìn)化過(guò)程中每只鳥(niǎo)(解)都在其鄰域內(nèi)進(jìn)行搜索,搜索到的鄰域解若優(yōu)于當(dāng)前解,則替換,同時(shí)較好的、未使用的鄰域解存到某個(gè)集合中供跟飛鳥(niǎo)進(jìn)化時(shí)使用。每只跟飛鳥(niǎo)通過(guò)其自身的鄰域解以及前面?zhèn)€體未使用的、較好的鄰域解進(jìn)化,若它們中最優(yōu)的優(yōu)于當(dāng)前解,則替換,直到所有的個(gè)體都完成進(jìn)化。這樣的過(guò)程經(jīng)過(guò)幾次巡回,更新領(lǐng)飛鳥(niǎo)。MBO算法在國(guó)內(nèi)外的研究還處于起步階段,文獻(xiàn)較少,因此如何設(shè)計(jì)算法使之適應(yīng)于解決各類優(yōu)化問(wèn)題,以及算法中參數(shù)的設(shè)計(jì)是值得研究的問(wèn)題,并且有很大的研究空間。

候鳥(niǎo)遷徙算法的偽代碼如下:

Generateninitial solutions and place them on an hypothetial V formation arbitrarily

ForT=1:Genmax

Forg=1:G

Fori=1:S

進(jìn)化領(lǐng)飛鳥(niǎo),通過(guò)領(lǐng)飛鳥(niǎo)的鄰域解;

進(jìn)化跟飛鳥(niǎo),通過(guò)跟飛鳥(niǎo)的鄰域解和前面?zhèn)€體鄰域解中未使用的較好的鄰域解;

End For

End For

更新領(lǐng)飛鳥(niǎo);

End For

其中：T和Genmax分別為進(jìn)化代數(shù)和最大進(jìn)化代數(shù)；G為巡回次數(shù)；S為種群規(guī)模。

MBO算法不同于其他群智能算法表現(xiàn)在以下幾方面:(1) 并行搜索。并行解進(jìn)化方式可以擴(kuò)大搜索范圍,更容易搜索到全局最優(yōu)解。(2) 個(gè)體進(jìn)化機(jī)制。該算法的個(gè)體進(jìn)化機(jī)制是目前群智能算法中獨(dú)一無(wú)二的。每個(gè)個(gè)體不僅在其鄰域內(nèi)搜索較優(yōu)的解,還可以利用前面?zhèn)€體產(chǎn)生的未使用的、較優(yōu)的鄰域解來(lái)更新個(gè)體。這種進(jìn)化機(jī)制使得種群中的個(gè)體不僅并行優(yōu)化,個(gè)體之間還會(huì)分享較優(yōu)的解,增加了算法的全局搜索能力。(3)一定的巡回次數(shù)后,更新領(lǐng)飛鳥(niǎo),增加算法的局部搜索能力，每個(gè)個(gè)體都會(huì)在它的鄰域內(nèi)充分搜索。

從MBO算法的進(jìn)化過(guò)程來(lái)看,它適用于流水車間調(diào)度這種組合優(yōu)化問(wèn)題。

3　求解置換流水車間調(diào)度問(wèn)題的離散候鳥(niǎo)遷徙優(yōu)化(DMBO)算法

3.1編碼與種群初始化

用工件排序進(jìn)行離散編碼,π={π(1),π(2),…,π(n)}。若π={2,5,3,1,4}是1個(gè)5工件的調(diào)度解,表明工件加工順序依次是2,5,3,1,4。

為了兼顧種群的質(zhì)量和多樣性,初始化中利用NEH初始化領(lǐng)飛鳥(niǎo),其余的個(gè)體隨機(jī)產(chǎn)生。已經(jīng)證明NEH[4]是一種性能較好的啟發(fā)式算法,特別是調(diào)度目標(biāo)為最大完成時(shí)間的流水車間調(diào)度問(wèn)題,因此常用來(lái)初始化種群。NEH算法描述如下:

(2) 根據(jù)優(yōu)化指標(biāo)調(diào)度排列中的前兩個(gè)工件,得到較優(yōu)的部分調(diào)度解,作為當(dāng)前部分調(diào)度解;

(3) 將步驟(1)排列中的第i(i=3,4,…,n)個(gè)工件依次插入到當(dāng)前部分調(diào)度解的所有可能位置,找出較優(yōu)的調(diào)度解作為當(dāng)前的部分調(diào)度解,直到所有的工件調(diào)度完。

將得到的種群按照優(yōu)化指標(biāo)(makespan)升序排列,其中最小的作為領(lǐng)飛鳥(niǎo),其余偶數(shù)序號(hào)的個(gè)體依次放在左邊隊(duì)列Ll,奇數(shù)序號(hào)的個(gè)體依次放在右邊隊(duì)列Lr,使種群中的個(gè)體排成倒V字形。

3.2領(lǐng)飛鳥(niǎo)的進(jìn)化

在流水車間調(diào)度問(wèn)題中,常用的鄰域解產(chǎn)生方式有3種,其中插入和交換較為有效。假設(shè)有n個(gè)工件待加工。

插入操作:假設(shè)把工件排列中的第v個(gè)工件插入到位置w。

ifv

πnew={π(1),…,π(v-1),π(v+1),…,π(w),π(v),π(w+1)，…，π(n)}

ifv>w,則

πnew={π(1),…,π(w-1),π(v),π(w),…,π(v-1),π(v+1)，…，π(n)}

交換操作:交換排列中任意兩個(gè)工件的加工順序。

ifv

πnew={π(1),…,π(v-1),π(w),π(v+1),…,π(w-1),π(v),π(w+1)，…，π(n)}

ifv>w,則

πnew={π(1),…,π(w-1),π(v),π(w+1),…,π(v-1),π(w),π(v+1)，…，π(n)}

DMBO算法中領(lǐng)飛鳥(niǎo)的更新是利用本身的鄰域解,其鄰域解中未使用的較優(yōu)解供跟飛鳥(niǎo)進(jìn)化時(shí)使用,領(lǐng)飛鳥(niǎo)的鄰域解質(zhì)量對(duì)算法的效果影響較大,因此,采用優(yōu)化插入加優(yōu)化交換操作。

優(yōu)化插入操作:

(1) 從當(dāng)前工件序列中隨機(jī)選擇一個(gè)工件π(v),并從原序列中刪除,得到部分序列;

(2) 把該工件插入到部分序列中的n個(gè)可能位置上,得到n個(gè)新的排列;

(3) 根據(jù)優(yōu)化目標(biāo),把n個(gè)新的排列中最優(yōu)的一個(gè),作為優(yōu)化插入后的序列。

優(yōu)化交換操作:

(1) 隨機(jī)從工件序列中選擇一個(gè)工件π(v),并把該工件與原序列中的任一工件交換位置,可以得到n-1個(gè)新的排列;

(2) 依據(jù)優(yōu)化目標(biāo),找到n-1個(gè)新的排序和原序列共n個(gè)序列中最好的排序,作為優(yōu)化交換后的序列。

優(yōu)化插入加優(yōu)化交換操作中優(yōu)化交換的對(duì)象為優(yōu)化插入作用后得到的序列。領(lǐng)飛鳥(niǎo)進(jìn)化采用優(yōu)化插入加優(yōu)化交換產(chǎn)生k個(gè)鄰域解。若這k個(gè)鄰域解中的最優(yōu)解優(yōu)于當(dāng)前領(lǐng)飛鳥(niǎo),則用這個(gè)最優(yōu)解替換當(dāng)前領(lǐng)飛鳥(niǎo),并將未使用的2x個(gè)最優(yōu)的鄰域解中x個(gè)填入集合PL，另外x個(gè)填入集合PR，其中PL和PR為左右兩邊存放該個(gè)體鄰域解中未使用的最優(yōu)解的集合。

3.3跟飛鳥(niǎo)的進(jìn)化

跟飛鳥(niǎo)通過(guò)鄰域解及前面?zhèn)€體鄰域解中未使用的較優(yōu)鄰域解進(jìn)化。為保證鄰域解的質(zhì)量和多樣性,每個(gè)鄰域解采用以下混合策略之一產(chǎn)生?；旌喜呗圆僮靼ú迦?、交換和破壞重建操作,用Si表示。而插入和交換的次數(shù)p(擾動(dòng)程度)對(duì)鄰域解的質(zhì)量影響很大。破壞重建(Destruction-Construction)操作是迭代貪婪算法(Iterated Greedy,IG)[17]的核心操作,也是較為有效的產(chǎn)生鄰域解的方法。

S1:執(zhí)行插入操作1次(p=1);

S2:執(zhí)行交換操作1次(p=1);

S3:執(zhí)行插入操作2次(p=2);

S4:執(zhí)行交換操作2次(p=2);

S5:執(zhí)行插入操作3次(p=3);

S6:執(zhí)行交換操作3次(p=3);

S7:執(zhí)行破壞重建操作。

破壞重建操作[17]的步驟如下:

(1) 從排序π中不重復(fù)地隨機(jī)選出d個(gè)工件,組成部分序列πd,并把這d個(gè)工件從原序列中刪除,其余工件組成的序列稱為πr;

(2) 把πd中的第1個(gè)工件插入到πr中的所有可能位置,依據(jù)優(yōu)化指標(biāo)找出最好的,更新πr,同時(shí)把πd中的第1個(gè)工件刪除,更新πd;

(3) 如果πd不為空,轉(zhuǎn)到步驟 (2),否則結(jié)束,πr即為經(jīng)過(guò)破壞重建操作的一個(gè)完整調(diào)度解。其中d為對(duì)調(diào)度解的破壞程度,因此,d的選擇將會(huì)對(duì)算影響較大。

對(duì)于個(gè)體π∈Ll,采用混合策略操作產(chǎn)生k-x個(gè)鄰域解,即{π(1),π(2),…,π(k-x)},集合NZ={π(1),π(2),…,π(k-x)}∪PL中最優(yōu)解如果優(yōu)于π則替換,清空PL,并用NZ中未使用的x個(gè)最優(yōu)解填充。

對(duì)于個(gè)體π∈Lr,采用多策略操作產(chǎn)生k-x個(gè)鄰域解,即{π(1),π(2),…,π(k-x)},集合NY={π(1),π(2),…,π(k-x)}∪PR中的最優(yōu)解如果優(yōu)于π,則替換,清空PR,并用NY中未使用的x個(gè)最優(yōu)解填充。

3.4領(lǐng)飛鳥(niǎo)的更新

領(lǐng)飛鳥(niǎo)和所有跟飛鳥(niǎo)進(jìn)化一定的巡回次數(shù)后,更新領(lǐng)飛鳥(niǎo),用標(biāo)志F0表示是用左邊隊(duì)列第1個(gè)跟飛鳥(niǎo)替換領(lǐng)飛鳥(niǎo)還是用右邊替換。若F0=1,則用左邊的替換領(lǐng)飛鳥(niǎo),而原來(lái)的領(lǐng)飛鳥(niǎo)移到左邊隊(duì)列的最后一個(gè),左邊隊(duì)列的其他鳥(niǎo)依次前移一個(gè)位置,并且置F0=0;若F0=0,用右邊第1個(gè)替代領(lǐng)飛鳥(niǎo),原來(lái)的領(lǐng)飛鳥(niǎo)到右邊隊(duì)列的最后一個(gè),右邊隊(duì)列的其他個(gè)體依次前移一個(gè)位置,并且置F0=1。

3.5種群重置

為了避免算法陷入局部最優(yōu),本文設(shè)計(jì)了一種重置機(jī)制。如果鳥(niǎo)群中的最優(yōu)個(gè)體超過(guò)limit代沒(méi)有更新,種群將會(huì)被重置。重置個(gè)體如果隨機(jī)產(chǎn)生,前面的進(jìn)化結(jié)果將不起作用,導(dǎo)致算法收斂速度下降。一般認(rèn)為最優(yōu)個(gè)體攜帶著較好的信息,因此對(duì)最優(yōu)個(gè)體執(zhí)行2次交換(SWAP)操作來(lái)產(chǎn)生種群中的個(gè)體,這樣,既保留了原來(lái)進(jìn)化得到的較好信息,也兼顧了種群的多樣性。

3.6局部搜索

局部搜索是為了增強(qiáng)算法的局部搜索能力,在領(lǐng)飛鳥(niǎo)和跟飛鳥(niǎo)都完成進(jìn)化后,對(duì)鳥(niǎo)群中的個(gè)體執(zhí)行破壞重建，進(jìn)行局部搜索,如果得到的解優(yōu)于原解,則替換,否則保留原解。

3.7離散候鳥(niǎo)遷徙優(yōu)化(DMBO)算法流程

離散候鳥(niǎo)遷徙優(yōu)化(DMBO)算法流程見(jiàn)圖1。

圖1　離散候鳥(niǎo)遷徙算法流程圖Fig.1　Flow chart of discrete migrating birds algorithm

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

4.1仿真環(huán)境和算例

仿真實(shí)驗(yàn)硬件環(huán)境為Intel Core(TM) i7-4770k/3.5 GHz/8.0 GB,軟件平臺(tái)為Windows 8系統(tǒng),所有算法均采用Matlab R2012b編寫。

仿真實(shí)驗(yàn)通過(guò)測(cè)試國(guó)際標(biāo)準(zhǔn)算例Car[18]和Rec[19]來(lái)測(cè)試本文算法的參數(shù)以及性能,其中Car算例有8個(gè)不同規(guī)模,而Rec標(biāo)準(zhǔn)算例包含21個(gè)不同規(guī)模。

4.2參數(shù)調(diào)節(jié)

智能優(yōu)化算法中的參數(shù)設(shè)置對(duì)算法的優(yōu)化效果影響很大,為了保證算法在其最佳的狀態(tài)下運(yùn)行,需要對(duì)參數(shù)合理設(shè)置。在DMBO算法中,鳥(niǎo)群規(guī)模S=51,每個(gè)個(gè)體進(jìn)行鄰域搜索時(shí)產(chǎn)生的鄰域解數(shù)量k=3,傳遞給下一個(gè)體的鄰域解數(shù)量x=1;然而巡回次數(shù)G,破壞重建操作中的破壞程度d,最優(yōu)解持續(xù)不變的最大代數(shù)limit以及混合策略中的插入和交換擾動(dòng)程度p也會(huì)對(duì)算法的效果造成影響。運(yùn)用正交試驗(yàn)法對(duì)上述4個(gè)參數(shù)調(diào)節(jié),4個(gè)參數(shù)設(shè)為4個(gè)因素,每個(gè)因素有3個(gè)水平,如表1所示。

表1　正交試驗(yàn)因素/水平表Table 1　Factors and levels for orthogonal experiment

用正交試驗(yàn)法對(duì)DMBO算法中的4個(gè)參數(shù)調(diào)節(jié),只需測(cè)試32=9組參數(shù)值,就能得到每個(gè)參數(shù)的最佳設(shè)置值,但如果對(duì)全部參數(shù)組合進(jìn)行測(cè)試,需要34=81組實(shí)驗(yàn),據(jù)此,采用正交試驗(yàn)法選擇參數(shù)可以提高效率。

本文通過(guò)對(duì)中等規(guī)模的算例Rec29進(jìn)行正交試驗(yàn)來(lái)測(cè)試參數(shù)。表2列出正交設(shè)計(jì)表L9(34)以及得到的正交試驗(yàn)結(jié)果,算法中的參數(shù)分別設(shè)置為表2中的參數(shù)組合,每組實(shí)驗(yàn)獨(dú)立運(yùn)行10次,共需測(cè)試9×10=90次算法。表2中的最后一列為該組參數(shù)得到的算法10次運(yùn)行最大完成時(shí)間(makespan)的平均值A(chǔ)VG。k1,k2,k3對(duì)應(yīng)各個(gè)參數(shù)在3個(gè)水平上測(cè)試結(jié)果的平均值。SD為標(biāo)準(zhǔn)差(Standard Deviation,SD),每個(gè)參數(shù)的k1到k3的標(biāo)準(zhǔn)差列于最后一行。k1,k2,k3中每一列的最小值對(duì)應(yīng)的水平為該因素較好的選擇,并在表中以黑體標(biāo)出。SD值較大的因素,對(duì)算法的影響也較大,SD值的排列按降序排列,序號(hào)置于對(duì)應(yīng)的值后的括號(hào)內(nèi)。4個(gè)參數(shù)在不同水平的變化曲線圖如圖2所示。

表2　L9(34)正交表和實(shí)驗(yàn)結(jié)果Table 2　Orthogonal parameter table L9(34) and results

圖2　DMBO算法中4個(gè)參數(shù)在3個(gè)水平的變化趨勢(shì)圖Fig.2　Trend graph of 4 parameters at 3 levels in HDABC algorithm

由表2和圖2可知,由于d的SD最大，因此破壞程度d對(duì)算法性能影響最大,而limit影響最小,G如果選擇太大將會(huì)使算法復(fù)雜度大大增加,因此在不影響算法效果的前提下,兼顧算法復(fù)雜度選擇G=10,其余參數(shù)選擇p=3,d=8,limit=5時(shí)算法效果較好。

4.3測(cè)試算法性能

為測(cè)試本文算法DMBO在求解PFSP時(shí)的效果,將DMBO算法與文獻(xiàn)[11]和文獻(xiàn)[12]中解決同一問(wèn)題的算法進(jìn)行對(duì)比,2個(gè)算法分別是混合差分進(jìn)化算法(HDE)和混合離散果蠅算法(HDFOA)。同時(shí)為了驗(yàn)證加入種群重置后的效果,還列出了NDMBO算法的測(cè)試結(jié)果，如表3所示。表中BRE為最優(yōu)百分偏差,ARE為平均百分偏差,計(jì)算公式如式(6)和式(7)所示。SD為10次測(cè)試結(jié)果的標(biāo)準(zhǔn)差,如式(8)所示。

(6)

(7)

(8)

式(6)和式(7)中，C*為makespan理論最優(yōu)值,Cmin和CAVG分別為10次測(cè)試結(jié)果的最小值和平均值。

表3列出了針對(duì)3個(gè)相同指標(biāo)4個(gè)算法的對(duì)比結(jié)果,對(duì)相同指標(biāo)4個(gè)算法得到的最小目標(biāo)值用黑體標(biāo)出?？梢钥闯?DMBO和NDMBO算法具有較好的優(yōu)化效果,但是計(jì)算時(shí)間比HDFOA和HDE算法的計(jì)算時(shí)間略長(zhǎng)。DMBO和NDMBO相比,加入種群重置機(jī)制可以使算法跳出局部最優(yōu),收斂到更好的目標(biāo)值。圖3示出了4種算法測(cè)試Car和Rec算例中的最大規(guī)模算例Rec41的收斂曲線,從4條曲線的收斂速度以及最后達(dá)到的收斂精度可以看出,DMBO和NDMBO相比,DMBO能搜索到更好的目標(biāo)值,二者收斂速度相當(dāng)。而在本算例上HDFOA要比HDE差些,但對(duì)其他大部分算例,>HDFOA要優(yōu)于HDE,這點(diǎn)從表3不難看出,但兩者都略差于本文提出的算法。

圖3　算例Rec41的4個(gè)算法收斂曲線圖Fig.3　Convergence curves of instance Rec41表3　NDMBO/DMBO/HDFOA/HDE算法對(duì)比結(jié)果Table 3　Comparison results of NDMBO,DMBO,HDFOAand HDE

問(wèn)題n,mNDMBODMBOHDFOA[13]HDE[11]BRE/%ARE/%SDBRE/%ARE/%SDBRE/%ARE/%SDBRE/%ARE/%SDCar111,5000000000000Car213,4000000000000Car312,500000000000.5444.35Car414,4000000000000Car510,600000000000.5949.54Car68,900000000000.1527.41Car77,700000000000.4560.22Car88,8000000000000Rec0120,500.140.6000000.100.9800.150.45Rec0320,500000000000.151.25Rec0520,500.191.2000.051.2000.220.770.240.383.33Rec0720,1000000000000.927.59Rec0920,1000000000000.2711.60Rec1120,10000000000000Rec1320,150.100.182.2900.020.8000.191.700.260.718.57Rec1520,1500000000.121.900.051.0014.96Rec1720,1500.07000000.042.100.371.3111.87Rec1930,100.280.2900.240.280.300.290.514.060.290.919.10Rec2130,100.151.317.800.140.1500.451.395.160.201.289.17Rec2330,100.150.372.460.100.212.100.350.602.820.500.7010.63Rec2530,150.200.483.4300.203.140.401.157.940.681.4316.49Rec2730,150.130.688.360.000.264.660.341.005.350.841.204.60Rec2930,150.090.345.570.000.112.800.480.954.800.531.3013.34Rec3150,100.260.422.300.260.270.300.851.357.970.431.2013.11Rec3350,100000000.030.404.760.350.794.74Rec3550,10000000000000Rec3775,201.391.6510.931.071.4712.532.182.8512.201.702.6333.41Rec3975,200.881.054.770.690.945.701.201.8512.781.281.547.86Rec4175,201.351.7217.330.911.3316.842.462.9413.301.712.6236.39Average0.170.312.310.120.181.740.310.543.050.330.7713.79

綜上,就求解PFSP問(wèn)題而言,本文提出的DMBO算法具有一定的有效性和優(yōu)越性,由于候鳥(niǎo)遷徙算法的并行搜索以及個(gè)體之間的利益共享機(jī)制使該算法具有較強(qiáng)的局部和全局搜索能力。

5　結(jié)　論

針對(duì)置換流水車間調(diào)度問(wèn)題(PFSP),本文提出了離散候鳥(niǎo)遷徙優(yōu)化算法優(yōu)化工件的最大完成時(shí)間。初始化采用NEH,提高初始化種群質(zhì)量。進(jìn)化過(guò)程分為領(lǐng)飛鳥(niǎo)進(jìn)化和跟飛鳥(niǎo)進(jìn)化兩個(gè)階段,領(lǐng)飛鳥(niǎo)進(jìn)化通過(guò)其鄰域解,跟飛鳥(niǎo)進(jìn)化通過(guò)其鄰域解以及前面?zhèn)€體鄰域解中未使用的、較好的鄰域解。進(jìn)化過(guò)程經(jīng)過(guò)一定的巡回次數(shù)后,更新領(lǐng)飛鳥(niǎo),每個(gè)個(gè)體都在其鄰域內(nèi)充分搜索,提高了算法的局部搜索能力。實(shí)驗(yàn)結(jié)果驗(yàn)證了DMBO算法的優(yōu)化能力,利用該算法求解,大部分算例幾乎都能找到最優(yōu)解,個(gè)別找不到最優(yōu)解的算例,也找到了比其他算法更接近最優(yōu)解的次優(yōu)解。下一步的研究重點(diǎn)是將離散候鳥(niǎo)遷徙優(yōu)化算法進(jìn)一步改進(jìn)應(yīng)用在其他調(diào)度問(wèn)題中,并致力于降低算法的復(fù)雜度。

[1]MOHAMMAD M.A novel hybrid genetic algorithm to solve the sequence-dependent permutation flow-shop scheduling problem[J].The International Journal of Advanced Manufacturing Technology,2014,71(1/4):429-437.

[2]GAREY M R,JOHNSON S,SETHY R.The complexity of flow shop and job-shop scheduling[J].Mathematics of Operations Research,1976,1(2):117- 129.

[3]唐聃,黃健.流水車間調(diào)度問(wèn)題的啟發(fā)式算法研究[J].電子科技大學(xué)學(xué)報(bào),2013,42(6):921-925.

[4]NAWAZ M,ENSCORE J E,HAM I.A heuristic algorithm for them-machine,n-job flow-shop sequencing problem[J].Omega,1983,11(1):91-95.

[5]ZOBOLAS G I,TARANTILIS C D,IOANNOU G.Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm[J].Computers & Operations Research,2009,36(4):1249-1267.

[6]凃雪平,施燦濤,李鐵克.求解流水車間調(diào)度問(wèn)題的改進(jìn)遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(36):50-53.

[7]PEMPERA J,SMUTNICKI C,ZELAZNY D.Optimizing bicriteria flow shop scheduling problem by simulated annealing algorithm[J].Procedia Computer Science,2013,18:936-945.

[8]KUO I H,HORNG S J.An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model[J].Expert Systems with Applications,2009,36(3):7027-7032.

[9]楊子江,顧幸生.基于混沌量子粒子群算法的置換流水車間調(diào)度[J].華東理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,39(3):325-330.

[10]劉延風(fēng),劉三陽(yáng).改進(jìn)微粒群優(yōu)化求解置換流水車間調(diào)度問(wèn)題[J].計(jì)算機(jī)集成制造系統(tǒng),2009,15(10):1968-1972.

[11]QIAN Bin,WANG Ling.A hybrid differential evolution method for permutation flow-shop scheduling[J].The International Journal of Advanced Manufacturing Technology,2008,38(7):757-777.

[12]LIU Yangfeng,LIU Sanyang.A hybrid discrete artificial bee colony algorithm for permutation flow shop scheduling problem[J].Applied Soft Computing,2013,13(3):1459-1463.

[13]鄭曉龍,王陵,王圣堯.求解置換流水線調(diào)度問(wèn)題的混合離散果蠅算法[J].控制理論與應(yīng)用,2014,31(2):159-164.

[14]DUMAN E,UYSAL M,ALKAYA A F.Migrating birds optimization:A new metaheuristic approach and its performance on quadratic assignment problem[J].Information Sciences,2012,217:65-77.

[15]PAN Quanke,YAN Dong.An improved migrating birds optimization for a hybrid flow shop scheduling with total flow time minimization[J].Information Sciences,2014,277:643-655.

[16]DUMAN E,ELIKUCUK I.Solving credit card fraud detection problem by the new metaheuristics migrating birds optimization[C]//Proceedings of 12th International Work-Conference on Artificial Neural Networks:Advances in Computational Intelligence.Spain:Springer,2013:62-71.

[17]RUIZ R,STüTZLE T.A simple and effective iterated greedy algorithm for the permutation flow shop scheduling problem[J].European Journal of Operational Research,2007,177(3):2033-2049.

[18]CARLIER J.Ordonnancements a contraintes disjonctives[J].Rairo IRO-Operations Research-Recherche Opérationnelle,1978,12(4):333-350.

[19]REEVES C R.A genetic algorithm for flow shop sequencing[J].Computers & Operations Research,1995,22(1):5-13.

A Discrete Migrating Birds Optimization Algorithm for Permutation Flow Shop Scheduling Problem

ZHANG Su-jun1,2,GU Xing-sheng2

(1.School of Mechanical and Electrical Engineering,Henan Institute of Science and Technology,Xinxiang 453003,Henan,China; 2.Key Laboratory of Advanced Control and Optimization for Chemical Process,Ministry of Education,East China University of Science and Technology,Shanghai 200237,China)

In this work,a discrete migrating birds optimization (DMBO) scheduling algorithm is proposed for permutation flow shop scheduling problem (PFSP) with the objective of minimizing maximum completion time (i.e. makespan).In order to guarantee the quality and diversity of the flock, NEH is employed to yield a feasible solution and the others are generated randomly in DMBO algorithm.The flock are arranged in the reversed hypothetical V formation according to the ascending order of optimization value.The leader is evolved from the neighbor solutions which are generated by optimizing insertion and swap operators.Meanwhile,the other birds in the flock are evolved by their neighbor solutions generated by hybrid-strategy and the unused better neighbor solutions of the previous generated by hybrid-strategy individuals.This evolution mechanism is unique for migrating birds optimization algorithm.Furthermore,a local search procedure is performed on every individual.Finally,an orthogonal design method is employed in experiment to regulate the parameters of DMBO.By testing the Car and Rec benchmarks,it is shown that the proposed DMBO algorithm is effective in the performance.

permutation flow shop scheduling problem; discrete migrating birds algorithm; destruction and construction; optimized insertion and optimized swap operators

A

1006-3080(2016)03-0412-08

10.14135/j.cnki.1006-3080.2016.03.019

2015-09-29

國(guó)家自然科學(xué)基金(61174040,61573144)

張素君(1978-),女,河南湯陰人,講師,主要研究方向?yàn)樯a(chǎn)調(diào)度和智能優(yōu)化算法。E-mail:sujunzh111@126.com

通信聯(lián)系人：顧幸生,E-mail:xsgu@ecust.edu.cn

F273