混合布谷鳥算法求解綠色流水車間調(diào)度問(wèn)題

鐘祾充 錢 斌 胡 蓉 王 凌

1.昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，昆明，650500 2.清華大學(xué)自動(dòng)化系，北京，100084

0 引言

全球變暖是由溫室氣體的過(guò)度排放引起的，特別是二氧化碳(CO2)的過(guò)度排放。其中，化石燃料的燃燒成為CO2排放的主要原因。合理減排能夠減緩地球變暖。本文研究的問(wèn)題模型包含環(huán)境指標(biāo)，符合當(dāng)前生態(tài)環(huán)境治理的需求。根據(jù)FANG等[1]的調(diào)查，約一半的世界能源消耗來(lái)自工業(yè)部門，制造企業(yè)已經(jīng)成為全球變暖的主要因素之一。一方面，法律法規(guī)對(duì)溫室氣體的排放量控制使得制造企業(yè)不得不限制碳排放；另一方面，高碳排放量帶來(lái)的高稅收也使得制造企業(yè)尋求切實(shí)可行的方法來(lái)減少能源消耗。

在傳統(tǒng)生產(chǎn)調(diào)度問(wèn)題上，主要考慮的優(yōu)化指標(biāo)或目標(biāo)均與時(shí)間、成本和質(zhì)量相關(guān)。當(dāng)制造業(yè)面對(duì)日益增強(qiáng)的環(huán)境和節(jié)能壓力時(shí)，便需要在生產(chǎn)制造過(guò)程中協(xié)同考慮經(jīng)濟(jì)指標(biāo)和綠色指標(biāo)。本文所研究的帶綠色指標(biāo)的多目標(biāo)置換流水線生產(chǎn)調(diào)度問(wèn)題(multi-objective permutation flow shop problem,MOPFSP)具有較強(qiáng)的工業(yè)背景。在計(jì)算復(fù)雜度上，2臺(tái)機(jī)器以上的置換流水車間調(diào)度問(wèn)題(permutation flow shop scheduling problem,PFSP)被證明是NP-hard問(wèn)題[2]，因此，更為復(fù)雜的MOPFSP也屬于NP-hard問(wèn)題。綜上，開(kāi)展帶綠色指標(biāo)的MOPFSP求解具有重要的工程和學(xué)術(shù)意義。

在過(guò)去幾十年里，流水線車間調(diào)度問(wèn)題已被廣泛研究，然而，近十年來(lái)才有一些文獻(xiàn)同時(shí)考慮經(jīng)濟(jì)和環(huán)境指標(biāo)。LUO等[3]針對(duì)帶電力消耗的多目標(biāo)混合流水車間調(diào)度問(wèn)題，設(shè)計(jì)了蟻群優(yōu)化算法進(jìn)行求解。DING等[4]針對(duì)帶碳排放總量的多目標(biāo)流水車間調(diào)度問(wèn)題進(jìn)行研究，并提出了一種改進(jìn)的迭代貪心算法求解該問(wèn)題。LIU等[5]設(shè)計(jì)了一種自適應(yīng)多目標(biāo)遺傳算法，可有效求解一類帶碳排放和總加權(quán)延遲兩個(gè)優(yōu)化指標(biāo)的流水線車間調(diào)度問(wèn)題。DING等[6]提出了基于非支配解結(jié)構(gòu)特性的迭代貪心算法，用于求解帶碳排放總量的雙目標(biāo)流水車間調(diào)度問(wèn)題。TANG等[7]提出了改進(jìn)的粒子群優(yōu)化算法，可求解基于能源消耗和最長(zhǎng)完工時(shí)間兩個(gè)目標(biāo)的柔性流水車間調(diào)度問(wèn)題。LU等[8]針對(duì)帶能源消耗的多目標(biāo)流水車間調(diào)度問(wèn)題，提出了一種基于機(jī)器設(shè)置時(shí)間和工件運(yùn)輸時(shí)間的混合多目標(biāo)回溯搜索算法進(jìn)行求解。綜上所述，帶綠色指標(biāo)的多目標(biāo)流水車間調(diào)度問(wèn)題的研究仍較為有限，迫切需要加強(qiáng)對(duì)求解該類重要問(wèn)題的有效方法的研究。

布谷鳥搜索 (cuckoo search,CS)算法是YANG和DEB于2009年提出的一種元啟發(fā)式算法，該算法根據(jù)布谷鳥產(chǎn)卵時(shí)的飛行機(jī)制進(jìn)行搜索，能夠快速有效地求解連續(xù)優(yōu)化問(wèn)題。近年來(lái)，CS算法也被擴(kuò)展用于求解帶經(jīng)濟(jì)指標(biāo)的單目標(biāo)生產(chǎn)調(diào)度問(wèn)題。LI等[9]利用NEH啟發(fā)式規(guī)則產(chǎn)生部分初始種群，并設(shè)計(jì)了一種帶局部搜索的混合CS算法對(duì)單目標(biāo)PFSP問(wèn)題進(jìn)行求解。MAEICHELVAM等[10]在CS算法的初始階段采用NEH規(guī)則初始化部分種群，進(jìn)而將其用于求解單目標(biāo)多階段混合流水線車間調(diào)度問(wèn)題。ALAA等[11]對(duì)CS算法中的萊維飛行公式進(jìn)行改進(jìn)，同時(shí)加強(qiáng)了對(duì)種群最優(yōu)個(gè)體鄰域的搜索，并將所提算法用于求解單目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題。WANG等[12]采用NEH規(guī)則產(chǎn)生部分初始種群，繼而提出了一種帶局部搜索的混合布谷鳥算法，用于求解單目標(biāo)流水線車間調(diào)度問(wèn)題。由上述文獻(xiàn)可知，尚無(wú)利用CS算法求解帶綠色指標(biāo)的MOPFSP的相關(guān)研究。此外，上述文獻(xiàn)均將步長(zhǎng)控制因子設(shè)定為某個(gè)常數(shù)，并未對(duì)其進(jìn)行動(dòng)態(tài)調(diào)整。實(shí)際上，隨著算法迭代次數(shù)的增加，若步長(zhǎng)控制因子設(shè)置過(guò)大，布谷鳥算法的搜索易偏離優(yōu)質(zhì)解區(qū)域，從而導(dǎo)致性能變差；若步長(zhǎng)控制因子設(shè)置過(guò)小，該算法在前期就容易陷入局部最優(yōu)而早熟。因此，針對(duì)綠色流水車間調(diào)度問(wèn)題，設(shè)計(jì)可動(dòng)態(tài)調(diào)整步長(zhǎng)控制因子的布谷鳥算法進(jìn)行有效求解，具有重要意義。

本文提出了一種混合布谷鳥(HCS)算法用于求解優(yōu)化目標(biāo)為最長(zhǎng)完工時(shí)間和總碳排放量的MOPFSP。在HCS算法中，不僅提出了一種步長(zhǎng)控制因子的自適應(yīng)調(diào)整策略，使布谷鳥算法具有較快的收斂速度和較好的全局搜索性能；同時(shí)還設(shè)計(jì)了一種多鄰域局部搜索機(jī)制，可對(duì)HCS算法全局搜索得到的優(yōu)質(zhì)解區(qū)域進(jìn)行細(xì)致搜索，進(jìn)而使算法在全局和局部搜索之間到達(dá)較好平衡。最后，通過(guò)仿真實(shí)驗(yàn)和算法對(duì)比來(lái)驗(yàn)證HCS算法的有效性。

1 低碳MOPFSP描述

設(shè)有n個(gè)工件需要在m臺(tái)機(jī)器上加工，每個(gè)機(jī)器有s種不同的加工速度，其中工件集合為J={1,2,…,n}，機(jī)器集合為M={1,2,…,m}，速度集合為S={v1,v2,…,vs}。Pi,k表示工件i在機(jī)器k上的標(biāo)準(zhǔn)加工時(shí)間；Vi,k表示工件i在機(jī)器k上的加工速度；Pi,k/Vi,k表示工件i在機(jī)器k上以速度Vi,k加工時(shí)的真實(shí)加工時(shí)間；Qk,v表示機(jī)器k以速度v工作時(shí)的單位能耗；Qk表示機(jī)器k待機(jī)狀態(tài)時(shí)的單位能耗；當(dāng)t時(shí)刻機(jī)器k以速度v工作時(shí)xkv(t)=1，其他時(shí)刻xkv(t)=0；t時(shí)刻機(jī)器k呈現(xiàn)待機(jī)狀態(tài)yk(t)=1，其他時(shí)刻yk(t)=0；π=(j1,j2,…,jn)為所有工件的某種排序；Π是不同排序π的集合；C(ji,k)i=(1,2,…,n)為工件ji在機(jī)器k上的完成時(shí)間。

PFSP的2個(gè)加工規(guī)則：①當(dāng)工件i∈J在機(jī)器(k-1)∈M上加工完成之后，工件j∈J才能在機(jī)器k∈M上加工。②每臺(tái)機(jī)器每次只能加工一個(gè)工件，不能同時(shí)加工多個(gè)工件。

假設(shè)工件j1至jn依次在機(jī)器1至機(jī)器m上順序加工，最長(zhǎng)完工時(shí)間make-span的數(shù)學(xué)模型如下：

C(j1,1)=Pj1,1/Vj1,1

(1)

C(ji,1)=C(ji-1,1)+Pji,1/Vj1,1

(2)

C(j1,k)=C(j1,k-1)+Pj1,k/Vj1,k

(3)

(4)

Cmax=C(jn,m)

(5)

其中，k=2,3,…,m，i=2,3,…,n；式(5)為最長(zhǎng)完工時(shí)間。

假設(shè)ε是每單位能耗的CO2排放量，CO2排放總量計(jì)算公式為

(6)

其中，CT表示能源總消耗；CCO2表示CO2排放總量，以下簡(jiǎn)稱碳排放總量(total carbon emissions,TCE)。

為了計(jì)算碳排放總量，需要構(gòu)建機(jī)器的速率矩陣An×m，其中Ai,k∈{1,2,…,s}。假設(shè)s=3，Ai,k∈{1,2,3}，n=3，m=2，則矩陣A3×2的其中一種情況表示如下：

(7)

如，A31表示第3個(gè)工件在第1臺(tái)機(jī)器上的加工速度為3。

對(duì)于低碳多目標(biāo)PFSP，不可能同時(shí)求得最長(zhǎng)完工時(shí)間(make-span)和TCE的全局最優(yōu)解，但是可以求得這樣一組解：任何一個(gè)目標(biāo)的繼續(xù)優(yōu)化都必須犧牲其他目標(biāo)函數(shù)值的有效解[13-14]。這類有效解組成的集合稱之為非劣解，即Pareto解集。

2 多目標(biāo)問(wèn)題相關(guān)概念

本文中MOPFSP可以表示為

minF(π)=[f1(π),f2(π)],π∈ψ

(8)

f1=Cmax

(9)

f2=CCO2

(10)

式中，ψ為可行域。

(1)支配。對(duì)于目標(biāo)向量F(π1)=(f1(π1),f2(π1))和F(π2)=(f1(π2),f2(π2)),當(dāng)且僅當(dāng)(?i∈{1,2}:fi(π1)≤fi(π2))∩(?i∈{1,2}:fi(π1)

(2)Pareto優(yōu)解。對(duì)于π∈ψ，當(dāng)且僅當(dāng)不存在π′∈ψ使F(π′)F(π)時(shí)，稱π為Pareto優(yōu)解。

(3)Pareto解集合。對(duì)于Pareto解集合P:

P={π∈ψ|π′∈ψ:F(π′)F(π)}

(4)Pareto前沿。

對(duì)于Pareto前沿PF，有

PF={F(π)=(f1(π),f2(π))|π∈P}

3 混合布谷鳥算法

3.1 標(biāo)準(zhǔn)布谷鳥算法

YANG等[15]根據(jù)布谷鳥尋窩產(chǎn)蛋的行為和萊維飛行(Lévy flight)特征，提出了標(biāo)準(zhǔn)的多目標(biāo)布谷鳥算法。布谷鳥算法中個(gè)體更新方式有兩種，第一種是使用萊維飛行公式：

xi,t+1=xi,t+α⊕Lévy(λ)

(11)

其中，xi,t+1、xi,t分別表示第i個(gè)個(gè)體在第k代和第k+1代時(shí)的位置向量；⊕表示點(diǎn)乘；α為控制步長(zhǎng)的步長(zhǎng)因子，大多數(shù)情況下，α=O(1)；Lévy(λ)為萊維飛行搜索路徑。

從式(11)可以看出，該分布使布谷鳥的連續(xù)位置形成了一種帶重尾的概率分布，能擴(kuò)大搜索范圍，增加種群多樣性，且容易跳出局部最優(yōu)。

第二種更新方式是根據(jù)一個(gè)固定的發(fā)現(xiàn)概率Pa與一個(gè)隨機(jī)數(shù)β之間的關(guān)系確定是否產(chǎn)生新個(gè)體，更新公式如下：

xi,t+1=xi,t+γH(Pa-β)⊕[xo,t-xk,t]

(12)

其中，γ和β二者均服從均勻分布，γ、β∈U[0,1]；xi,t、xo,t、xk,t分別為第t代中3個(gè)不同的隨機(jī)個(gè)體；H為赫威賽德函數(shù)，其計(jì)算公式為

(13)

3.2 混合布谷鳥算法(HCS)

3.2.1自適應(yīng)步長(zhǎng)因子

CS算法雖然在諸多領(lǐng)域得到應(yīng)用研究，但其本身存在固有不足：萊維飛行是一種馬爾科夫鏈，只與當(dāng)前情況有關(guān)，隨機(jī)性較大，所以標(biāo)準(zhǔn)CS算法缺乏有效機(jī)制來(lái)加強(qiáng)搜索深度，算法收斂精度不高。CS算法在式(11)中定義了步長(zhǎng)控制因子，該因子在標(biāo)準(zhǔn)算法中一般設(shè)定為固定的常數(shù)(譬如常取值為0.01)。若步長(zhǎng)控制因子取值過(guò)大，易導(dǎo)致算法后期的搜索偏離優(yōu)質(zhì)解，使其收斂速度變慢；反之，若步長(zhǎng)控制因子取值過(guò)小，則算法可能過(guò)早地陷入局部最優(yōu)解，從而導(dǎo)致算法性能較弱。因此，對(duì)步長(zhǎng)控制因子的改進(jìn)有利于算法性能的提升。如果在算法搜索前期使用一個(gè)較大的步長(zhǎng)控制因子，有利于在全局范圍內(nèi)迅速發(fā)現(xiàn)優(yōu)質(zhì)解所在區(qū)域；同時(shí)，隨著算法搜索的推進(jìn)，應(yīng)逐漸減小步長(zhǎng)控制因子，加強(qiáng)對(duì)局部?jī)?yōu)質(zhì)解區(qū)域的細(xì)致搜索，這有利于提高算法的收斂速度和性能。

本文從步長(zhǎng)控制因子方面對(duì)標(biāo)準(zhǔn)CS算法進(jìn)行改進(jìn)：用動(dòng)態(tài)步長(zhǎng)控制因子替換原有固定的步長(zhǎng)控制因子。尋優(yōu)過(guò)程中，隨著個(gè)體質(zhì)量逐步提高，適當(dāng)縮小搜索范圍，以加強(qiáng)搜索深度，有利于搜尋到更優(yōu)的解。合理的步長(zhǎng)控制因子應(yīng)該是隨著進(jìn)化代數(shù)的增加而逐漸減小，使得算法在進(jìn)化后期容易發(fā)現(xiàn)優(yōu)質(zhì)個(gè)體。

本文根據(jù)以下方面自適應(yīng)調(diào)整步長(zhǎng)控制因子α：將α取值范圍設(shè)置為[0.01,0.2]；另外，引入余弦函數(shù)使α隨著進(jìn)化代數(shù)的增加而減小。綜上所述，提出α的改進(jìn)公式：

(14)

其中，R表示當(dāng)前進(jìn)化代數(shù)與總進(jìn)化代數(shù)之比；αmin為步長(zhǎng)控制因子的下限；αmax為步長(zhǎng)控制因子的上限；Tmax為最大迭代次數(shù)；k為當(dāng)前進(jìn)化代數(shù)。算法初始階段R≤0.2，此時(shí)應(yīng)有大步長(zhǎng)去發(fā)現(xiàn)優(yōu)質(zhì)解所在區(qū)域，因此步長(zhǎng)控制因子α隨進(jìn)化代數(shù)增加而逐漸減??；算法中期可能達(dá)到最佳更新?tīng)顟B(tài)，即0.5>R>0.2，此時(shí)應(yīng)在優(yōu)質(zhì)解所在區(qū)域進(jìn)一步搜索，加強(qiáng)局部精細(xì)搜索，α保持不變；算法后期R≥0.5，此時(shí)個(gè)體逐漸接近Pareto前沿，無(wú)需大步長(zhǎng)跳躍，因此保留α下界即可。

3.2.2多鄰域局部搜索

為進(jìn)一步提高布谷鳥算法的局部搜索能力，本文引入多鄰域局部搜索策略，對(duì)種群中的優(yōu)質(zhì)個(gè)體執(zhí)行基于不同鄰域的細(xì)致搜索。具體來(lái)說(shuō)，就是對(duì)算法當(dāng)前的非劣解集中的個(gè)體執(zhí)行基于三種鄰域的局部搜索。這三種鄰域搜索分別為：Interchange local search、Insert local search[16]、2-opt local search，具體定義如下。

Interchange local search：對(duì)每個(gè)個(gè)體的工件排序，隨機(jī)選擇其中兩個(gè)不同的位置，交換位置上的工件。例如10工件排序?yàn)閇4,2,7,1,3,5,9,8,10,6]，隨機(jī)產(chǎn)生了兩個(gè)位置p1=3，p2=9，則將位置3的工件7和位置9的工件10交換位置，得到一個(gè)新排序[4,2,10,1,3,5,9,8,7,6]。

Insert local search：該步驟可分為前插入和后插入。對(duì)每個(gè)個(gè)體的工件排序進(jìn)行操作，隨機(jī)選擇其中2個(gè)不同的位置p1和p2，假設(shè)p1>p2。后插入是指將位置p1的工件插入位置p2，位置p1+1～p2的工件均往前挪一個(gè)位置；前插入是指將p2的工件插入位置p1，位置p1～p2-1的工件均往后挪一個(gè)位置。例如10工件排序?yàn)閇4,2,7,1,3,5,9,8,10,6]，隨機(jī)產(chǎn)生了兩個(gè)位置p1=3，p2=9，按照上文，后插入得到的新排序?yàn)閇4,2,1,3,5,9,8,10,7,6]，前插入得到的新排序?yàn)閇4,2,10,7,1,3,5,9,8,6]。

2-opt local search：對(duì)每個(gè)個(gè)體的工件排序，隨機(jī)選擇其中兩個(gè)不同的位置p1和p2，將p1～p2的工件排序逆序排列，其他位置工件排序不變。例如10工件排序?yàn)閇4,2,7,1,3,5,9,8,10,6]，隨機(jī)產(chǎn)生了兩個(gè)位置p1=3，p2=9，按照上文，得到的新排序?yàn)閇4,2,10,8,9,5,3,1,7,6]。

令π(X)為個(gè)體X基于LOV規(guī)則的工件排序，π(X′)為個(gè)體X′基于LOV規(guī)則的工件排序，k為擾動(dòng)或探索次數(shù)。對(duì)個(gè)體X執(zhí)行多鄰域局部搜索的具體步驟如下：

(1)擾動(dòng)階段。①設(shè)k=0；②隨機(jī)選擇2個(gè)不同位置p1和p2，π(X)=Insert(π(X),p1,p2)，k=k+1；③如果k<2，則返回步驟②。

(2)探索階段。①設(shè)k=0，t=0；②隨機(jī)選擇兩個(gè)不同位置p1和p2；如果t=0，π(X′)=Insert(π(X),p1,p2)；如果t=1，π(X′)=Interchange(π(X),p1,p2)；如果t=2，π(X′)=2-opt(X,p1,p2)；③如果π(X′)π(X)，則π(X)=π(X′)，k=k+1，否則t=t+1；④如果k<30，則跳到步驟⑤，否則停止探索并輸出π(X)和X；⑤如果t<3，返回步驟②，否則t=0，返回步驟②。

3.3 HCS算法求解MOPFSP的步驟

基于改進(jìn)的HCS算法求解MOPFSP的主要步驟如下：

(1)參數(shù)初始化。設(shè)置種群規(guī)模N；個(gè)體上下界，并在界內(nèi)初始化種群W；設(shè)置最大迭代次數(shù)gene或算法運(yùn)行時(shí)間T。

(2)個(gè)體離散化。采用LOV規(guī)則將連續(xù)的個(gè)體轉(zhuǎn)化為離散排序；計(jì)算每個(gè)個(gè)體的兩個(gè)目標(biāo)函數(shù)值。

(3)個(gè)體更新。隨機(jī)挑選一個(gè)個(gè)體xi，根據(jù)式(11)采用萊維飛行對(duì)個(gè)體進(jìn)行更新，產(chǎn)生一個(gè)新個(gè)體xi1；新老個(gè)體采用非支配原則保優(yōu)，若互不支配，則隨機(jī)保留一個(gè)，保留的個(gè)體存入xi1。

(4)拋棄概率的應(yīng)用。根據(jù)拋棄概率判斷是否對(duì)步驟(3)中保留的個(gè)體xi1進(jìn)行操作，若要對(duì)其進(jìn)行操作，則利用式(12)更新并得到一個(gè)新個(gè)體xi2，最后對(duì)新舊個(gè)體采用非支配原則保優(yōu)；若互不支配，則隨機(jī)保留一個(gè)，保留的個(gè)體存入xi1。

(5)保留Pareto前沿。利用非支配原則將本代的Pareto前沿找出，并將本代Pareto前沿的個(gè)體存入Pareto解集P(t)。

(6)多鄰域搜索。將本代P(t)集合里的每個(gè)個(gè)體XP(t)對(duì)應(yīng)的排序依次進(jìn)行多鄰域搜索，得到本代更新后的Pareto解集P(t)′。

(7)記錄當(dāng)前Pareto解集。將更新后的Pareto解集P(t)′與第t-1代保留下來(lái)的Pareto解集P融合，利用非支配原則求出當(dāng)前第t代Pareto解集P，并用此集合P代替本代非劣解集P(t)′，便于在下一代中使用。

(8)根據(jù)式(14)更新步長(zhǎng)控制因子α，每一代都要對(duì)步長(zhǎng)控制因子做出判斷，并更新。

(9)終止條件若當(dāng)前迭代次數(shù)小于最大迭代次數(shù)gene或進(jìn)化時(shí)間小于算法運(yùn)行時(shí)間T，重復(fù)執(zhí)行步驟(2)～步驟(8)；否則輸出當(dāng)前Pareto解集P，結(jié)束算法。

基于以上步驟，利用HCS算法求解MOPFSP的算法流程圖見(jiàn)圖1。

圖1 HCS算法流程圖Fig.1 Flow chart of HCS

4 算法測(cè)試結(jié)果及分析

為驗(yàn)證HCS算法求解MOPFSP的有效性，本文選取了10種規(guī)模大小不同的算例，采用標(biāo)準(zhǔn)CS和INSGA-Ⅱ算法[17]進(jìn)行對(duì)比實(shí)驗(yàn)。INSGA-Ⅱ算法是基于經(jīng)典多目標(biāo)算法NSGA-Ⅱ的改進(jìn)算法，文獻(xiàn)[17]利用仿真實(shí)驗(yàn)驗(yàn)證了INSGA-Ⅱ算法優(yōu)于NSGA-Ⅱ算法，所以將HCS算法與INSGA-Ⅱ算法比較是有意義的。

在測(cè)試算例中，工件在每臺(tái)機(jī)器上的加工時(shí)間采用100以內(nèi)的隨機(jī)正整數(shù)按照問(wèn)題規(guī)模生成；機(jī)器速度擋位設(shè)定為Ai,k∈{1,2,3}；所有算法的種群大小均為30；HCS算法與CS算法的拋棄概率均為0.25；CS算法步長(zhǎng)控制因子為0.01；HCS算法初始步長(zhǎng)控制因子為0.2；INSGA-Ⅱ算法中變異概率為0.3，交叉概率為0.9。本文以 50n(單位ms)作為各算法運(yùn)行的終止條件，其中，n為每種問(wèn)題規(guī)模的工件數(shù)。這使得測(cè)試同一個(gè)問(wèn)題規(guī)模時(shí)，所有算法的運(yùn)行時(shí)間一致，可確保比較的公平性。各算法對(duì)每一測(cè)試問(wèn)題均獨(dú)立運(yùn)行20次。

所有算法和測(cè)試程序均用Delphi 10.2編程實(shí)現(xiàn)，操作系統(tǒng)為Win 10，處理器為Intel(R) Core(TM) i5-4210U 1.70 GHz，內(nèi)存為4 GB。

本文采用的分析指標(biāo)是文獻(xiàn)[18]中提出的多目標(biāo)分析指標(biāo)，分別為R_NDS(Sr)和NDS_NUM(Sr)，計(jì)算公式如下：

R_NDS(Sr)=|Sr-{x∈Sr|?y∈S:yx}|/|Sr|

(15)

NDS_NUM(Sr)=|Sr-{x∈Sr|?y∈S:yx}|

(16)

其中，Sr是指算法r的Pareto解集；S是指K種算法的Pareto解集的并集，可以表示為S=S1∪…∪Sr∪…SK；yx是指?jìng)€(gè)體y完全支配個(gè)體x；|Sr|是指Sr集合中個(gè)體的數(shù)量；NDS_NUM(Sr)是指算法r中未被支配的個(gè)體數(shù)量；R_NDS(Sr)是指算法r中未被支配的個(gè)體數(shù)占算法r中總的Pareto解集個(gè)體數(shù)的比率。R_NDS(Sr)=1意味著Sr中所有的Pareto個(gè)體都不被支配；R_NDS(Sr)=0.9意味著Sr中90%的Pareto個(gè)體都不被支配。

本文中每個(gè)問(wèn)題規(guī)模的數(shù)據(jù)結(jié)果可以在表1和表2中找到：HCS算法和CS算法的對(duì)比數(shù)據(jù)見(jiàn)表1， HCS算法和INSGA-Ⅱ算法的對(duì)比數(shù)據(jù)見(jiàn)表2。根據(jù)上文中S的定義，表1中的S可以表示為S=SHCS∪SCS，表2中的S可以表示為S=SHCS∪SINSGA-Ⅱ。R_NDS_HCS表示20個(gè)R_NDS(SHCS)數(shù)據(jù)的平均比率，R_NDS_CS表示20個(gè)R_NDS(SCS)數(shù)據(jù)的平均比率，R_NDS_INSGA-Ⅱ表示20個(gè)R_NDS(SINSGA-Ⅱ)數(shù)據(jù)的平均比率，NDS_NUM_HCS表示20個(gè)NDS_NUM(SHCS)數(shù)據(jù)的平均數(shù)，NDS_NUM_CS表示20個(gè)NDS_NUM(SCS)數(shù)據(jù)的平均數(shù)，NDS_NUM_INSGA-Ⅱ表示20個(gè)NDS_NUM(SINSGA-Ⅱ)數(shù)據(jù)的平均數(shù)。

表1 HCS算法和CS算法對(duì)比數(shù)據(jù)

表2 HCS算法和INSGA-Ⅱ算法對(duì)比數(shù)據(jù)

由表1可看出，R_NDS_HCS全部為1，而R_NDS_CS幾乎為零，說(shuō)明在求解以上所有問(wèn)題規(guī)模的MOPFSP時(shí)，HCS算法完全支配標(biāo)準(zhǔn)CS算法，且NDS_NUM_HCS的個(gè)數(shù)在3～6之間，符合種群規(guī)模為30的情況；由表2可看出，R_NDS_HCS均大于R_NDS_INSGA-Ⅱ，且有8個(gè)問(wèn)題規(guī)模的R_NDS_HCS大于0.8，說(shuō)明HCS算法有80%以上的Pareto個(gè)體支配INSGA-Ⅱ算法的Pareto個(gè)體，而在其他2個(gè)問(wèn)題規(guī)模中，比率為65%以上?？傮w而言，HCS算法得到的解集更優(yōu)，證明了HCS算法的有效性。

10_5規(guī)模和100_30規(guī)模某次運(yùn)行情況見(jiàn)圖2、圖3。從圖2中可看出，雖然HCS算法與INSGA-Ⅱ算法尋得的Pareto解集重合，但都完全支配標(biāo)準(zhǔn)CS算法。從圖3中可看出，HCS算法的Pareto前沿在其他2個(gè)算法的左下方，說(shuō)明HCS算法的Pareto解集把其他2個(gè)算法的Pareto解集完全支配。隨著問(wèn)題規(guī)模的增大，較標(biāo)準(zhǔn)CS算法和INSGA-Ⅱ算法，HCS算法的Pareto前沿與其他2個(gè)算法的Pareto前沿距離越拉越大，尋優(yōu)的優(yōu)越性越來(lái)越明顯。

圖2 問(wèn)題規(guī)模為10_5時(shí)3種算法的某次Pareto解點(diǎn)圖Fig. 2 Non-dominated solutions of HCS (3points)、CS (2points) and INSGA-Ⅱ (3points) when the instance is 10_5

圖3 問(wèn)題規(guī)模為100_30時(shí)3種算法的某次Pareto解點(diǎn)圖Fig. 3 Non-dominated solutions of HCS (4points)、CS (4points) and INSGA-Ⅱ (4points) when the instance is 100_30

綜上所述，在以上所有問(wèn)題規(guī)模中，HCS算法在求解MOPFSP時(shí)比INSGA-Ⅱ算法和CS算法有效。

5 實(shí)例分析

為進(jìn)一步驗(yàn)證所提算法的有效性，將HCS算法用于求解江西瑞金某電線電纜廠的電線電纜生產(chǎn)調(diào)度問(wèn)題。該工廠初成型電纜生產(chǎn)過(guò)程依次為單絲拉制、單絲退火、導(dǎo)體絞制、絕緣擠出、成纜共5個(gè)環(huán)節(jié)。5個(gè)環(huán)節(jié)分別在5臺(tái)特定的機(jī)器上加工，各環(huán)節(jié)的加工機(jī)器可通過(guò)調(diào)整擋位來(lái)設(shè)定加工速度。近年來(lái)，該公司積極響應(yīng)綠色生產(chǎn)節(jié)能減排，在其生產(chǎn)過(guò)程中同時(shí)考慮經(jīng)濟(jì)指標(biāo)(make-span)和環(huán)境指標(biāo)(TCE)。顯然，此初成型電纜的生產(chǎn)調(diào)度問(wèn)題是典型的MOPFSP。目前，該電纜廠生產(chǎn)調(diào)度是由調(diào)度員基于經(jīng)驗(yàn)對(duì)工件編號(hào)后進(jìn)行人工排序調(diào)度。

本文采用該工廠生產(chǎn)30類電纜的實(shí)際生產(chǎn)數(shù)據(jù)作為測(cè)試實(shí)例，用HCS算法運(yùn)行1.5 s求解，同時(shí)請(qǐng)調(diào)度員在5 min內(nèi)給出人工調(diào)度方案。HCS算法獲得了調(diào)度方案S1～S4，見(jiàn)表3和圖4。調(diào)度員通過(guò)經(jīng)驗(yàn)得到的調(diào)度方案T1，見(jiàn)表3。由表3可知，S1～S4均明顯優(yōu)于T1。這一結(jié)果表明HCS算法可快速有效地求解實(shí)際問(wèn)題。

表3 調(diào)度方案

圖4 HCS目標(biāo)值對(duì)比Fig.4 HCS target value comparison

6 結(jié)論

本文提出了一種混合布谷鳥算法，用于求解綠色多目標(biāo)流水車間調(diào)度問(wèn)題(MOPFSP)。HCS算法通過(guò)采用所提的自適應(yīng)步長(zhǎng)控制因子和多鄰域局部搜索，較好地平衡了算法的全局和局部搜索，提高了算法的性能和收斂速度。仿真實(shí)驗(yàn)和算法比較結(jié)果表明，HCS算法能夠較快求解MOPFSP，且其性能優(yōu)于CS算法和INSGA-Ⅱ算法。驗(yàn)證了HCS算法在求解MOPFSP上的有效性。

關(guān)于布谷鳥算法在復(fù)雜生產(chǎn)調(diào)度上的未來(lái)研究，可以考慮將其拓展應(yīng)用于比MOPFSP更加復(fù)雜的調(diào)度問(wèn)題上，特別是不確定綠色調(diào)度問(wèn)題。