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

陳飛躍, 徐震浩, 顧幸生

(華東理工大學化工過程先進控制和優化技術教育部重點實驗室,上海 200237)

?

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

陳飛躍, 徐震浩, 顧幸生

(華東理工大學化工過程先進控制和優化技術教育部重點實驗室,上海 200237)

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

布谷鳥搜索算法; 差分進化; 阻塞; 差速; 最小完成時間

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

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

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

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

1 問題描述

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

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

一般對帶阻塞有差速混合流水車間調度生產過程作如下假設:

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

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

(3) 工件間沒有優先級;

(4) 一臺機器不能同時加工多個工件,一個工件不能在同一時間被多臺機器加工;

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

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

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

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

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

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

minCmax

(1)

s.t.

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

(2)

(3)

其中:式(1)為問題的目標函數;式(2)表示某一工件的某一工序只能由一臺機器進行加工;式(3)表示某一時刻某一機器只能加工某一工件;式(4)、式(5)表示有差速并行機并且帶阻塞限制的開工時間以及完工時間的約束關系。

2 改進的離散布谷鳥算法

2.1 概述

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

2.2 算法思路

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

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

1≤i≤n,1≤xi≤n

(6)

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

解碼可分為3步:

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

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

(3) 若有工序存在本工序完工時間相同的情況,則隨機選擇一臺機器進行該工序的加工。

2.2.2 基于反向學習的初始化 隨機產生的初始鳥巢可能會在整個解空間中分布不均勻,為了提高初始鳥巢的質量,同時保證初始鳥巢的均勻性,引入基于反向學習的機制[13],即對初始序列作xi=1+n-xi變換,然后分別計算其適應度值,選取較優的個體作為初始鳥巢,從而保證初始化種群的優越性及提高收斂速度。

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

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

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

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

根據以上3個步驟,對所有工件完成加工,求得最大完工時間。

2.3 算法流程

基本布谷鳥算法只適用于求解連續型優化問題,而生產調度屬于組合優化問題,因此借鑒遺傳算法的交叉思想以及基于排列的差分進化變異思想對CS算法進行離散化。

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

(7)

(8)

從而新鳥巢的位置為

?L(β)

(9)

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

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

(10)

其中:Pmax、Pmin表示最大、最小發現概率;i表示當前迭代代數;maxgen表示最大迭代代數。

引入該策略,可以使得算法在計算前期能夠在保證全局搜索能力的前提下快速收斂到非劣解,隨著迭代代數的增加,種群個體的質量逐漸提高;到尋優后期,Pa隨著代數的增加而減小,有利于算法進行更精確的局部搜索。通過測試驗證表明,動態發現概率有效地提高了算法的收斂速度并改善了搜索能力。

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

(11)

(12)

其中:r1、r2為[1,N]內與i不相等的隨機整數,且兩兩不相等;F為縮放因子,為了增加增強算法的自適應能力,本文取非線性遞增的取值策略,從而保證算法在運算初期劣解與當前最優解差異較大時適當地控制擾動,在算法后期適當地增大擾動,動態調節縮放因子F,從而可以有效平衡全局搜索與局部搜索。F的取值如式(12)所示,其中Fl=0.1,Fh=0.9,從而可以保證F在[0.1,0.9]之間隨著迭代代數的變化而變化。通過DE變異操作,可以有效地補充丟失的有效“基因”而維持鳥巢種群的多樣性。

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

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

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

設置參數,Pmax、Pmin,最大迭代代數maxgen,鳥巢個數,dir=0;

根據反向學習機制對鳥巢位置進行初始化,并獲取當前最優鳥巢位置;

For index

獲取當前最優鳥巢,并替換最差鳥巢位置;

利用基于交叉的萊維飛行產生新的鳥巢位置,獲取當前最優鳥巢;

采用余弦遞減策略的動態發現概率,產生各代的發現概率Pa;

IfPa>rand

對劣質鳥巢進行DE變異操作,產生新的鳥巢位置;

End

計算鳥巢種群適應度值fit;

If rand<0.05

隨機選擇鳥巢變異位置,然后對兩個位置“基因”交換位置;

計算突變后鳥巢的適應度值fit_temp,

If fit_temp

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

End

End

If 當前最優等于全局最優

dir = dir+1;

End

If dir==5

重復Empty_Nest操作;

End

End

對鳥巢種群個體極值進行局部搜索(ILS)操作;

計算當前最優鳥巢位置,并替換最差鳥巢位置;

End

2.4 算法復雜度分析

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

3 仿真實驗

3.1 實驗設置

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

3.2 參數分析

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

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

表1 正交設計因素和水平表

正交試驗取9組不同規模隨機算例獨立運算10次統計其運算結果。表2給出了所取9個算例的STD值,并列出了這4個參數在9個不同規模的隨機算例計算結果中的Mij值,如表3～6所示。其中Mij(i=1,2,3;j=1,2,3,4)表示第j個參數的第i個Level的平均值;STD表示Mij的標準差。對于每個參數,若第j列的某個Mij最小,則說明參數j取i水平所對應的參數值最佳。

表2 隨機算例的正交計算結果方差

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

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

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

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

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

3.3 性能分析

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

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

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

圖3 收斂曲線對比Fig.3 Comparison of convergence curves

(2) 綜合性能分析。針對BUHFSP選取文獻[18]的測試實例,兩個算例的已知最優下界為301、26。采用本文DCS算法以及基于各工序最小完工時間的啟發式規則的求解方法對文獻[18]的兩個實例進行運算。為了便于分析算法的結果,此處取最優相對誤差(ORE)、最差相對誤差(WRE)和平均相對誤差(ARE)作為評價指標。

(13)

(14)

(15)

其中:Cmin和Cmax分別表示20次計算結果中得到的最優解和最劣解;STDEV表示20次運算結果標準差;Cave表示20次結果的平均值;C*表示文獻最優下界。運算結果如表8、9所示。

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

表8 算例1計算結果

表9 算例2計算結果

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

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

3.4 算法性能比較

為了驗證本文提出的DCS的優越性,選擇隨機生成不同規模的算例進行算法性能測試,同時與APSO和SAGA兩種算法進行比較。算例生成機制如下:

(1) 限定生產工序數,在某個范圍內隨機產生每道工序并行機數量;

(2) 在每道工序隨機產生一個比工序的基準加工時間BaseTime,然后隨機生成每臺并行機的差異加工時間RandTime,BaseTime+RandTime即為該工序并行機的加工時間。

圖 4 收斂曲線對比Fig.4 Comparison of convergence curves

利用以上算例生成規則,分別生成5道工序*10件工件、5道工序*20件工件、10道工序*10件工件、10道工序*20件工件的各10個算例。采用各算例獨立20次運算結果的最劣下界(Max)、最優下界(Min)、平均值(Mean)、標準差(STD)作為評價指標,由于篇幅有限僅選取幾組不同規模算例如表10所示。

表10 DCS與其他算法結果比較

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

為了從統計學的角度驗證本文提出的DCS算法的性能優越性,采用方差分析法對隨機算例的計算結果進行進一步分析。針對4組不同規模的40個算例獨立運算20次的結果,計算不同規模的最優平均相對誤差

ARE=(Mean-Min)/Mean

(16)

然后對同一規模的不同算例取平均值均方差,結果見表11。

表11 不同算法ARE均值統計比較

表11中ARE表示該算法求得的解與所有算法求得的最優解相比較的平均相對誤差。很明顯,ARE越小,說明算法的尋優性能就越好。STD表示ARE的標準差,STD越小則說明算法的穩定性越高。從表11黑體字可以看出,針對不同規模的算例,本文提出的DCS算法的最優平均相對誤差的平均值始終最小,且其方差也總是最小,可以判定該算法的尋優能力以及尋優穩定性要優于另外兩種經典算法。在LSD區間均值圖中,若兩個區間完全沒有重疊,則可以說明這兩個區間代表的元素在統計學上有顯著的差異。從圖5可以看出DCS算法的置信區間均值與另外兩種經典求解調度問題的改進算法大體上不重疊,說明本文提出的DCS算法在統計意義上有明顯的優勢;同時,從圖5中可以看出DCS算法的區間相比于另外兩種算法最窄,說明該算法相比于兩種算法具有良好的穩定性。

圖5 不同規模不同算法具有95%置信區間的LSD區間均值圖

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

4 結 論

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

[1] 王凌,周剛,許燁,等.混合流水線調度研究進展[J].化工自動化及儀表,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] 劉長平,葉春明.求解置換流水車間調度問題的布谷鳥算法[J].上海理工大學學報,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].小型微型計算機系統,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 的模糊時間 ZW 多產品廠間歇調度[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] 張其亮,陳永生.帶有阻塞限制的混合流水車間調度問題的混合粒子群求解算法[J].信息與控制,2013,42(2):252-257.

[19] 張頂學,關治洪,劉新芝.一種動態改變慣性權重的自適應粒子群算法[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.

歡迎訂閱

《華東理工大學學報(自然科學版)》

地址：上海市梅隴路130號436信箱 郵編：200237

郵發代號：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

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

陳飛躍(1990-)，男，河南開封人，碩士生，研究方向為生產調度、智能算法。

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

TP301

A