一種求解阻塞流水車間多目標調(diào)度的離散差分進化算法

鄧冠龍, 田廣東, 顧幸生, 張淑寧

(1.魯東大學信息與電氣工程學院,山東 煙臺 264025; 2.吉林大學交通學院,長春 130022;3.華東理工大學化工過程先進控制和優(yōu)化技術(shù)教育部重點實驗室,上海 200237)

?

一種求解阻塞流水車間多目標調(diào)度的離散差分進化算法

鄧冠龍1, 田廣東2, 顧幸生3, 張淑寧1

(1.魯東大學信息與電氣工程學院,山東 煙臺 264025; 2.吉林大學交通學院,長春 130022;3.華東理工大學化工過程先進控制和優(yōu)化技術(shù)教育部重點實驗室,上海 200237)

針對流水車間中產(chǎn)品不存在緩沖區(qū)的多目標優(yōu)化問題,研究了阻塞流水車間的最大完工時間和總流程時間的最小化問題,提出了一種多目標離散差分進化(Multi-objective Discrete Differential Evolution,MDDE)算法搜索Pareto最優(yōu)調(diào)度解。MDDE的變異個體通過非支配解或當前解的鄰域隨機產(chǎn)生,實驗個體通過交叉操作產(chǎn)生,而選擇過程則設計為一種多目標選擇策略。此外,算法還混合了一種基于插入的Pareto局部搜索方法?；跇藴蕼y試算例的數(shù)值仿真實驗表明,MDDE算法獲得的非支配解集在Inverted Generational Distance、Set Coverage和Hypervolume性能指標上均有較好的表現(xiàn)。

進化算法; 生產(chǎn)調(diào)度; 優(yōu)化; 多目標; Pareto

作為車間調(diào)度中的典型難題,流水車間(Flow shop)調(diào)度問題近幾十年來得到了廣泛關注,并隨著近年智能優(yōu)化方法的普遍使用愈加成為研究熱點之一[1-2]。經(jīng)典的流水車間調(diào)度問題并不考慮工件加工完畢后的存儲問題,即假定在任意兩臺機器間有足夠的容量來存儲工件。而在實際生產(chǎn)過程中,若存儲容量不夠并且下個工序的機器并未空閑,則已加工完畢的工件只能滯留在當前機器上而不能離開;若有存儲容量或下個工序的機器已經(jīng)就緒,則工件可以離開當前機器。若任意兩臺機器間的存儲容量為零,則工件極易在機器上阻塞,從而使Flow shop生產(chǎn)受到較大影響,該問題稱為阻塞Flow shop調(diào)度問題(Blocking Flow Shop Scheduling Problem,BFSP)。BFSP廣泛存在于各種生產(chǎn)環(huán)境中,如石油化工、間歇生產(chǎn)、塑料制模、鋼鐵制造等[3-4],因此,其研究具有重要的理論和實際意義。

目前,該問題的研究已有一些成果。文獻[5]證明了以最大完工時間(makespan)為目標時,機器數(shù)大于2的該問題即是NP-難的。Companys等[6]于2007年提出了一種分支定界方法最小化makespan,可求解較小規(guī)模的問題。Bautista等[7]結(jié)合動態(tài)規(guī)劃和分支定界兩種方法,提出了一種有界動態(tài)規(guī)劃算法來求解,針對小規(guī)模問題有較好效果,而對較大規(guī)模問題仍不甚理想。在啟發(fā)式規(guī)則方面,有輪廓適合(Profile Fitting,PF)規(guī)則[8]、Nawaz-Enscore-Ham(NEH)啟發(fā)式規(guī)則[9]、minmax(MM)、MM與NEH的結(jié)合(MME)、PF與NEH的結(jié)合(PFE)[10]。近年來,元啟發(fā)式算法廣泛地應用在調(diào)度領域,涌現(xiàn)了較多的研究成果。針對阻塞Flow shop調(diào)度,相應的算法有Caraffa等[11]提出的遺傳算法、Grabowski等[12]提出的禁忌搜索算法、Wang等[13]提出的混合離散差分進化算法、Ribas等[14]提出的迭代貪婪算法、Wang等[15]提出的混合和聲搜索算法。除上述研究成果之外,國內(nèi)學者也對BFSP做了一些研究工作。張其亮[16]提出了一種混合粒子群算法以最小化該問題的makespan目標,同樣針對makespan目標的方法還有包云等[17]提出的混合和聲搜索方法、郭麗萍等[18]提出的改進螢火蟲算法、韓煒等[19]提出的改進蛙跳算法、李坤等[20]提出的分散變鄰域搜索算法等。而對BFSP的總流程時間(Total Flow Time,TFT)最小化問題,鄧冠龍等[21]提出了一種離散人工蜂群算法,取得了較好的求解效果。此外,謝展鵬等[22]提出的候鳥優(yōu)化算法、張素君[23]提出的混合離散人工蜂群算法均對BFSP的TFT目標優(yōu)化有較好的性能。

上述研究都是針對單一目標進行優(yōu)化,然而,對生產(chǎn)調(diào)度問題而言,優(yōu)化目標可能有多個,且決策者對各個目標的重視程度通常是不可預知的,因此,多目標調(diào)度顯得尤為重要。關于置換流水車間的多目標調(diào)度,已有不少的研究成果,文獻[24]進行了綜述,而針對BFSP的多目標優(yōu)化研究較為少見。本文BFSP的多目標調(diào)度,提出了一種可實現(xiàn)多目標調(diào)度的離散差分進化算法,以makespan和TFT為最小化目標進行Pareto求解。

作為一種新型智能優(yōu)化算法,差分進化算法[25]由于結(jié)構(gòu)簡單、收斂較快、尋優(yōu)性能較好得到了廣泛的應用。在生產(chǎn)調(diào)度領域,研究者較多地采用離散編碼的離散差分進化算法[13,26],取得了較好的效果。因此,本文引入該算法的進化機制,結(jié)合多目標優(yōu)化的特性,設計變異、交叉和選擇操作,提出了一種多目標離散差分進化(Multi-objective Discrete Differential Evolution,MDDE)算法,以期對BFSP的多目標優(yōu)化有效求解。

1 多目標BFSP

BFSP可描述如下:已知有n個工件和m臺機器,每個工件需要依次經(jīng)過第1臺機器、第2臺機器,直到第m臺機器。工件j(j=1,2,…,n) 在第i(i=1,2,…,m) 臺機器Mi上的加工過程記為工序Oji,對應的加工時間為p(j,i)。生產(chǎn)過程中具有阻塞約束,即在任意兩臺機器之間沒有中間存儲,這意味著每個工件一旦開始在某臺機器上加工,則不論該工序是否加工結(jié)束,在下一臺機器可用之前都必須滯留在當前機器上。為使問題描述嚴格,還需做以下假設:

(1) 任意時刻,一臺機器只能加工至多一個工件,且一個工件只能在至多一臺機器上加工;

(2) 工件不允許拆分;

(3) 所有工件和機器在零時刻是可用的;

(4) 加工時間大于零,且是確定的、已知的;

(5) 工件的準備時間、在機器間的轉(zhuǎn)移時間均忽略不計。

對上述問題,工件的加工次序可表示為工件排列π=(π(1),π(2),…,π(n)),其中,π(j)表示工件號 (j=1,2,…,n)。令dπ(j),i表示工件π(j)離開機器Mi的時刻,則最大完工時間makespan和總流程時間TFT可定義如下:

(1) makespan定義為最大完工時間,即最后加工工件的完工時間,也即工件π(n)離開機器Mm的時刻dπ(n),m;

圖1示出了某4個工件3臺機器的BFSP的調(diào)度甘特圖,其中,陰影區(qū)域表示該機器被工件阻塞。圖1給出的是按照工件號1-2-3-4先后加工(即π=(1,2,3,4))的調(diào)度安排,可見,工件的加工次序確定,則makespan和TFT也就確定了(該例子中分別為21和62)。若改變加工次序,則兩個目標函數(shù)均可能發(fā)生變化。值得一提的是,這兩個目標是有沖突的,makespan最小的解并不一定能達到TFT最小,反之亦然。例如,若有兩個調(diào)度解A和B,具有不同的工件次序,且解A的makespan要小于解B,則一種可能的情況是:由于解A中各個工件的阻塞時間要多于解B,使得解A某些工件的完工時間大于解B,從而導致解A的TFT大于解B。

圖1 某BFSP例子調(diào)度甘特圖Fig.1 Gantt chart of a BFSP example

根據(jù)離開時刻dπ(j),i的描述,為計算目標函數(shù),可先計算工件π(1)在各臺機器上的離開時刻,然后計算π(2)的各個離開時刻,依次下去,直到dπ(j),i全部計算完畢。

(1)

(2)

(3)

(4)

(5)

其中,dπ(j),0表示工件π(j)在機器M1上的開始時間。

令f1(π)和f2(π)分別表示π對應的makespan和TFT,則有

(6)

(7)

上述兩個目標函數(shù)可在時間復雜度O(mn)內(nèi)得到。用Π表示所有工件排列的集合,則本文考慮的多目標BFSP為

(8)

由于該問題為多目標問題,本文采用Pareto方法處理,所用算法嘗試搜索問題對應的Pareto最優(yōu)解集合。

2 多目標離散差分進化算法

2.1 概述

標準差分進化算法是一種簡單、有效的群體搜索算法,在連續(xù)函數(shù)優(yōu)化和組合優(yōu)化領域都有較多的應用。算法種群內(nèi)的個體稱為目標個體,種群初始化后,算法進入迭代過程。通過變異操作產(chǎn)生變異個體,再由交叉操作產(chǎn)生試驗個體,然后通過選擇操作更新目標種群。本文考慮的問題為離散的調(diào)度問題,產(chǎn)品序號的排列可直接映射到活躍調(diào)度,因此,采用離散排列π作為種群個體。又由于需要進行多目標優(yōu)化,因而相應的變異、交叉、選擇操作需要進行重新設計,以適應多目標優(yōu)化過程中Pareto非支配解的搜索。為增強算法對Pareto前沿的搜索性能,在算法中混合了一種基于插入的Pareto局部搜索(Insertion-based Pareto Local Search,IPLS)。

2.2 種群初始化

作為性能優(yōu)異的啟發(fā)式規(guī)則,NEH規(guī)則[27]被廣泛應用在流水車間調(diào)度問題中。其步驟如下:

Step 1 按工件在機器上的總加工時間遞減的順序得到n個工件的排列。

Step 2 取前兩個工件調(diào)度使部分最大完工時間最小,得到部分序列。

Step 3 依次將第k(k為3,…,n)個工件插入到部分序列中,有k個可能的位置,選擇使部分最大完工時間最小的位置插入,得到新的部分序列,直到所有工件調(diào)度完成。

該規(guī)則是針對經(jīng)典流水車間的makespan目標提出的性能較好的啟發(fā)式規(guī)則,而針對BFSP,Wang等[28]將Step 1中的工件按照遞增排序,得到了更優(yōu)的NEH_WPT規(guī)則。根據(jù)初步的計算試驗,將Step 1中工件隨機排列,得到的調(diào)度解多樣性更好,且質(zhì)量并無明顯差異,將該方法記為規(guī)則NEH_RAN[21]。

MDDE算法在每一次的迭代中始終維持大小為ps的目標種群,記為PL。在算法進入迭代操作之前,需初始化種群中的每個個體。對于多目標BFSP,本文設計以下初始化種群方式:一個初始個體采用以f1為目標的NEH_WPT產(chǎn)生,一個初始個體采用以f2為目標的NEH_WPT產(chǎn)生,其他ps-2個個體采用NEH_RAN產(chǎn)生。其中,NEH_RAN過程中,目標函數(shù)f3設計如下:

(9)

這樣,初始種群的目標函數(shù)能較均勻地分布在f1和f2的二維平面,從而使得初始種群具有較好性能的同時也兼具多樣性。

由于算法進行多目標搜索,因此算法始終維持一個非支配解集合 (Non-dominated solution set),記為NDS={S1,S2,…,Snb},nb為當前非支配解集合的大小。在初始化種群之后,使用PL的非支配集來初始化NDS。為配合后文的局部搜索方法,NDS中的每個解都做“searched”或“unsearched”的標記,初始化時,NDS中的解都標記為“unsearched”。

2.3 差分進化操作

變異個體的產(chǎn)生方式如下:

(10)

其中:insert(·)表示一次隨機插入移動;pm是變異率,表示變異個體通過NDS產(chǎn)生的概率;r1是[1,nb]間的隨機整數(shù);r2是[1,ps]間的隨機整數(shù)且r≠i;rand是(0,1)范圍內(nèi)的隨機數(shù)。

試驗個體的產(chǎn)生方式如下:

(11)

其中:crossover(·)表示對兩個個體進行交叉操作,并隨機返回一個個體;pc是交叉率,表示實驗個體通過交叉產(chǎn)生的概率,交叉操作選用部分匹配交叉。

選擇操作根據(jù)試驗個體和目標個體的支配關系,并結(jié)合當前NDS進行,方式如下:

(12)

其中:a

2.4 基于插入的Pareto局部搜索

為了克服早熟收斂,增強算法的局部搜索能力,MDDE算法在差分進化操作結(jié)束后嵌入了一種基于插入的Pareto局部搜索IPLS。

IPLS過程在原有解X的基礎上,對某個工件進行插入,若插入操作可獲得支配X的解,則改變工件繼續(xù)進行下去,直到對所有工件的插入都不能再找到更優(yōu)的支配解。IPLS步驟如下:

Step 1 產(chǎn)生一個隨機的排列πr= {πr1,πr2,…,πrn},令i=0,j=1。

Step 2 找出X中產(chǎn)品πrj的位置,將X中產(chǎn)品πrj插入到X的其他n-1個位置上,可得n-1個解,通過計算目標值可得這n-1個解的局部非支配集合(Local Non-Dominated Solution set),記為LNDS。若存在X′∈LNDS且X′

Step3NDS=NDS∪+LNDS,若NDS中有新解加入,則將其標記為“unsearched”。

Step4 若i

上述過程可持續(xù)搜索支配X的解X′,直到插入鄰域不再能找到X′為止。圖2給出了某初始解X經(jīng)擾動后執(zhí)行IPLS的搜索過程示意圖。

在MDDE中嵌入IPLS的策略如下:

Step1 若非支配集合NDS中存在標記為“unsearched”的個體(假設為Sk),則令X=Sk,轉(zhuǎn)Step3。

Step2 隨機選擇NDS中一個個體(假設為Sk),令X=Sk,對X進行d次隨機插入操作(即擾動),再對X執(zhí)行IPLS。

Step3 對X執(zhí)行IPLS,若IPLS未能改變X,則將對應的NDS中解Sk標記為“searched”。

由于集合NDS中的解通常具有較好的性能,但在進化后期很可能是局部最優(yōu),因此進行d次隨機插入操作可得到鄰域解,該鄰域解可保持大部分解結(jié)構(gòu),同時又可能跳出了局部最優(yōu)。

圖2 基于插入的Pareto局部搜索示意圖Fig.2 Chart of insertion-based Pareto local search

2.5 MDDE算法流程

在給出了MDDE的種群初始化、差分進化操作和嵌入的局部搜索方法之后,整個算法流程便可描述如下:

Step 1 初始化算法參數(shù),初始化目標種群PL和非支配解集NDS。

Step 2 變異操作產(chǎn)生變異種群,交叉操作產(chǎn)生實驗種群、選擇操作更新目標種群,必要時更新NDS。

Step 3 執(zhí)行算法中嵌入IPLS的策略。

算法涉及的參數(shù)有:種群大小ps、變異概率pm、交叉概率pc、擾動規(guī)模d。

3 仿真實驗

3.1 算法運行設置

為了驗證MDDE算法的效果,仿真實驗采用Taillard給出的算例[29],使用其中的90個算例,工件數(shù)為20～100,機器數(shù)為5～20。本文所有算法均采用C++語言編程實現(xiàn),運行環(huán)境為4 GB內(nèi)存的Intel(R) Core(TM) i7-2600 CPU @3.06 GHz的計算機。

與單目標優(yōu)化不同,多目標優(yōu)化算法找到的是一個非支配解的集合。因此,算法效果的評價方式有多種,本文使用Inverted Generational Distance (IGD)[30]、Set Coverage[31]、Hypervolume[32]指標。

(1) IGD。假設P*為已知的某個參考解集,A為某算法找到的非支配解集。解x∈A和解y∈P*的歸一化歐氏距離為

(13)

計算A的IGD值為

(14)

可見,IGD是A到P*的所有解的最短距離的平均,該指標可反映A的多樣性和收斂性。

(2) Set Coverage。假設A和B是兩個非支配解集,Set Coverage 計算值為

(15)

可見,C(A,B)表示B中解被A中某個解支配的比例,若C(A,B)較大而C(B,A)較小,表明在某種意義上A要優(yōu)于B。

(3) Hypervolume。假設A是某非支配解集,參考點記為Ref=(ref1,ref2,…,refr),則解集A的Hypervolume指標定義為由解集A中所有點與參考點在目標空間中圍成的超立方體的體積,表示為

(16)

其中,等式右邊表示被X支配而不被參考點Ref支配的空間圍成的超立方體的勒貝格測度。

3.2 算法參數(shù)設置

MDDE算法共有4個參數(shù),其中,種群規(guī)模越大,算法的計算代價也越大,當然,算法求解效果相應地也會較好。通過初步實驗,對產(chǎn)品數(shù)為20～100的算例,取值在10至20間是較合適的,因此本文取ps=15。而對另外3個參數(shù),采用統(tǒng)計分析方法確定其取值。具體地,變異概率pm取值為0.2、0.5、0.8,變異概率pc取值為0.2、0.5、0.8,擾動規(guī)模d取值為2、6、10,這樣構(gòu)成27種組合。選擇Ta21、Ta51、Ta81共3個算例,每個算例運行10次,算法終止條件為30mnms,將IGD指標值作為響應值,得到27×3= 810個數(shù)據(jù)點,對數(shù)據(jù)做方差分析可得到3個參數(shù)取不同值時IGD響應的均值和95%置信區(qū)間圖,結(jié)果見圖3。

圖3的結(jié)果顯示,參數(shù)pm取不同值時對算法性能影響較小,取值為0.5或其他值都可以接受。而參數(shù)d和pc對算法性能有較大的影響,d取值為6時要明顯優(yōu)于2和10,參數(shù)pc取值為0.8時要明顯優(yōu)于0.2和0.5。本文MDDE參數(shù)選擇為:ps=15,pm=0.5,pc=0.8,d=6。

圖3 參數(shù)取不同值時帶LSD區(qū)間的均值圖Fig.3 Means plot with 95% LSD intervals for different values of the parameters

3.3 MDDE、HDE、BMSA的性能比較

為驗證算法效果,將MDDE與混合差分進化[33](Hybrid Differential Evolution,HDE)算法和多目標多初始點模擬退火(Bi-objective Multi-start Simulated Annealing,BMSA)算法[34]進行比較,為使比較相對公平,算法參數(shù)設置和原文保持一致。每個算法對每個算例運行10次,終止條件為30mnms。為統(tǒng)計方便,將3個算法10次運行得到的非支配解集合并,作為算法獲得的非支配解集A1、A2、A3;將解集A1、A2、A3的最大目標值作為參考點的目標值,用于計算Hypervolume;并將A1、A2、A3合并,得到的非支配解集作為參考解集P*,用于計算IGD。由于算例較多,按照算例規(guī)模,將IGD、Set Coverage和Hypervolume的計算結(jié)果求平均值后分別列于表1、表2和表3。

表1 不同規(guī)模算例下算法的IGD值Table 1 IGD values obtained by the algorithms for instances with different sizes

表2 不同規(guī)模算例下算法的Set Coverage值Table 2 Set Coverage values of the algorithms for instances with different sizes

表3 不同規(guī)模算例下算法的Hypervolume值Table 3 Hypervolume values of the algorithms for instances with different sizes

表1給出了3種算法在各種規(guī)模算例下獲得的IGD值。根據(jù)IGD值的定義,該值越小意味著算法找到的非支配解集在收斂性和多樣性上越接近參考解集?？梢?對20個工件的較小規(guī)模,BMSA所得IGD值為3種算法中最好,MDDE和BMSA接近,而HDE要明顯差于另外兩種算法。而對工件數(shù)為50和100的中大規(guī)模算例,MDDE所得IGD值具有明顯的優(yōu)勢。由IGD值接近零可知,MDDE所得解集非常接近參考解集。從表1還可以看出,在IGD指標上,HDE和BMSA兩者之間總體上效果相當,對于小規(guī)模的算例,BMSA表現(xiàn)優(yōu)于HDE,但對部分中大規(guī)模的算例,HDE表現(xiàn)又優(yōu)于BMSA。從IGD總體平均值上看,BMSA比HDE略有優(yōu)勢。

表2從Set Coverage的角度將MDDE與HDE、BMSA進行了比較?？梢钥吹?在工件數(shù)為50和100的算例上,MDDE的Set Coverage表現(xiàn)分別優(yōu)于HDE和BMSA算法。一個有趣的結(jié)果是工件數(shù)為20的算例,C(A,B)較大而C(B,A)較小,表明HDE獲得的解在該指標上要優(yōu)于MDDE；C(A,C)和C(C,A)相當接近,表明MDDE和BMSA在這一指標上并無明顯差異。從Set Coverage平均值上看,MDDE算法總體上獲得了優(yōu)于另外兩種算法的結(jié)果。

表3從Hypervolume的角度對這3種算法進行了比較?？梢?對于小規(guī)模的算例,HDE算法要稍好于MDDE算法,MDDE算法和BMSA算法效果相當。而對于中大規(guī)模的算例,MDDE算法要明顯優(yōu)于另外兩者。在總體平均值上,MDDE算法獲得的值(1 610 655.6)要優(yōu)于HDE算法和BMSA算法的值(1 221 991.5和873 352.4)。這一結(jié)果說明了MDDE算法的性能優(yōu)勢。

分析上述結(jié)果,對較小規(guī)模(工件數(shù)為20)的算例,MDDE算法和HDE算法優(yōu)勢相當,而與BMSA算法相比,優(yōu)勢也并不顯著。我們認為原因是這些算例規(guī)模不大,相對容易求解。此外,在給定的計算時間內(nèi)這幾種算法都能找到較好的非支配解集,再者算法運行的隨機性對結(jié)果有一定影響。而對工件數(shù)為50和100的中大規(guī)模算例,算例本身求解難度較大,在給定的計算時間內(nèi)算法的性能差異更能體現(xiàn),對MDDE算法,本文設計的多目標選擇策略和Pareto局部搜索方法的優(yōu)勢得以體現(xiàn),因此,MDDE算法的結(jié)果要明顯優(yōu)于另兩種算法。

4 結(jié) 論

針對流水車間調(diào)度問題中存在的阻塞特性以及目前多目標優(yōu)化的現(xiàn)狀,研究了一類阻塞約束下的流水車間多目標調(diào)度問題?？紤]到最大完工時間和總流程時間對生產(chǎn)過程有重要影響,以兩者為最小化目標,提出了一種新型的多目標離散差分進化算法進行求解。算法通過非支配解或當前解的鄰域產(chǎn)生變異種群,并利用部分匹配交叉產(chǎn)生試驗種群,通過特殊設計的多目標選擇策略實現(xiàn)了選擇操作,在每一迭代中,算法還混合了一種基于插入的Pareto局部搜索方法,增強了對解空間的探索與開發(fā)。仿真實驗結(jié)果表明,本文提出的算法能較好地求解各種規(guī)模下的阻塞流水車間多目標調(diào)度問題,與其他算法相比,該算法獲得的非支配解集在IGD、Set Coverage和Hypervolume性能指標上均有較好的表現(xiàn),特別是在中大規(guī)模的問題上,算法具有更顯著的效果。

[1] 王圣堯,王凌,許燁,等.求解混合流水車間調(diào)度問題的分布估計算法[J].自動化學報,2012,38(3):437-443.

[2] 徐建有,顧幸生.基于新鄰域結(jié)構(gòu)的Memetic算法求解流水車間調(diào)度問題[J].控制與決策,2012,27(12):1781-1786.

[3] MARTINEZ S,PERES S D,GUERET C,etal.Complexity of flowshop scheduling problems with a new blocking constraint[J].European Journal of Operational Research,2006,169(3):855-864.

[4] GONG Hua,TANG Lixin,DUIN C W.A two-stage flow shop scheduling problem on a batching machine and a discrete machine with blocking and shared setup times[J].Computers and Operations Research,2010,37(5):960-969.

[5] HALL N G,SRISKANDARAJAH C.A survey of machine scheduling problems with blocking and no-wait in process[J].Operations Research,1996,44(3):510-525.

[6] COMPANYS R,MATEO M.Different behaviour of a double branch-and-bound algorithm on Fm/prmu/Cmax and Fm/block/Cmax problems[J].Computers and Operations Research,2007,34(4):938-953.

[7] BAUTISTA J,CANO A,COMPANYS R.Solving the Fm/block/Cmax problem using bounded dynamic programming[J].Engineering Applications of Artificial Intelligence,2012,25(6):1235-1245.

[8] MCCORMICK S T,PINEDO M L,SHENKER S.Sequencing in an assembly line with blocking to minimize cycle time[J].Operations Research,1989,37(6):925-936.

[9] LEISTEN R.Flowshop sequencing problems with limited buffer storage[J].International Journal of Production Research,1990,28(11):2085-2100.

[10] RONCONI D P.A note on constructive heuristics for the flowshop problem with blocking[J].International Journal of Production Economics,2004,87(1):39-48.

[11] CARAFFA V,IANES S,BAGCHI T P.Minimizing makespan in a blocking flowshop using genetic algorithms[J].International Journal of Production Economics,2001,70(2):101-115.

[12] GRABOWSKI J,PEMPERA J.The permutation flowshop problem with blocking:A tabu search approach[J].OMEGA,2007,35(3):302-311.

[13] WANG Ling,PAN Quanke,SUGANTHAN P N,etal.A novel hybrid discrete differential evolution algorithm for blocking flowshop scheduling problems[J].Computers and Operations Research,2010,37(3):509-520.

[14] RIBAS I,COMPANYS R,TORT-MARTORELL X.An iterated greedy algorithm for the flowshop scheduling with blocking[J].OMEGA,2011,39(3):293-301.

[15] WANG Ling,PAN Quanke,TASGETIREN M F.A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem[J].Computers and Industrial Engineering,2011,61(1):76-83.

[16] 張其亮,陳永生.有效的混合粒子群算法求解阻塞流水車間調(diào)度問題[J].計算機集成制造系統(tǒng),2012,18(12):2689-2695.

[17] 包云,姜華,鄭麗萍.基于和聲搜索的阻塞流水車間調(diào)度問題的算法優(yōu)化[J].計算機工程與科學,2013,35(7):108-112.

[18] 郭麗萍,李向濤,谷文祥,等.改進的螢火蟲算法求解阻塞流水線調(diào)度問題[J].智能系統(tǒng)學報,2013,8(1):33-38.

[19] 韓煒,崔喆,顧幸生.基于新型蛙跳算法的帶阻塞流水線調(diào)度問題[J].華東理工大學學報(自然科學版),2014,40(1):86-90.

[20] 李坤,王亞超,田慧欣.一種求解阻塞流水車間調(diào)度問題的分散變鄰域搜索算法[J].系統(tǒng)工程,2014,32(9):130-136.

[21] DENG Guanlong,XU Zhenhao,GU Xingsheng.A discrete artificial bee colony algorithm for minimizing the total flow time in the blocking flow shop scheduling[J].Chinese Journal of Chemical Engineering,2012,20(6):1067-1073.

[22] 謝展鵬,賈艷,張超勇,等.基于候鳥優(yōu)化算法的阻塞流水車間調(diào)度問題[J].計算機集成制造系統(tǒng),2015,21(8):2099-2107.

[23] 張素君,顧幸生.基于混合離散人工蜂群算法的阻塞flow shop調(diào)度[J].華東理工大學學報(自然科學版),2015,41(3):357-363.

[24] MEHMET M Y,BETUL Y.Multi-objective permutation flow shop scheduling problem:Literature review,classification and current trends[J].OMEGA,2014,45(4):119-134.

[25] STORN R,PRICE K.Differential evolution:A simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization,1997,11(4):341-359.

[26] DENG Guanlong,GU Xingsheng.A hybrid discrete diffe-rential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion[J].Computers and Operations Research,2012,39(9):2152-2160.

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

[28] WANG Ling,PAN Quanke,TASGETIREN M F.Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms[J].Expert Systems with Applications,2010,37(12):7929-7936.

[29] TAILLARD E.Benchmarks for basic scheduling-problems[J].European Journal of Operations Research,1993,64(2):275-285.

[30] COELLO C,CORTéS N.Solving multiobjective optimization problems using an artificial immune system[J].Genetic Programming and Evolvable Machines,2005,6(2):163-190.

[31] ZITZLER E,DEB K,THIELE L.Comparison of multiobjective evolutionary algorithms:Empirical results[J].Evolutionary Computation,2000,8(2):173-195.

[32] ZITZLER E,THIELE L,LAUMANNS M,etal.Performance assessment of multiobjective optimizers:An analysis and review[J].IEEE Trans on Evolutionary Computation,2003,7(2):117-132.

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

[34] LIN S W,YING K C.Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm[J].Computers & Operations Research,2013,40(6):1625-1647.

A Discrete Differential Evolution Algorithm for Multi-objective Scheduling in Blocking Flow Shop

DENG Guan-long1, TIAN Guang-dong2, GU Xing-sheng3, ZHANG Shu-ning1

(1.School of Information and Electrical Engineering,Ludong University,Yantai 264025,Shandong,China;2.Transportation College,Jilin University,Changchun 130022,China;3.Key Laboratory of Advanced Control and Optimization for Chemical Processes,Ministry of Education, East China University of Science and Technology,Shanghai 200237,China)

This paper considers the problem of the multi-objective scheduling with makespan and total flow time minimizations for blocking flow shop.A multi-objective discrete differential evolution (MDDE) is proposed for searching alternative Pareto solutions,in which mutant individual is obtained by Pareto front solution or incumbent solution,and trial individual is generated by crossover operation while selection process is designed as a multi-objective selection strategy.Moreover,an insertion-based Pareto local search procedure is hybridized in this algorithm.The computational experiments on a bunch of instances for blocking flow shop show that the proposed algorithm can attain better non-dominated solution set in term of three performance measures,i.e.,Inverted Generational Distance,Set Coverage,and Hypervolume.

evolution algorithm; production scheduling; optimization; multi-objective; Pareto

1006-3080(2016)05-0682-08

10.14135/j.cnki.1006-3080.2016.05.015

2015-12-24

國家自然科學基金(61403180,51405075,61573144);山東省優(yōu)秀中青年科學家科研獎勵基金(BS2015DX018)

鄧冠龍(1985-),男,湖南郴州人,講師,博士,從事生產(chǎn)計劃與調(diào)度、智能優(yōu)化算法等研究。

TP18

A