基于離散布谷鳥搜索算法的帶阻塞有差速混合流水車間調(diào)度

陳飛躍, 徐震浩, 顧幸生

(華東理工大學(xué)化工過程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,上海 200237)

?

基于離散布谷鳥搜索算法的帶阻塞有差速混合流水車間調(diào)度

陳飛躍, 徐震浩, 顧幸生

(華東理工大學(xué)化工過程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,上海 200237)

基于以最小完工時(shí)間為目標(biāo)的帶阻塞有差速混合流水車間調(diào)度問題,提出了一種改進(jìn)的離散布谷鳥搜索算法。在基本布谷鳥搜索算法的萊維飛行和巢寄生性的基礎(chǔ)結(jié)構(gòu)上,提出了一種基于交叉策略的萊維飛行機(jī)制,以便算法能夠解決離散問題;同時(shí),通過非余弦遞減策略的動(dòng)態(tài)發(fā)現(xiàn)概率去發(fā)現(xiàn)劣質(zhì)鳥巢,并利用排列差分進(jìn)化算法的變異思想將劣質(zhì)鳥巢重建;在搜索過程中設(shè)定全局最優(yōu)極值保持代數(shù)為閾值去重新發(fā)現(xiàn)劣質(zhì)鳥巢,以防止算法陷入局部最優(yōu);最后利用鄰域搜索方法進(jìn)一步提高算法的搜索精度。通過仿真實(shí)驗(yàn)驗(yàn)證了該算法在求解混合流水車間調(diào)度類離散問題上的有效性與優(yōu)越性。

布谷鳥搜索算法; 差分進(jìn)化; 阻塞; 差速; 最小完成時(shí)間

混合流水車間調(diào)度[1](Hybrid Flow-shop Scheduling Problem,HFSP)在現(xiàn)代復(fù)雜制造業(yè)普遍存在,很多學(xué)者對(duì)其進(jìn)行了深入的研究并取得了豐厚的成果。由于生產(chǎn)工藝要求、設(shè)備性能差異等客觀原因,帶阻塞有差速的混合流水車間調(diào)度問題應(yīng)運(yùn)而生。帶阻塞有差速的混合流水車間調(diào)度問題可以拆分為混合流水車間調(diào)度問題、帶阻塞流水車間調(diào)度問題以及有差速并行機(jī)流水車間調(diào)度問題。HFSP是一般流水車間調(diào)度問題的推廣,其最主要的特征是工件加工工序中至少有一道工序存在并行機(jī),并且在存在此工序,工件可以選擇任意一個(gè)并行機(jī)進(jìn)行加工;帶阻塞流水車間調(diào)度問題(Blocking Flow-shop Scheduling Problem,BFSP)[2]是對(duì)普通流水車間調(diào)度問題的進(jìn)一步約束,即工序之間不存在緩沖區(qū);有差速并行機(jī)流水車間調(diào)度(Unrelated Parallel Flow-shop Scheduling Problem,UPFSP)[3]是對(duì)一般帶并行機(jī)流水車間調(diào)度問題的拓展,即在每道工序的并行機(jī)可能由于設(shè)備型號(hào)、性能等客觀原因?qū)е录词股a(chǎn)相同工件,生產(chǎn)效率也不盡相同。帶阻塞有差速的混合流水車間調(diào)度(Blocking and Unrelated Hybrid Flow-shop Scheduling Problem,BUHFSP)是以上3種調(diào)度模型的擴(kuò)展融合。由于BUHFSP具有更高的柔性,而更適用于現(xiàn)代制造業(yè),對(duì)其研究有助于提高生產(chǎn)效率,且混合流水車間調(diào)度問題以及阻塞流水車間調(diào)度問題都屬于NP[4-5]完全問題,所以本文對(duì)帶阻塞有差速的混合流水車間調(diào)度問題的研究具有重要的學(xué)術(shù)價(jià)值和現(xiàn)實(shí)意義。

由于BHFSP問題的普遍存在性與求解復(fù)雜性,學(xué)者一直對(duì)其進(jìn)行著研究。Sawik[6]首次提出運(yùn)用整數(shù)規(guī)劃求解帶阻塞及中間存儲(chǔ)有限的混合流水車間調(diào)度問題,但整數(shù)規(guī)劃只適合求解小規(guī)模問題;Tavakkoli等[7]針對(duì)該問題提出了一種帶鄰域搜索的文化基因算法,并證明了該算法效果明顯優(yōu)于經(jīng)典的遺傳算法。然而,以上兩個(gè)算法都只是針對(duì)相同的并行加工設(shè)備。Yaurima等[8]利用改進(jìn)GA求解不相關(guān)并行機(jī)的緩沖區(qū)有限的混合流水車間調(diào)度問題,但其求解最多包含6個(gè)加工階段。在現(xiàn)實(shí)生產(chǎn)中,包含多階段不相關(guān)并行設(shè)備的情況普遍存在,而以往研究大多只針對(duì)無差速或者少階段、有差速、帶阻塞混合流水車間。因此本文對(duì)帶阻塞約束的有差速混合流水車間調(diào)度問題進(jìn)行了研究,以最小完工時(shí)間為目標(biāo)提出了一種基于每道工序完工時(shí)間最優(yōu)的啟發(fā)式規(guī)則的最小完工時(shí)間求解方法。

布谷鳥搜索算法作為一種新型現(xiàn)代元啟發(fā)式算法[9],由于其控制參數(shù)少、能有效平衡全局最優(yōu)與局部最優(yōu)及其結(jié)構(gòu)簡(jiǎn)單易實(shí)現(xiàn)的優(yōu)點(diǎn),一經(jīng)提出就受到學(xué)者的推崇,并成功用于工程優(yōu)化等實(shí)際問題中。Burnwal等[10]采用改進(jìn)的布谷鳥算法解決以最小化延期懲罰成本和最大化機(jī)器利用率為目標(biāo)的混合流水車間調(diào)度問題,并通過算例驗(yàn)證了該算法性能優(yōu)于已有的GA、PSO算法;劉長(zhǎng)平等[11]采用布谷鳥算法求解以最小完工時(shí)間為目標(biāo)的置換流水車間調(diào)度問題,并通過Benchmark算例證明了該算法的優(yōu)越性與有效性。布谷鳥搜索算法僅適用于求解連續(xù)問題,已有文獻(xiàn)針對(duì)調(diào)度類離散問題大多是利用一定的排序映射規(guī)則將布谷鳥算法應(yīng)用到離散問題,但是用該方法求解大規(guī)模問題就會(huì)陷入解震蕩的局面。

通過研究分析,針對(duì)BUHFSP問題,本文設(shè)計(jì)了5種改進(jìn)策略,分別是采用反向?qū)W習(xí)機(jī)制初始化布谷鳥鳥巢位置、改進(jìn)萊維飛行方式將算法離散化、改進(jìn)劣質(zhì)鳥巢發(fā)現(xiàn)概率、基于最優(yōu)閾值防止陷入局部最優(yōu)以及融入鄰域搜索。將以上改進(jìn)DCS算法用于求解帶阻塞的有差速混合流水車間調(diào)度問題,仿真實(shí)驗(yàn)驗(yàn)證了改進(jìn)DCS算法求解BUHFSP問題的有效性。

1 問題描述

一般的流水車間調(diào)度都會(huì)假設(shè)工序間緩沖區(qū)無限大,而本文研究的帶阻塞混合流水車間調(diào)度問題則假設(shè)工序之間不存在緩沖區(qū),即若某工件的某一工序完成該工序操作后,下一工序機(jī)器仍處于被占用狀態(tài),則該工件會(huì)在該機(jī)器上等待,并且阻塞該工序以后工件的加工直至下一個(gè)工序機(jī)器被釋放。針對(duì)一般流水調(diào)度車間模型,假設(shè)某車間要加工6件不同的工件,每個(gè)工件要經(jīng)歷3道工序,則不同的工序間存儲(chǔ)策略的對(duì)比如圖1所示。

圖1 不同存儲(chǔ)策略的3道工序流水車間最大完工時(shí)間的對(duì)比Fig.1 Comparison of the make-span of 3 procedures with different storage strategies

一般對(duì)帶阻塞有差速混合流水車間調(diào)度生產(chǎn)過程作如下假設(shè):

(1) 所有工件加工工序相同;

(2) 有并行機(jī)存在的工序,工件可以選擇任意空閑機(jī)器進(jìn)行加工;

(3) 工件間沒有優(yōu)先級(jí);

(4) 一臺(tái)機(jī)器不能同時(shí)加工多個(gè)工件,一個(gè)工件不能在同一時(shí)間被多臺(tái)機(jī)器加工;

(5) 工序間的緩沖區(qū)為零;

(6) 工件在各工序、各機(jī)器上的加工時(shí)間已知,并且各工序的并行機(jī)加工同一工件的時(shí)間可能不同;

(7) 原料不限,完工工件存儲(chǔ)空間不限。

根據(jù)以上假設(shè),帶阻塞有差速的混合流水車間可以描述為:n個(gè)待加工的工件要依次經(jīng)過S道工序的加工,每道工序至少有一臺(tái)加工設(shè)備并且至少有一道工序存在并行加工設(shè)備(設(shè)第j道工序的設(shè)備數(shù)為mj,j=1,2,…,S),要求確定所有工件的加工順序及其在并行機(jī)上的分配情況,以使得最大完工時(shí)間(makespan)最小。有差速混合流水車間調(diào)度模型如圖2所示,其中mi表示不同工序并行機(jī)的數(shù)量,矩形的大小表示工件在該機(jī)器上加工時(shí)間。

圖2 帶阻塞有差速混合流水車間調(diào)度模型Fig.2 Model of BUHFSP

假設(shè)工件數(shù)為n,機(jī)器數(shù)為m,工序數(shù)為λ,第k道工序的并行機(jī)數(shù)量為πk(k=1,2,…,λ),Ti,j表示工件Ji(i=1,2,…,n)在機(jī)器Mj(j=1,2,…,m)上的加工時(shí)間,Si,k表示工件Ji在工序k上的開始加工時(shí)間,Ci,k表示工件Ji在工序k上的完工時(shí)間,cmax為最大完工時(shí)間,Rj表示Mj被釋放的時(shí)間,可以得出BUHFSP的數(shù)學(xué)模型為

minCmax

(1)

s.t.

i=1,2,…,n;k=1,2,…,λ

(2)

(3)

其中:式(1)為問題的目標(biāo)函數(shù);式(2)表示某一工件的某一工序只能由一臺(tái)機(jī)器進(jìn)行加工;式(3)表示某一時(shí)刻某一機(jī)器只能加工某一工件;式(4)、式(5)表示有差速并行機(jī)并且?guī)ё枞拗频拈_工時(shí)間以及完工時(shí)間的約束關(guān)系。

2 改進(jìn)的離散布谷鳥算法

2.1 概述

布谷鳥搜索算法(Cuckoo Search Algorithm,CS)是由Yang等[9]基于布谷鳥的繁殖寄生行為提出的一種新型元啟發(fā)式群智能算法,其主要思想基于巢寄生特性以及萊維飛行機(jī)制兩個(gè)策略。巢寄生特性:布谷鳥等寄生鳥類在繁殖產(chǎn)卵季節(jié)選擇適宜的鳥巢并將鳥蛋產(chǎn)在宿主鳥巢,由宿主鳥孵育下一代;萊維飛行機(jī)制:萊維飛行是動(dòng)物最有效的一種覓食方式[12],在智能算法中采取萊維飛行機(jī)制,大步長(zhǎng)、小步長(zhǎng)交替出現(xiàn),可以有效地平衡局部最優(yōu)與全局最優(yōu)。本文利用基本布谷鳥搜索算法的優(yōu)勢(shì),提出了改進(jìn)的離散布谷鳥搜索算法(Discrete Cuckoo Search Algorithm,DCS)。

2.2 算法思路

2.2.1 編碼與解碼 采用整數(shù)編碼,即只針對(duì)工件的加工順序排序。編碼序列為

X=(x1,x2,…,xi,…,xn),

1≤i≤n,1≤xi≤n

(6)

其中xi為正整數(shù),表示所有工件加工的次序。

解碼可分為3步:

(1) 第1個(gè)工件分別選擇在各工序加工時(shí)間最短的機(jī)器上加工;

(2) 后續(xù)工件則占用最早完成本道工序加工的啟發(fā)式規(guī)則,依次加工剩余工件;

(3) 若有工序存在本工序完工時(shí)間相同的情況,則隨機(jī)選擇一臺(tái)機(jī)器進(jìn)行該工序的加工。

2.2.2 基于反向?qū)W習(xí)的初始化 隨機(jī)產(chǎn)生的初始鳥巢可能會(huì)在整個(gè)解空間中分布不均勻,為了提高初始鳥巢的質(zhì)量,同時(shí)保證初始鳥巢的均勻性,引入基于反向?qū)W習(xí)的機(jī)制[13],即對(duì)初始序列作xi=1+n-xi變換,然后分別計(jì)算其適應(yīng)度值,選取較優(yōu)的個(gè)體作為初始鳥巢,從而保證初始化種群的優(yōu)越性及提高收斂速度。

2.2.3 基于最早完工啟發(fā)式規(guī)則的適應(yīng)度值計(jì)算 編碼解碼方法初步解決了機(jī)器的分配問題。本文主要用到的啟發(fā)式思想為:從第1件工件開始加工,針對(duì)存在并行機(jī)的加工階段都選擇能夠使本階段最早完工的機(jī)器進(jìn)行加工。若并行機(jī)空閑,則直接選擇最優(yōu)的機(jī)器進(jìn)行加工;若有并行機(jī)被占用,則待其被釋放后比較該階段的完工時(shí)間,依舊選擇能夠使本階段最早完工的機(jī)器。算法處理過程如下:

Step1 針對(duì)前min(πk)件工件,只選擇能使工件在各階段最早完工的機(jī)器進(jìn)行加工;

Step2 針對(duì)min(πk)到max(πk)的工件,有空閑并行機(jī)存在的則選擇最優(yōu)的機(jī)器,瓶頸階段則選擇最早空閑或者能夠最早完工的機(jī)器進(jìn)行加工;

Step3 針對(duì)max(πk)以后的工件,則按照工件加工次序,依次進(jìn)行加工,對(duì)第1工序被釋放的機(jī)器按照最先釋放、最早優(yōu)先的規(guī)則安排工件加工,后序工序則采用使本階段最早完工、最早優(yōu)先的規(guī)則進(jìn)行加工,直至所有工序完畢為止。

根據(jù)以上3個(gè)步驟,對(duì)所有工件完成加工,求得最大完工時(shí)間。

2.3 算法流程

基本布谷鳥算法只適用于求解連續(xù)型優(yōu)化問題,而生產(chǎn)調(diào)度屬于組合優(yōu)化問題,因此借鑒遺傳算法的交叉思想以及基于排列的差分進(jìn)化變異思想對(duì)CS算法進(jìn)行離散化。

(1) 基于交叉的萊維飛行。萊維飛行是一種隨機(jī)游走機(jī)制,代表一類非高斯隨機(jī)過程。其隨機(jī)游走的公式為

(7)

(8)

從而新鳥巢的位置為

?L(β)

(9)

本文借鑒遺傳算法的交叉思想提出基于交叉的萊維飛行將萊維飛行離散化,即將種群的每個(gè)鳥巢位置分量與當(dāng)前最優(yōu)鳥巢位置分量以Pcross的概率進(jìn)行交叉操作。交叉操作可以部分或全部地繼承父代的優(yōu)秀基因,因此,所有鳥巢與最優(yōu)鳥巢的交叉可以使得各鳥巢位置向最優(yōu)位置快速靠攏。交叉概率Pcross借鑒搜索向量L(β)產(chǎn)生的思想,取Pcross=max(α⊕L(β)),即若當(dāng)前鳥巢位置分量與最優(yōu)鳥巢位置相對(duì)分量最大差異值較小時(shí),則該鳥巢位置與最優(yōu)鳥巢位置交叉概率較小;反之則較大。這樣根據(jù)與最優(yōu)鳥巢位置差異來控制交叉概率,從而能夠更好地利用“大小交叉概率”控制鳥巢種群的優(yōu)化方向。其中交叉采用整數(shù)修正的交叉方法。

(2) 余弦遞減策略的發(fā)現(xiàn)概率。一般的CS算法都是采用固定的發(fā)現(xiàn)概率Pa,Pa的大小會(huì)影響最優(yōu)解的搜索速度,Pa過大則較難收斂到最優(yōu)解,Pa過小則會(huì)使得收斂速度變慢。為了增加算法的自適應(yīng)性,本文引入了基于余弦遞減策略的動(dòng)態(tài)發(fā)現(xiàn)概率

(10)

其中:Pmax、Pmin表示最大、最小發(fā)現(xiàn)概率;i表示當(dāng)前迭代代數(shù);maxgen表示最大迭代代數(shù)。

引入該策略,可以使得算法在計(jì)算前期能夠在保證全局搜索能力的前提下快速收斂到非劣解,隨著迭代代數(shù)的增加,種群個(gè)體的質(zhì)量逐漸提高;到尋優(yōu)后期,Pa隨著代數(shù)的增加而減小,有利于算法進(jìn)行更精確的局部搜索。通過測(cè)試驗(yàn)證表明,動(dòng)態(tài)發(fā)現(xiàn)概率有效地提高了算法的收斂速度并改善了搜索能力。

(3) 剔除劣質(zhì)鳥巢,新增優(yōu)質(zhì)鳥巢。用一個(gè)隨機(jī)數(shù)r作為衡量宿主鳥發(fā)現(xiàn)鳥巢異常的概率,并與Pa進(jìn)行比較,若r>Pa,則通過對(duì)劣質(zhì)鳥巢位置進(jìn)行變異操作,產(chǎn)生新的鳥巢位置。本文采用排序差分進(jìn)化算法[14]的變異操作,其基本原理為將差分向量加到要變異的基向量上去。選擇DE/target-to-best/1的變異策略。即

(11)

(12)

其中:r1、r2為[1,N]內(nèi)與i不相等的隨機(jī)整數(shù),且兩兩不相等;F為縮放因子,為了增加增強(qiáng)算法的自適應(yīng)能力,本文取非線性遞增的取值策略,從而保證算法在運(yùn)算初期劣解與當(dāng)前最優(yōu)解差異較大時(shí)適當(dāng)?shù)乜刂茢_動(dòng),在算法后期適當(dāng)?shù)卦龃髷_動(dòng),動(dòng)態(tài)調(diào)節(jié)縮放因子F,從而可以有效平衡全局搜索與局部搜索。F的取值如式(12)所示,其中Fl=0.1,Fh=0.9,從而可以保證F在[0.1,0.9]之間隨著迭代代數(shù)的變化而變化。通過DE變異操作,可以有效地補(bǔ)充丟失的有效“基因”而維持鳥巢種群的多樣性。

(4) 基于最優(yōu)代數(shù)閾值的變異操作。在算法迭代開始前,定義全局最優(yōu)保持代數(shù)dir為零;當(dāng)對(duì)鳥巢位置迭代更新時(shí),在每一代的進(jìn)化過程中,記錄并更新當(dāng)前全局最優(yōu)值保持的代數(shù)dir,當(dāng)其全局最優(yōu)值保持代數(shù)超過設(shè)定的閾值stage時(shí),對(duì)當(dāng)前鳥巢種群進(jìn)行步驟(3)的操作,然后對(duì)dir置零。設(shè)置最優(yōu)代數(shù)閾值,可以有效地加快算法收斂速度,當(dāng)算法陷入局部最優(yōu),會(huì)通過變異來增加種群的多樣性,從而使算法能夠快速跳出局部最優(yōu)。而針對(duì)閾值的選擇,通過取不同等級(jí)的stage實(shí)驗(yàn)驗(yàn)證了隨著stage的增大,優(yōu)化性能會(huì)逐漸降低,但是若stage選取過小,則會(huì)增大算法的時(shí)間復(fù)雜度。綜合相關(guān)實(shí)驗(yàn)以及文獻(xiàn)[15]分析,取閾值stage=5。當(dāng)達(dá)到預(yù)設(shè)stage時(shí),則重復(fù)步驟(3)的操作,增加種群的多樣性,在一定程度上避免算法陷入局部最優(yōu)。

(5) 鄰域搜索。為了提高算法的搜索精度,引入鄰域搜索方法[16]。目前,針對(duì)調(diào)度等組合優(yōu)化類問題通常采用Insert、Swap以及Interchange 3種方法。Schiavinotto等[17]的研究表明,Insert和Interchange的直徑都是n-1,而Swap的直徑是n(n-1)/2,這表明局部搜索過程中,Insert和Interchange方法要比Swap方法更有效。本文采用基于Insert和Interchange方法的局部搜索(Local Search,IILS),在每代進(jìn)化的最后,對(duì)每個(gè)鳥巢的個(gè)體最優(yōu)值進(jìn)行局部搜索,從而提高算法精度。

離散的布谷鳥算法流程偽代碼如下:

設(shè)置參數(shù),Pmax、Pmin,最大迭代代數(shù)maxgen,鳥巢個(gè)數(shù),dir=0;

根據(jù)反向?qū)W習(xí)機(jī)制對(duì)鳥巢位置進(jìn)行初始化,并獲取當(dāng)前最優(yōu)鳥巢位置;

For index

獲取當(dāng)前最優(yōu)鳥巢,并替換最差鳥巢位置;

利用基于交叉的萊維飛行產(chǎn)生新的鳥巢位置,獲取當(dāng)前最優(yōu)鳥巢;

采用余弦遞減策略的動(dòng)態(tài)發(fā)現(xiàn)概率,產(chǎn)生各代的發(fā)現(xiàn)概率Pa;

IfPa>rand

對(duì)劣質(zhì)鳥巢進(jìn)行DE變異操作,產(chǎn)生新的鳥巢位置;

End

計(jì)算鳥巢種群適應(yīng)度值fit;

If rand<0.05

隨機(jī)選擇鳥巢變異位置,然后對(duì)兩個(gè)位置“基因”交換位置;

計(jì)算突變后鳥巢的適應(yīng)度值fit_temp,

If fit_temp

更新鳥巢位置為突變后的鳥巢位置

End

End

If 當(dāng)前最優(yōu)等于全局最優(yōu)

dir = dir+1;

End

If dir==5

重復(fù)Empty_Nest操作;

End

End

對(duì)鳥巢種群個(gè)體極值進(jìn)行局部搜索(ILS)操作;

計(jì)算當(dāng)前最優(yōu)鳥巢位置,并替換最差鳥巢位置;

End

2.4 算法復(fù)雜度分析

假設(shè)算法的最大迭代次數(shù)為maxgen,由2.1節(jié)可得計(jì)算該類問題的目標(biāo)函數(shù)的時(shí)間復(fù)雜度為O(sn2),萊維飛行的時(shí)間復(fù)雜度為O(NEST lgn);基于DE變異操作的淘汰劣質(zhì)鳥巢的時(shí)間復(fù)雜度為O(NESTsn);突變產(chǎn)生新鳥巢位置的時(shí)間復(fù)雜度為O(NESTsn);閾值變異操作的時(shí)間復(fù)雜度為O(NESTsn);鄰域搜索的時(shí)間復(fù)雜度為O(sn2(n+1))。由于突變操作、閾值變異操作以及鄰域搜索都是概率發(fā)生的,對(duì)時(shí)間復(fù)雜度的增加影響不大,因此算法的時(shí)間復(fù)雜度為O(maxgen (NEST lgn+ NESTsn+sn2))。可以看出算法計(jì)算量主要與迭代次數(shù)maxgen、鳥巢種群NEST以及算例規(guī)模(工序數(shù)s、工件數(shù)n)有關(guān)。

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

3.1 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證算法、模型的可行性和優(yōu)越性,選取文獻(xiàn)[18]的算例以及在一定規(guī)則下生成的隨機(jī)算例進(jìn)行計(jì)算分析。引用解決調(diào)度問題較為成熟且效果較好的算法APSO[19]、SAGA[20]進(jìn)行算法性能比較。所有實(shí)驗(yàn)均在處理器為Intel(R) Core(TM) i3-2310M @ 2.10 GHz,6 G內(nèi)存的PC機(jī)上采用Matlab R2014a對(duì)算法進(jìn)行編程計(jì)算。

3.2 參數(shù)分析

智能優(yōu)化算法中參數(shù)的設(shè)置對(duì)于算法的尋優(yōu)性能以及收斂速度具有很大的影響,為了選取能夠達(dá)到綜合性能最優(yōu)的參數(shù),本文引入了因子設(shè)計(jì)方法(Factorial Design,FD)[21]來選取DCS的參數(shù)。

DCS算法包含4個(gè)參數(shù):n,pmax,pmin,β,將這4個(gè)參數(shù)設(shè)置為4個(gè)因素,每個(gè)因素含有3個(gè)水平,如表1 所示。為了減少計(jì)算量,提高參數(shù)設(shè)計(jì)效率,本文采用正交設(shè)計(jì)的方法,即只需要32=9組試驗(yàn)即可取得最優(yōu)參數(shù)值。

表1 正交設(shè)計(jì)因素和水平表

正交試驗(yàn)取9組不同規(guī)模隨機(jī)算例獨(dú)立運(yùn)算10次統(tǒng)計(jì)其運(yùn)算結(jié)果。表2給出了所取9個(gè)算例的STD值,并列出了這4個(gè)參數(shù)在9個(gè)不同規(guī)模的隨機(jī)算例計(jì)算結(jié)果中的Mij值,如表3～6所示。其中Mij(i=1,2,3;j=1,2,3,4)表示第j個(gè)參數(shù)的第i個(gè)Level的平均值;STD表示Mij的標(biāo)準(zhǔn)差。對(duì)于每個(gè)參數(shù),若第j列的某個(gè)Mij最小,則說明參數(shù)j取i水平所對(duì)應(yīng)的參數(shù)值最佳。

表2 隨機(jī)算例的正交計(jì)算結(jié)果方差

表3 DCS算法選取不同n值的仿真結(jié)果

表4 DCS算法選取不同Pmax值的仿真結(jié)果

表5 DCS算法選取不同Pmin值的仿真結(jié)果

表6 DCS算法選取不同β值的仿真結(jié)果

STD值反應(yīng)了參數(shù)j對(duì)算法的影響程度,STD越大,說明參數(shù)j的設(shè)置對(duì)算法的尋優(yōu)性能影響越大。根據(jù)表2可以看出,無論算例規(guī)模大小,在大多數(shù)情況下,n、β對(duì)算法影響程度最大。在表3～6中,黑體數(shù)字表示該算例的最小值,對(duì)于大多數(shù)算例,當(dāng)n=30、Pmax=0.8、Pmin=0.2、β=1.5時(shí),算法能夠取得較好的結(jié)果。因此,算法性能分析中,DCS的參數(shù)設(shè)置為n=30、Pmax=0.8、Pmin=0.2、β=1.5。

3.3 性能分析

DCS算法采用基于反向?qū)W習(xí)機(jī)制的初始化方法,使得該算法初始解較優(yōu);利用基于交叉的萊維飛行機(jī)制產(chǎn)生新的鳥巢以及基于PDE的變異策略重構(gòu)鳥巢位置解決連續(xù)問題的布谷鳥搜索算法應(yīng)用到離散問題領(lǐng)域,使得該算法能夠既保持布谷鳥搜索算法的平衡全局搜索與局部搜索的優(yōu)勢(shì),又能夠極好地適用于解決離散型優(yōu)化問題;采用余弦遞減的發(fā)現(xiàn)概率策略,使得該算法能夠在整個(gè)算法進(jìn)程中既保持了前期的快速收斂性,又具有后期強(qiáng)勁的局部搜索能力;添加的突變操作以及代數(shù)閾值操作保證了種群“基因”的完整性以及防止算法陷入局部最優(yōu);而局部搜索策略則保證了算法的搜索精度。

(1) 鄰域搜索策略分析。針對(duì)DCS可能存在的搜索精度不高以及收斂速度慢的缺陷,添加鄰域搜索的改進(jìn)策略,即在DCS迭代過程中針對(duì)每代的最優(yōu)鳥巢位置進(jìn)行鄰域搜索。選擇效率較高的Insert和Interchange局部搜索策略,可以使得DCS具有較強(qiáng)的能力跳出局部最優(yōu)。為了驗(yàn)證以上理論,分別對(duì)采用鄰域搜索策略和不采用鄰域搜索策略的DCS進(jìn)行算例測(cè)試分析,實(shí)驗(yàn)結(jié)果如表7所示,其中Best表示獨(dú)立運(yùn)算20代的最優(yōu)值,Worse表示獨(dú)立運(yùn)算20代的最劣值,Avg表示20代尋優(yōu)的平均值,STD表示20代最優(yōu)值的標(biāo)準(zhǔn)差,avg_dir表示20代最優(yōu)尋優(yōu)代數(shù)的平均值,std_dir表示20代最優(yōu)尋優(yōu)代數(shù)的標(biāo)準(zhǔn)差。

表7示出的10個(gè)算例為隨機(jī)生成的規(guī)模為10道工序10件工件的算例,其中DCS_ IILS表示帶鄰域搜索策略的DCS。由表7可以看出,DCS_ IILS與DCS獨(dú)立運(yùn)算20次求得的最優(yōu)下界都相同,但是從Worse列可以看出,DCS_IILS要明顯優(yōu)于DCS,并且Avg列與STD也都明顯優(yōu)于DCS,這表明添加鄰域搜索策略使得DCS算法的搜索精度有了明顯的改善;從avg_dir列可以看出,DCS_IILS要明顯優(yōu)于DCS,可以證明添加了添加鄰域搜索策略的DCS的收斂速度也同樣得到了明顯的改善。圖3示出了隨機(jī)選擇的Obj02與Obj07的收斂曲線對(duì)比圖,可以更清晰地看出添加了鄰域搜索策略的DCS在收斂速度與精度上的優(yōu)越性。從表7中數(shù)據(jù)以及圖3收斂曲線的對(duì)比可以看出,帶鄰域搜索策略的DCS算法在鳥巢種群處于優(yōu)秀區(qū)域時(shí)采用鄰域搜索可以進(jìn)一步提高算法搜索精度,同時(shí)可以能夠在一定程度上跳出局部最優(yōu)加快算法的收斂速度。

圖3 收斂曲線對(duì)比Fig.3 Comparison of convergence curves

(2) 綜合性能分析。針對(duì)BUHFSP選取文獻(xiàn)[18]的測(cè)試實(shí)例,兩個(gè)算例的已知最優(yōu)下界為301、26。采用本文DCS算法以及基于各工序最小完工時(shí)間的啟發(fā)式規(guī)則的求解方法對(duì)文獻(xiàn)[18]的兩個(gè)實(shí)例進(jìn)行運(yùn)算。為了便于分析算法的結(jié)果,此處取最優(yōu)相對(duì)誤差(ORE)、最差相對(duì)誤差(WRE)和平均相對(duì)誤差(ARE)作為評(píng)價(jià)指標(biāo)。

(13)

(14)

(15)

其中:Cmin和Cmax分別表示20次計(jì)算結(jié)果中得到的最優(yōu)解和最劣解;STDEV表示20次運(yùn)算結(jié)果標(biāo)準(zhǔn)差;Cave表示20次結(jié)果的平均值;C*表示文獻(xiàn)最優(yōu)下界。運(yùn)算結(jié)果如表8、9所示。

表7 變鄰域搜索策略的影響

表8 算例1計(jì)算結(jié)果

表9 算例2計(jì)算結(jié)果

由表8、9中的數(shù)據(jù)可以清晰地看出,用DCS算法求解帶阻塞的混合流水車間調(diào)度問題有一定的優(yōu)勢(shì),該方法求得的最優(yōu)下界都明顯優(yōu)于文獻(xiàn)[18]的結(jié)果。同時(shí),DCS算法無論是最優(yōu)下界還是Cave都優(yōu)于SAGA、APSO、CS等算法,并且DCS的ORE始終不大于其他算法的ORE,DCS算法在尋優(yōu)能力上具有絕對(duì)的優(yōu)勢(shì);通過比較分析STDEV可以看出,DCS算法保持最小,說明該算法在求解穩(wěn)定性上具有一定的優(yōu)勢(shì)。

為了更清晰顯示DCS算法在收斂性和尋優(yōu)能力的優(yōu)越性,繪制算例1、2的收斂曲線如圖4所示。從圖4可以看出,由于DCS算法采用了基于反向?qū)W習(xí)機(jī)制的初始化方法,所以其算法初始解明顯要優(yōu)于另外幾種算法;在算法迭代前期,比如針對(duì)所有算法的前10代,可以明顯看出DCS算法下降速度明顯要優(yōu)于另外幾種算法;而在接下來的迭代過程中,DCS算法還能繼續(xù)尋優(yōu)而不是陷入局部最優(yōu)之中,可見本文改進(jìn)的DCS算法保留了基本CS算法既能保持全局最優(yōu)又能局部尋優(yōu)的優(yōu)勢(shì)。而針對(duì)算法的最終尋優(yōu)結(jié)果,DCS算法在后期始終保持最優(yōu)的狀態(tài),并且綜合表8、9,可以得出DCS算法在尋優(yōu)能力方面具有絕對(duì)的優(yōu)勢(shì)。

3.4 算法性能比較

為了驗(yàn)證本文提出的DCS的優(yōu)越性,選擇隨機(jī)生成不同規(guī)模的算例進(jìn)行算法性能測(cè)試,同時(shí)與APSO和SAGA兩種算法進(jìn)行比較。算例生成機(jī)制如下:

(1) 限定生產(chǎn)工序數(shù),在某個(gè)范圍內(nèi)隨機(jī)產(chǎn)生每道工序并行機(jī)數(shù)量;

(2) 在每道工序隨機(jī)產(chǎn)生一個(gè)比工序的基準(zhǔn)加工時(shí)間BaseTime,然后隨機(jī)生成每臺(tái)并行機(jī)的差異加工時(shí)間RandTime,BaseTime+RandTime即為該工序并行機(jī)的加工時(shí)間。

圖 4 收斂曲線對(duì)比Fig.4 Comparison of convergence curves

利用以上算例生成規(guī)則,分別生成5道工序*10件工件、5道工序*20件工件、10道工序*10件工件、10道工序*20件工件的各10個(gè)算例。采用各算例獨(dú)立20次運(yùn)算結(jié)果的最劣下界(Max)、最優(yōu)下界(Min)、平均值(Mean)、標(biāo)準(zhǔn)差(STD)作為評(píng)價(jià)指標(biāo),由于篇幅有限僅選取幾組不同規(guī)模算例如表10所示。

表10 DCS與其他算法結(jié)果比較

表10中黑體表示3種算法的最優(yōu)結(jié)果?？梢悦黠@看出,本文提出的DCS算法無論是最優(yōu)下界還是最優(yōu)下界平均值都要優(yōu)于SAGA、APSO算法,可見該算法的尋優(yōu)性能要明顯優(yōu)于SAGA、APSO算法;分別分析當(dāng)工件數(shù)相同以及工序數(shù)相同的兩種情況下的最優(yōu)下界的平均值Mean可以看出:當(dāng)工件數(shù)量增加時(shí),DCS的尋優(yōu)能力明顯增強(qiáng);當(dāng)工件相同工序增加,DCS的尋優(yōu)能力增加,但沒有工件增加時(shí)尋優(yōu)能力增強(qiáng)得那么明顯;從STD列可以看出DCS算法針對(duì)不同規(guī)模的算例,總體上也明顯優(yōu)于兩位兩種算法。綜合分析表中不同規(guī)模算例,可以看出隨著算例規(guī)模的增大,DCS算法在尋優(yōu)能力上始終保持絕對(duì)的優(yōu)越性并且隨著模型規(guī)模的增大,最優(yōu)下界的優(yōu)越性也隨之增加。

為了從統(tǒng)計(jì)學(xué)的角度驗(yàn)證本文提出的DCS算法的性能優(yōu)越性,采用方差分析法對(duì)隨機(jī)算例的計(jì)算結(jié)果進(jìn)行進(jìn)一步分析。針對(duì)4組不同規(guī)模的40個(gè)算例獨(dú)立運(yùn)算20次的結(jié)果,計(jì)算不同規(guī)模的最優(yōu)平均相對(duì)誤差

ARE=(Mean-Min)/Mean

(16)

然后對(duì)同一規(guī)模的不同算例取平均值均方差,結(jié)果見表11。

表11 不同算法ARE均值統(tǒng)計(jì)比較

表11中ARE表示該算法求得的解與所有算法求得的最優(yōu)解相比較的平均相對(duì)誤差。很明顯,ARE越小,說明算法的尋優(yōu)性能就越好。STD表示ARE的標(biāo)準(zhǔn)差,STD越小則說明算法的穩(wěn)定性越高。從表11黑體字可以看出,針對(duì)不同規(guī)模的算例,本文提出的DCS算法的最優(yōu)平均相對(duì)誤差的平均值始終最小,且其方差也總是最小,可以判定該算法的尋優(yōu)能力以及尋優(yōu)穩(wěn)定性要優(yōu)于另外兩種經(jīng)典算法。在LSD區(qū)間均值圖中,若兩個(gè)區(qū)間完全沒有重疊,則可以說明這兩個(gè)區(qū)間代表的元素在統(tǒng)計(jì)學(xué)上有顯著的差異。從圖5可以看出DCS算法的置信區(qū)間均值與另外兩種經(jīng)典求解調(diào)度問題的改進(jìn)算法大體上不重疊,說明本文提出的DCS算法在統(tǒng)計(jì)意義上有明顯的優(yōu)勢(shì);同時(shí),從圖5中可以看出DCS算法的區(qū)間相比于另外兩種算法最窄,說明該算法相比于兩種算法具有良好的穩(wěn)定性。

圖5 不同規(guī)模不同算法具有95%置信區(qū)間的LSD區(qū)間均值圖

綜合以上分析,本文提出的DCS算法在求解基于各工序最早完工的差值平移模型的帶阻塞有差速混合流水車間調(diào)度問題時(shí)無論是收斂速度還是尋優(yōu)能力都具有明顯的優(yōu)勢(shì)。

4 結(jié) 論

本文研究了以最小化最大完工時(shí)間為目標(biāo)的帶阻塞有差速混合流水車間調(diào)度問題。該問題基于經(jīng)典流水車間調(diào)度模型考慮了并行機(jī)約束、阻塞約束以及設(shè)備效率差異,建立了基于各工序最早完工的啟發(fā)式規(guī)則的調(diào)度模型。調(diào)度問題作為經(jīng)典的離散組合優(yōu)化問題,而原始CS算法只適用于求解連續(xù)問題。為了使將該算法用于求解調(diào)度類組合優(yōu)化問題,本文提出了一種改進(jìn)的離散布谷鳥搜索算法,采用基于交叉的萊維飛行機(jī)制以及基于排列差分進(jìn)化思想的變異操作將布谷鳥算法離散化,進(jìn)而適用于求解離散排序問題。采用反向?qū)W習(xí)的初始化方法以及動(dòng)態(tài)的發(fā)現(xiàn)概率改善了初始種群的優(yōu)越性及算法的搜索能力,引入最優(yōu)代數(shù)閾值使的算法能夠在一定程度上避免陷入局部最優(yōu),最后通過鄰域搜索,進(jìn)一步提高了算法的搜索精度。通過仿真實(shí)驗(yàn)以及對(duì)算法的分析對(duì)比,驗(yàn)證了所提算法在求解調(diào)度類組合優(yōu)化問題上的有效性與優(yōu)越性。

[1] 王凌,周剛,許燁,等.混合流水線調(diào)度研究進(jìn)展[J].化工自動(dòng)化及儀表,2011 (1):1-8.

[2] GRABOWSKI J,PEMPERA J.Sequencing of jobs in some production system[J].European Journal of Operational Research,2000,125(3):535-550.

[3] FIGIELSKA E.A genetic algorithm and a simulated annealing algorithm combined with column generation technique for solving the problem of scheduling in the hybrid flowshop with additional resources[J].Computers & Industrial Engineering,2009,56(1):142-151.

[4] GUPTA J N D.Two stage hybrid flow shop scheduling problem[J].Asia-Pacific Journal of Operational Research,1988,39(4):359-364.

[5] DENG G,CUI Z,GU X.A discrete artificial bee colony algorithm for the blocking flow shop scheduling problem[C]// 2012 10th World Congress on Intelligent Control and Automation (WCICA).USA:IEEE,2012:518-522.

[6] SAWIK T J.A scheduling algorithm for flexible flow lines with limited intermediate buffers[J].Applied Stochastic Models and Data Analysis,1993,9(2):127-138.

[7] TAVAKKOLI-MOGHADDAM R,SAFAEI N,SASSANI F.A memetic algorithm for the flexible flow line scheduling problem with processor blocking[J].Computers & Operations Research,2009,36(2):402-414.

[8] YAURIMA V,BURTSEVA L,TCHERNYKH A.Hybrid flowshop with unrelated machines,sequence-dependent setup time,availability constraints and limited buffers[J].Computers & Industrial Engineering,2009,56(4):1452-1463.

[9] YANG X S,DEB S.Cuckoo search via Lévy flights[C]// World Congress on Nature & Biologically Inspired Computing,2009.USA:IEEE,2009:210-214.

[10] BURNWAL S,DEB S.Scheduling optimization of flexible manufacturing system using cuckoo search-based approach[J].The International Journal of Advanced Manufacturing Technology,2013,64(5/8):951-959.

[11] 劉長(zhǎng)平,葉春明.求解置換流水車間調(diào)度問題的布谷鳥算法[J].上海理工大學(xué)學(xué)報(bào),2013,35(1):17-20.

[12] REYNOLDS A M,SMITH A D,MENZEL R,etal.Displaced honey bees perform optimal scale-free search flights[J].Ecology,2007,88(8):1955-1961.

[13] 吳昱,李元香,徐星.基于群智能的新型反向混合差分進(jìn)化算法[J].小型微型計(jì)算機(jī)系統(tǒng),2009,30(5):903-907.

[14] DAS S,ABRAHAM A,CHAKRABORTY U K,etal.Differential evolution using a neighborhood-based mutation operator[J].IEEE Transactions on Evolutionary Computation,2009,13(3):526-553.

[15] 徐震浩,李青青,顧幸生.基于 DEPSO 的模糊時(shí)間 ZW 多產(chǎn)品廠間歇調(diào)度[J].控制與決策,2015,30(12):2275-2279.

[16] QIAN B,WANG L,HU R,etal.A DE-based approach to no-wait flow-shop scheduling[J].Computers & Industrial Engineering,2009,57(3):787-805.

[17] SCHIAVINOTTO T,STüTZLE T.A review of metrics on permutations for search landscape analysis[J].Computers & Operations Research,2007,34(10):3143-3153.

[18] 張其亮,陳永生.帶有阻塞限制的混合流水車間調(diào)度問題的混合粒子群求解算法[J].信息與控制,2013,42(2):252-257.

[19] 張頂學(xué),關(guān)治洪,劉新芝.一種動(dòng)態(tài)改變慣性權(quán)重的自適應(yīng)粒子群算法[J].控制與決策,2008,23(11):1253-1257.

[20] JIA Hongyan,HONG H.Research on job-shop scheduling problem based on self-adaptation genetic algorithm[C]// 2010 International Conference on Logistics Systems and Intelligent Management.USA:IEEE,2010: 940-943.

[21] MONTGOMERY D C.Design and Analysis of Experiments[M].USA:John Wiley & Sons,2008.

歡迎訂閱

《華東理工大學(xué)學(xué)報(bào)(自然科學(xué)版)》

地址：上海市梅隴路130號(hào)436信箱 郵編：200237

郵發(fā)代號(hào)：4-382

Discrete Cuckoo Search Algorithm for Blocking and Unrelated Hybrid Flow Shop Scheduling Problem

CHEN Fei-yue, XU Zhen-hao, GU Xing-sheng

(Key Laboratory of Advanced Control and Optimization for Chemical Processes,Ministry of Education,East China University of Science and Technology,Shanghai 200237,China)

For the hybrid flow shop scheduling problem of minimizing the total flow time subject to blocking and differential speed,this paper proposes a discrete cuckoo search algorithm (DCS).By means of the Levy flight and the brood parasite of the cuckoo search algorithm,this paper proposes a crossover strategy based Levy flight mechanism so that the DCS can solve the discrete optimization problems.And then,the dynamic detection probability method is utilized to search for the inferior nest that is further reconstructed by adopting the mutation technique of the permutation-based differential evolution.In order to prevent the DCS from falling into local extremism,this paper introduces the global optimum extreme value algebra as the threshold to rediscover the inferior nests.Finally,the neighborhood search algorithm is used to further improve the search accuracy.The simulation results verify the effectiveness of the proposed algorithm for solving the hybrid flow shop scheduling problems subject to blocking.

cuckoo search algorithm; differential evolution; block; unrelated; minimizing flow time

1006-3080(2017)03-0425-11

10.14135/j.cnki.1006-3080.2017.03.020

2016-09-28

國家自然科學(xué)基金(61104178, 61174040)

陳飛躍(1990-)，男，河南開封人，碩士生，研究方向?yàn)樯a(chǎn)調(diào)度、智能算法。

徐震浩，E-mail: xuzhenhao@ecust.edu.cn

TP301

A