具有總能耗約束的柔性作業(yè)車間調(diào)度問題研究

雷德明 楊冬婧

柔性作業(yè)車間調(diào)度問題(Flexible job shop scheduling problem,FJSP)廣泛存在于汽車裝配、紡織、化工生產(chǎn)和半導(dǎo)體制造等制造過程和行業(yè)中,自Bruker等在1990年的開創(chuàng)性工作[1]之后,FJSP的研究受到廣泛關(guān)注,取得了很大進(jìn)展[1?27].

由于FJSP的高度復(fù)雜性,精確算法難以在合理的時間內(nèi)對其求解,使得智能算法成為解決FJSP的主要手段,智能算法已成功應(yīng)用于各類FJSP的求解,其中關(guān)于多目標(biāo)FJSP,早期的工作為Kacem等[2]提出的基于遺傳算法和局部方法的混合算法,在此之后,研究者大量應(yīng)用GA(Genetic algorithm)[2?9]、粒子群算法[10?11]、和聲搜索算法[12]、人工蜂群算法[13]、禁忌搜索[14?15]、變鄰域搜索[16]、蛙跳算法[17]和分布估計算法[18]等求解FJSP.

近些年,低碳制造和低碳生產(chǎn)調(diào)度受到工業(yè)界和學(xué)術(shù)界的廣泛關(guān)注,其中關(guān)于低碳FJSP,Tang等[19]考慮了FJSP的能耗并運用遺傳模擬退火算法求解.Liu等[20]運用GA求解雙目標(biāo)低碳FJSP.He等[21]提出一種節(jié)能優(yōu)化算法,它通過機床選擇減少機器加工能耗和操作序列調(diào)整減少機器閑置時的能源浪費.Zhang等[22]設(shè)計結(jié)合改進(jìn)局部搜索的多目標(biāo)GA以解決低碳FJSP.蔣增強等[23]提出了基于血緣變異的改進(jìn)非劣排序遺傳算法(Non-dominated sorting genetic algorithm-II,NSGA-II[28]).唐立力[24]給出一種改進(jìn)型候鳥優(yōu)化算法.Yin等[25]運用多目標(biāo)GA解決了具有產(chǎn)能、能源效率和噪聲減少等目標(biāo)的FJSP.文獻(xiàn)[26?27]分別利用一種新型蛙跳算法和一種新的教學(xué)優(yōu)化算法求解低碳FJSP.

盡管低碳FJSP的研究取得了較大進(jìn)展,但其研究仍不夠深入,有些問題的研究還未引起研究者的重視,例如,具有總能耗約束的FJSP,在該問題中,總能耗不是目標(biāo)函數(shù),無需最優(yōu)化,總能耗只需不超過給定的閾值即可,能耗約束的加入,產(chǎn)生了如下幾個新特征:1)總能耗約束不是總能得到滿足,即智能算法的解所具有的總能耗經(jīng)常超過給定的閾值.2)總能耗與機器分配和工件加工順序密切相關(guān),其閾值難以事先確定.3)由于以上兩個特點,需要利用新原理和策略比較問題的解并更新非劣解集.

如上所述,多種智能算法在FJSP和低碳FJSP方面都具有成功的應(yīng)用,不過,作為一種模擬社會政治行為的帝國競爭算法(Imperialist competitive algorithm,ICA)[29],盡管已在設(shè)備布局[30?31]、調(diào)度[32?37]、裝配線平衡[38?40]、旅行商問題[41]等方面具有一些成果,但I(xiàn)CA較少用于FJSP和低碳FJSP的求解[36?37].根據(jù)文獻(xiàn)[29],ICA既具有較強的鄰域搜索能力,又是有效的全局優(yōu)化方法,且結(jié)構(gòu)靈活,這些特點表明ICA在求解FJSP和低碳FJSP方面具有不同其他算法如GA的優(yōu)勢,如不必像GA那樣要加強局部搜索才能實現(xiàn)全局搜索與局部搜索的協(xié)調(diào),因此,有必要研究ICA在FJSP和低碳FJSP方面的應(yīng)用.

本文研究具有總能耗約束的FJSP,由于該問題的能耗約束經(jīng)常無法得到滿足,為了有效地解決問題,首先將問題轉(zhuǎn)化所有約束都可滿足的三目標(biāo)FJSP,以簡化對能耗約束的處理,同時擴(kuò)大搜索區(qū)域,然后直接優(yōu)化原問題,以進(jìn)一步改進(jìn)第一階段的搜索結(jié)果,為此,設(shè)計基于ICA和VNS(Variable neighborhood search)的雙階段算法,先應(yīng)用ICA產(chǎn)生一定數(shù)量的可行解,然后運用VNS對可行解改進(jìn),其中,ICA不直接求解原問題,而是優(yōu)化具有總能耗、總延遲時間和Makespan的三目標(biāo)FJSP;而VNS則從第一階段獲得的解出發(fā),對原問題求解,并通過周期性更新當(dāng)前解增強VNS的探索能力和它本身較強的局部搜索能力,不斷提高解的質(zhì)量.通過大量仿真實驗,驗證所得閾值的合理性和算法的搜索性能.

1 問題描述

具有能耗約束的FJSP描述如下:存在工件集J={J1,J2,···,Jn}和機器集M={M1,M2,···,Mm}.工件Ji具有hi道工序,工序oij為工件Ji的第j道工序,該工序可由相容機器集Sij中的任何一臺機器加工,Sij?M.機器Mk具有兩種模式:加工模式和空閑模式.Ek,SEk分別表示機器Mk在加工模式和空閑模式時單位時間的能耗.

存在一些與機器和工件相關(guān)的約束,包括同一時刻一臺機器最多只加工一道工序,同一時刻一個工件最多只能在一臺機器上加工,工序加工不能中斷準(zhǔn)備時間和清理時間包含在加工時間內(nèi)等.

另外,還考慮總能耗約束TEC≤QEC,式中,

其中,TEC表示總能耗,yijk(t)為二進(jìn)制量,如果在時刻t機器Mk∈Sij處于加工模式,則yijk(t)=1;否則,yijk(t)=0;如果機器Mk在時刻t處于空閑,則zk(t)=1;否則,zk(t)=0.QEC為總能耗閾值.Cmax表示最大完成時間.

問題包括調(diào)度子問題和機器分配子問題.問題的目的在于在所有約束滿足的條件下同時最小化如下兩個目標(biāo)函數(shù).

其中,Ci,Di表示工件Ji的完成時間和交貨期,目標(biāo)函數(shù)f1,f2分別為Makespan和總延遲時間.

對于多目標(biāo)優(yōu)化問題,假設(shè)其目標(biāo)總數(shù)為G且都是最小化目標(biāo),其最優(yōu)解不再只是單獨一個解,而是一組解的集合,且需要通過比較所有解才能確定最優(yōu)解集.通常,要用到如下幾個概念:對于解x,y,如果對于?i∈{1,2,···,G},fi(x)≤fi(y);且?i∈{1,2,···,G},fi(x)

2 求解具有總能耗約束的FJSP的雙階段算法

對于所研究的FJSP,需要確定合適的能耗閾值,同時在所有約束條件滿足的情況下,最優(yōu)化兩個目標(biāo)函數(shù),為了完成這兩個任務(wù),提出一種基于ICA和VNS的雙階段算法.

2.1 編碼

針對具有n個工件和m臺機器的FJSP,通常利用調(diào)度串 [(θ1,r1),(θ2,r2),···,(θi,ri),···,(θh,rh)]和機器分配串 [q11,q12,···,q1h1,···,qnhn]來表示問題的一個解,其中,表示工序總數(shù).

在第一個串中,θi∈{1,2,···,n},1≤ri≤hθi,二元組(θi,ri)對應(yīng)工序oθiri,這樣整個串對應(yīng)一個有序工序表 [oθ1r1,oθ2r2,···,oθiri,···,oθhrh].第二個串中,基因qij∈Sij表示用于加工工序oij的相容機器.上述編碼方法[27,41]能保證除總能耗約束TEC≤QEC之外的其他約束總是成立,但無法保證能耗約束總是成立.對于新加入的約束TEC≤QEC,需要確定閾值QEC并處理不可行解.

2.2 第一階段:ICA

本階段首先將能耗約束從原問題中去掉,而增加第三個目標(biāo)f3=TEC,這樣問題變成具有f1,f2,f3的FJSP,通過問題的轉(zhuǎn)化,將原問題轉(zhuǎn)化為所有約束都可以得到滿足的問題;然后,設(shè)計一種新的ICA對三目標(biāo)FJSP進(jìn)行求解;最后,根據(jù)ICA的結(jié)果確定合適的閾值.由于原問題的不可行解是轉(zhuǎn)化后問題的可行解,這樣擴(kuò)大了ICA的搜索區(qū)域,有助于獲得高質(zhì)量的解.

ICA的主要步驟包括構(gòu)建初始帝國、殖民地同化、殖民地革命、交換和帝國競爭,本文根據(jù)轉(zhuǎn)化后的FJSP的特點,采用一些新策略實現(xiàn)ICA的以上步驟,構(gòu)建新的ICA.

由于只增加一個目標(biāo),只在第一階段優(yōu)化三目標(biāo)FJSP,ICA的非劣排序復(fù)雜性將有所增加,但非劣排序不是每代都做,故問題轉(zhuǎn)化對算法復(fù)雜度的影響不大.

2.2.1 初始帝國構(gòu)建

由于所研究FJSP的多目標(biāo)特性,導(dǎo)致種群中的優(yōu)秀個體經(jīng)常彼此非劣,當(dāng)這些個體被選作殖民國家時,應(yīng)該分配相近數(shù)量的殖民地以同等對待它們.基于該思想,提出了一種初始帝國構(gòu)造新方法.假設(shè)初始帝國總數(shù)為Nim,種群規(guī)模為N,顯然,殖民地總數(shù)Nc=N?Nim,其具體過程如下:

步驟1.對初始種群P中的解按文獻(xiàn)[28]的方法進(jìn)行非劣排序,得到每個解的rank值.

步驟2.確定rank值為1的η個解.

步驟3.如果η

步驟4.對于每個帝國k=1,2,···,Nim,如果k

其中,round(z)為最接近z的整數(shù).

當(dāng)η

2.2.2 同化與革命

同化和革命是ICA的重要步驟,本文提出了革命的實現(xiàn)新途徑.對于調(diào)度問題,同化往往通過利用殖民地和殖民國家之間的交叉[32?37]來實現(xiàn).

本文的同化過程如下:對于帝國內(nèi)的殖民地λ和殖民國家v,隨機產(chǎn)生一個隨機數(shù)s,如果s<ζ,則對兩個解的調(diào)度串應(yīng)用第一種交叉;否則,對兩個解的機器分配串應(yīng)用第二種交叉,產(chǎn)生新解z,并與殖民地λ進(jìn)行比較,若新解支配殖民地λ或者與殖民地λ彼此非劣,則利用新解替代殖民地λ,并更新非劣解集?,其中兩種交叉的詳細(xì)過程見文獻(xiàn)[26?27].

通常,調(diào)度子問題比機器分配子問題更復(fù)雜,求解難度更大,為此,令ζ>0.5以分配更多的計算資源給調(diào)度子問題,通過實驗確定,ζ=0.6.

非劣解集?的更新過程如下:將新解加入到集合?之后,對集合內(nèi)的所有解進(jìn)行Pareto比較,保留非劣解,剔除受支配解.以上更新過程是根據(jù)三個目標(biāo)f1,f2,f3對解進(jìn)行比較,而不是原問題中的f1,f2.

殖民地革命模擬某種非預(yù)期的改變,例如,改變殖民地的語言或宗教,從而改變其特征和地位[29].本文采用新的策略實現(xiàn)殖民地革命,其具體過程描述如下:

對于帝國k

步驟1.令α←1,對于每個τ=1,2,···,Fk,產(chǎn)生隨機數(shù)rand,若rand

步驟2.根據(jù)Pareto支配對帝國內(nèi)的所有殖民地進(jìn)行比較,確定每個殖民地λ的wλ.

步驟3.若α>1,則對于l=1,2,···,α,執(zhí)行如下步驟:

確定具有最小wλ的殖民地λ,令g←1

重復(fù)執(zhí)行如下步驟R次:

若g=1,則對殖民地λ執(zhí)行insert;否則,對殖民地λ執(zhí)行change,產(chǎn)生新解z;

若新解支配殖民地λ或者與殖民地λ彼此非劣,則利用新解替代殖民地λ并更新集合?;否則g←g+1,若g=3則g←1.

其中,R為整數(shù),UR表示革命概率.

關(guān)于革命概率UR,文獻(xiàn)[42?43]分別將其設(shè)置為0.35和0.3.與文獻(xiàn)[42?43]不同,只有部分相對優(yōu)秀的殖民地參與革命過程,基于這一特征,本文選擇一個較小的UR,根據(jù)實驗確定UR為0.1.

3、外文字母的大、小寫和正斜體要分清，希臘文要寫清并注明；符號上下角的高低位置應(yīng)明確區(qū)別，例如；凡國內(nèi)尚未用過的譯名，請在譯名后附原文，外國人名及企業(yè)名稱直接用外文，不要譯成中文。

對于帝國內(nèi)殖民地,如果殖民地λ受同一帝國的其他wλ個殖民地支配,則該殖民地賦給值wλ.只有wλ值最小的部分殖民地參與革命,這是因為利用較優(yōu)秀的殖民地更容易獲得更好的殖民地,甚至產(chǎn)生新的殖民國家.

由于FJSP具有兩個子問題,為此,運用多種鄰域結(jié)構(gòu)insert,swap和change產(chǎn)生新解,其中,insert將隨機選擇的調(diào)度串元素(θi,ri)插入到新位置k 6=i并隨后根據(jù)θi在調(diào)度串中出現(xiàn)的次序為ri重新賦值[26].swap則在互換調(diào)度串的兩個不同元素之后為ri重新賦值.change的實現(xiàn)過程如下:首先構(gòu)建集合Θ={qij||Sij|>1,i=1,2,···,n,j=1,2,···,hi},然后從集合中隨機選擇一些元素,為它們重新賦值,例如,qij被選中,則從Sij中隨機確定一臺機器替代當(dāng)前的qij.

2.2.3 帝國競爭

帝國競爭是ICA的重要步驟.對于本階段考慮的三目標(biāo)FJSP,給出了一種新方式來計算一個解的成本(cost),成本值主要根據(jù)解的rank值和擁擠距離來確定,為此,首先通過非劣排序[28]將種群分解成rankmax個Hl,其中,Hl內(nèi)元素的rank值均為l;然后,對每個集合Hl的非邊界解,按文獻(xiàn)[28]的方法計算擁擠距離,得到這些距離的最大值ψ,邊界解的擁擠距離為ψ+α,其中,α≥1,利用α是為了區(qū)分邊界解與其他解.

帝國競爭的新過程描述如下:如果Nim≥2

步驟1.確定種群P內(nèi)所有解的rank值和擁擠距離.

步驟2.對于集合Hl,l=1,2,···,rankmax,將該集合內(nèi)解的成本定義為,其中,distf表示個體f∈Hl的擁擠距離.

步驟3.按照基本ICA[29]的過程實現(xiàn)帝國競爭的剩余步驟.

計算帝國總成本時的參數(shù)ζ仍取0.1.

2.2.4 ICA描述

ICA的具體過程如下:

步驟1.隨機產(chǎn)生初始種群并確定初始集合?.

步驟2.殖民地同化與革命.

步驟3.殖民地與殖民國家之間的交換.

步驟4.帝國競爭.

步驟5.如果第一階段的終止條件成立,則停止搜索;否則轉(zhuǎn)到步驟2.

其中交換過程如下:對于帝國內(nèi)的每個殖民地,確定殖民地能否支配殖民國家或者與殖民國家彼此非劣,是,則利用殖民地替代當(dāng)前殖民國家,成為帝國新的殖民國家,而原殖民國家則變成殖民地.

第一階段終止條件為目標(biāo)函數(shù)估計次數(shù),由于步驟2每次循環(huán)產(chǎn)生的解個數(shù)不一樣,在步驟2執(zhí)行過程中,要判斷終止條件是否成立,成立則停止搜索.

總之,ICA根據(jù)所研究FJSP具有多目標(biāo)、雙子問題和調(diào)度子問題更復(fù)雜等特點,構(gòu)建初始帝國、讓優(yōu)秀殖民地參加革命、同化過程偏重于調(diào)度子問題的優(yōu)化以及結(jié)合rank值和擁擠距離進(jìn)行帝國競爭,這些策略與問題特點相適應(yīng),有助于提高ICA的求解質(zhì)量.

2.2.5 總能耗閾值

文獻(xiàn)[44]考慮了能耗閾值QEC,但并未討論如何確定閾值大小.本文根據(jù)第一階段ICA的優(yōu)化結(jié)果來確定閾值,這樣可以減少決策者的認(rèn)知和決策負(fù)擔(dān).

關(guān)于每個實例,獲得QEC的具體過程如下:

步驟1.ICA隨機運行20次;

步驟2.計算Qi=max{TEC(z)|z∈?i},;

步驟3.從所有滿足Qi≥的Qi中剔除一些相近的Qi;

步驟4.運行兩階段算法并根據(jù)計算結(jié)果確定哪個Qi≥ˉQ可以作為QEC.

其中,?i表示ICA第i次運行所獲得的非劣解集.

2.3 第二階段:VNS

本階段利用VNS求解具有TEC≤QEC的FJS-P,由于總能耗約束不總是得到滿足,需要處理不可行解,為此,給出一種新原則來比較兩個解x,z:

1)TEC(x)>QEC和TEC(z)≤QEC;

2)x,z都是可行解,且z不受x支配;

3)x,z都是不可行解,且TEC(z)≤TEC(x).

以上三個條件只要有一個滿足,則解x被z替代,其中條件(2)根據(jù)f1,f2對兩個解進(jìn)行Pareto比較.

關(guān)于集合?,第一階段它由通過比較f1,f2,f3而得到的非劣解組成,在從第一階段過渡到第二階段,該集合被直接保留下來,這樣,導(dǎo)致?中存在一些不可行解.

第二階段集合?的更新過程如下:對于解x

1)若TEC(x)>QEC

如果集合?中至少存在一個不可行解y,且滿足TEC(x)

2)若TEC(x)≤QEC

如果集合?所有解都可行,則存在兩種情況.

a)解x與?中的一個成員具有相同的f1,f2,但x的總能耗更小,則利用x替代該成員.

b)情況1的條件不成立,則直接將x添加到集合?中,對所有解根據(jù)f1,f2進(jìn)行Pareto比較,剔除所有受支配解.

如果集合?中存在不可行解,則直接用x替代其中一個不可行解.

VNS的詳細(xì)步驟如下:

步驟1.將集合?中的第一個解當(dāng)作當(dāng)前解,令w←max_it1.

步驟2.令g←1.

步驟3.重復(fù)如下步驟直到g=3或w>max-it隨機產(chǎn)生解z∈Ng(x).

根據(jù)上述原則,如果x能被z所替代,則直接替代,并利用新的x更新集合?且g←1;否則,g←g+1.

如果w能被整數(shù)β整除,則選擇y∈?并替代x.

步驟4.如果w≤max-it,則轉(zhuǎn)到步驟2;否則,停止搜索,剔除?中的非可行解.

其中,max-it1為第一階段的終止條件,max-it為整個兩階段算法的終止條件,N1,N2,N3分別表示鄰域結(jié)構(gòu)swap,insert,change,Ng(x)表示運用Ng所產(chǎn)生的x的鄰域解集.

集合?更新過程中,每次最多只剔除一個非可行解,是為了使?中保留足夠多的解,以便在重新選擇當(dāng)前解時有更多的可能性.

2.4 算法描述:兩階段算法

如上所述,運用兩階段算法可以簡化對能耗約束的處理,擴(kuò)大ICA的搜索區(qū)域,從而提高搜索質(zhì)量.

另外,它還具有如下特點:它不僅能求解所考慮的FJSP,而且能獲得合適的總能耗閾值;它將全局搜索算法和局部搜索算法有機地結(jié)合在一起.

3 計算實驗

為了測試兩階段算法在求解具有總能耗約束的FJSP方面的性能,利用37個實例MK1-15[45]、DP1-18[46]、Ka4×5、Ka10×7、Ka10×10、Ka15×10[2]進(jìn)行計算實驗,這些實驗由Microsoft Visual C++6.0編程實現(xiàn),并運行于4.0GB RAM 1.70GHz CPU PC.

為了用于所研究的FJSP,在37個實例中引入能耗信息:Ek∈[2,4],SEk=1,其交貨期計算公式如下:

其中,δ的值如表1所示.

表1 δ的設(shè)置Table 1 The setting onδ

其中,σxy表示解x與參考解y在歸一化目標(biāo)空間中的距離,

選用NSGA-II[8]和VNS[16]作為對比算法,這兩種算法對FJSP具有較多的應(yīng)用[5,8,16,23],且很容易應(yīng)用于所研究的FJSP的求解.NSGA-II作為求解多目標(biāo)優(yōu)化問題的著名算法,其主要步驟包括非劣排序和擁擠距離的計算等.文獻(xiàn)[8]針對具有隨機故障的FJSP,應(yīng)用NSGA-II求解,為了應(yīng)用于具有總能耗約束的FJSP,對該算法做如下修改:去掉與隨機故障相關(guān)的部分,對可行解采用算法原來的非劣排序和擁擠距離計算,所有不可行解賦予同樣的且大于可行解最大rank值的rank值,擁擠距離設(shè)置為ωmax?TEC(x),其中,ωmax為足夠大的正數(shù).

文獻(xiàn)[16]所設(shè)計的VNS用來解決具有加權(quán)目標(biāo)的FJSP,將第2.3節(jié)中新舊解更替原則和非劣解集更新策略引入后,該VNS可直接求解本文所研究的FJSP,但該VNS與兩階段算法中的VNS的鄰域結(jié)構(gòu)和算法結(jié)構(gòu)不一樣.

兩階段算法的參數(shù)設(shè)置如下:N=80,Nim=6,max_it1=20000,max-it關(guān)于Ka4×5為2.5×104,關(guān)于其他實例為105,β關(guān)于Ka4×5為4000,關(guān)于其他實例為5000,R=8.

NSGA-II的參數(shù)如下:種群規(guī)模為100,交叉概率為0.8,變異概率為0.1,最大代數(shù)為max_it/100.這些參數(shù)值根據(jù)計算實驗而得,是使算法獲得最佳結(jié)果的一組值.

關(guān)于 VNS,nmax=350由文獻(xiàn) [16]給出,max-it與兩階段算法相同.

關(guān)于總能耗閾值QEC,如果閾值過大,大多數(shù)解都滿足總能耗約束,這樣的閾值沒有意義;如果閾值過小,則算法很難得到可行解,導(dǎo)致整個算法的優(yōu)化只是處理能耗約束,目標(biāo)函數(shù)難以得到充分的優(yōu)化,故需要設(shè)置一個合適的閾值.

第2.2節(jié)給出了確定閾值的詳細(xì)過程,以Ka10×7為例,隨機運行ICA20次,得到20個Qi,如表2所示,等于229.7;然后,對于大于的Qi,剔除230.2,232.4,244.4,254.1等相近的值,得到剩余的Qi;最后,運行整個兩階段算法,分別測試剩余的Qi,根據(jù)上述兩種指標(biāo)評價計算結(jié)果,最終確定245.9作為閾值.

表2 閾值的確定Table 2 Decision on threshold

由于閾值是ICA進(jìn)化的結(jié)果,同時又大于ˉQ,故閾值大小合適.表3給出了關(guān)于各個實例的閾值以及三種算法最終所獲得的非劣解所對應(yīng)的實際能耗,其中ATEC和MTEC表示非劣解集中所有非劣解的最小能耗值和平均能耗值.

如表3所示,三種算法關(guān)于所有實例所得到的ATEC和MTEC都小于QEC,而且關(guān)于大多數(shù)實例這兩個指標(biāo)都與QEC接近,這說明第二階段總能耗的下降速度顯著降低了,從而說明第二階段的新舊解更替原則和集合的更新策略是合理的,第二階段主要用于目標(biāo)函數(shù)f1,f2的最小化處理.

表4和5描述了三種算法的計算結(jié)果和計算時間,可以看出,兩階段算法關(guān)于幾乎所有實例所產(chǎn)生的結(jié)果明顯由于另外兩種算法.兩階段算法關(guān)于19個實例提供了參考集的所有元素,而NSGA-II和VNS關(guān)于這19個實例所獲得的解都受兩階段算法的非劣解支配,NSGA-II只是關(guān)于Ka10×7產(chǎn)生了參考集的全部成員,MK06的參考集全部都由VNS提供,另外,NSGA-II和VNS搜索所得的解總是距參考集較遠(yuǎn),總之,兩階段算法利用和另外兩種算法相似的計算時間取得了明顯占優(yōu)的計算結(jié)果.

表3 總能耗閾值和三種算法的ATEC和MTECTable 3 Total energy consumption threshold and ATEC and MTEC of three algorithms

InstanceQEC兩階段算法 NSGA-II VNS ATEC MTEC ATEC MTEC ATEC MTEC MK10 9728 8537.1 8536.2 8991.6 8955.6 9022.7 8972.6 MK1112890 12415 12276 12640 12577 12417 12353 MK1214933 14291 14220 14314 14148 14214 14109 MK1314202 13131 13104 13845 13763 13382 13310 MK1416985 14916 14856 15307 15239 15020 14981 MK1517000 13793 13656 13877 13786 13643 13612 DP1 34534 33829 33745 34117 34026 33902 33758 DP2 40332 38574 38394 38874 38813 38654 38512 DP3 36428 35271 35086 35701 35504 35367 35215 DP4 36880 36171 35656 36077 35742 36225 36089 DP5 40085 38815 38766 39428 39252 38882 38619 DP6 37091 35882 35729 36445 36162 36185 35897 DP7 26373 60667 60542 61033 60989 60707 60673 DP8 52422 49948 49870 50638 50627 50722 50527 DP9 64539 62395 62232 63458 63202 63282 62966 DP10 60350 58580 58133 59242 59145 59277 59070 DP11 57613 55548 55373 56332 56260 56118 55612 DP12 60711 58022 57981 59288 58947 58260 58220 DP13 86142 84382 84335 85046 85027 85200 85062 DP14 83000 80940 80803 82332 82135 81889 81787 DP15 73000 70977 70631 72033 71854 71800 71702 DP16 80468 78790 78584 79976 79878 79417 79266 DP17 86677 84886 84798 85963 85675 85394 85324 DP18 86330 84114 83685 84951 84785 85045 84679

表4 三種算法的計算結(jié)果Table 4 Computational results of three algorithms

Instance DIRρl兩階段算法NSGA-II VNS兩階段算法NSGA-II VNS DP3 1.424 37.62 5.638 0.915 0.000 0.085 DP4 1427 2911 7302 0.750 0.000 0.250 DP5 5.861 50.89 4.452 0.583 0.000 0.417 DP6 0.000 52.16 12.64 1.000 0.00 0.00 DP7 0.000 33.53 19.41 1.000 0.00 0.00 DP8 0.652 42.3 20.47 0.988 0.000 0.012 DP9 0.000 66.43 34.33 1.000 0.00 0.00 DP10 0.543 4836 11.20 0.950 0.000 0.050 DP11 0.000 34.21 14.03 1.000 0.00 0.00 DP12 2.597 67.65 4.814 0.667 0.000 0.333 DP13 0.00 3326 20.31 1.000 0.00 0.00 DP14 0.258 46.08 1264 0.981 0.000 0.019 DP15 0.000 46.20 19.04 1.000 0.00 0.00 DP16 0.000 67.34 44.41 1.000 0.00 0.00 DP17 0.000 34.69 16.09 1.000 0.00 0.00 DP18 0.000 39.64 21.59 1.000 0.00 0.00

表5 三種算法的計算時間Table 5 Comparisons on the computational times of three algorithms

兩階段算法的優(yōu)良性能主要來自于算法的兩階段結(jié)構(gòu)以及全局搜索和局部搜索的良好協(xié)調(diào),而ICA和VNS的一些改進(jìn)策略進(jìn)一步增強了算法性能,因此,兩階段算法是解決具有總能耗約束的FJSP具有較強競爭力的方法.

4 結(jié)論

盡管FJSP已得到較充分的研究,但具有總能耗約束的多目標(biāo)FJSP的研究相對較少,隨著綠色制造和低碳制造的應(yīng)用不斷深入,需要進(jìn)一步研究節(jié)能FJSP.本文提出一種基于ICA和VNS的兩階段算法在總能耗不超過給定的閾值條件下最小化Makespan和總延遲時間.第一階段將原問題轉(zhuǎn)化為包括總能耗的三目標(biāo)FJSP,然后利用新策略構(gòu)建ICA以優(yōu)化轉(zhuǎn)化后的FJSP,并根據(jù)第一階段的結(jié)果確定總能耗閾值;第二階段則運用一種高效的VNS對原問題求解.計算結(jié)果表明,兩階段算法具有較強的搜索性能和優(yōu)勢.

未來我們將繼續(xù)深入研究具有總能耗或峰值能耗約束的調(diào)度問題,并進(jìn)一步研究帝國競爭算法在低碳生產(chǎn)調(diào)度方面的應(yīng)用;另外,分布式調(diào)度也是我們未來研究的主題之一.