基于灰狼優(yōu)化算法的低碳車間調(diào)度問題

姜天華

(魯東大學(xué) 交通學(xué)院，山東 煙臺 264025)

0 引言

當(dāng)今世界能源與環(huán)境危機(jī)已經(jīng)引起絕大多數(shù)國家的關(guān)注，加快推進(jìn)低碳制造成為全球制造業(yè)發(fā)展面臨的關(guān)鍵問題。車間調(diào)度是實(shí)現(xiàn)制造系統(tǒng)管理、運(yùn)籌與優(yōu)化等技術(shù)提升的核心，因此采用先進(jìn)調(diào)度方法將成為企業(yè)實(shí)現(xiàn)低碳制造的有效途徑之一。

近些年低碳車間調(diào)度雖已引起學(xué)者們的興趣和關(guān)注，但現(xiàn)有相關(guān)文獻(xiàn)還相對較少，且研究對象較為簡單。文獻(xiàn)[1]構(gòu)建了碳排放約束下工件等待時間受限的廢鋼鐵再制造生產(chǎn)調(diào)度模型，并設(shè)計(jì)了遺傳算法進(jìn)行求解;文獻(xiàn)[2]采用差分遺傳算法求解以高效低碳為目標(biāo)的置換流水車間調(diào)度問題;文獻(xiàn)[3]針對廢鋼鐵再熔煉生產(chǎn)調(diào)度問題，采用遺傳算法優(yōu)化車間二氧化碳排放量;文獻(xiàn)[4]針對兩機(jī)流水車間，以峰值功率負(fù)載、能耗總量、二氧化碳排放量和最大完工時間為優(yōu)化目標(biāo)，對車間調(diào)度問題進(jìn)行研究;文獻(xiàn)[5]以系統(tǒng)能耗量最小為目標(biāo)，采用遺傳算法研究了電價可變情況下的單機(jī)調(diào)度問題;文獻(xiàn)[6]以最大完工時間和車間能耗量為優(yōu)化指標(biāo)，采用遺傳算法求解作業(yè)車間內(nèi)多目標(biāo)能效優(yōu)化問題;文獻(xiàn)[7]以最小化碳排放量和最大完工時間為目標(biāo)，對置換流水車間調(diào)度問題進(jìn)行了研究;文獻(xiàn)[8]考慮能耗總量和最大完工時間兩種性能指標(biāo)，提出多目標(biāo)遺傳算法求解兩機(jī)流水車間調(diào)度問題。上述文獻(xiàn)中的低碳調(diào)度問題大多以簡單系統(tǒng)作為研究對象，而目前有關(guān)柔性作業(yè)車間低碳調(diào)度問題的研究還相對較少。文獻(xiàn)[9]基于設(shè)備狀態(tài)—能耗曲線建立了多目標(biāo)柔性作業(yè)低碳調(diào)度模型，并提出一種改進(jìn)非支配排序遺傳算法;文獻(xiàn)[10]以能源消耗、最大完工時間和生產(chǎn)成本為調(diào)度目標(biāo)，建立了多目標(biāo)柔性作業(yè)車間低碳調(diào)度模型，提出一種改進(jìn)離散蝙蝠算法對其求解。文獻(xiàn)[11]以車間能耗成本和工件提前/拖期成本為優(yōu)化指標(biāo)，建立了柔性作業(yè)車間低碳調(diào)度模型，并提出了一種雙種群離散貓群優(yōu)化算法進(jìn)行求解。

柔性作業(yè)車間是經(jīng)典作業(yè)車間調(diào)度問題的擴(kuò)展形式，該問題不但要解決每臺機(jī)器上工序的排序問題，而且排序前還需為每道工序分配合適的機(jī)器，大大增加了求解的復(fù)雜程度[12]，因此本文將低碳調(diào)度問題擴(kuò)展到柔性作業(yè)車間中進(jìn)行研究。此外，從求解方法來看，上述文獻(xiàn)大多采用遺傳算法對問題進(jìn)行求解，求解方法稍顯單一，只有文獻(xiàn)[10]和文獻(xiàn)[11]對新型智能算法在低碳調(diào)度中的應(yīng)用進(jìn)行了研究。然而，隨著各學(xué)科的發(fā)展和滲透，新型智能優(yōu)化算法層出不窮，有必要探尋更多新型有效的算法，以豐富該類問題的求解途徑。灰狼優(yōu)化算法是根據(jù)狼群捕食行為而提出的一種新型群智能優(yōu)化算法[13]，該算法由于出現(xiàn)的時間較晚，目前在車間調(diào)度方面的應(yīng)用還較少，且大多集中于流水車間調(diào)度[14-17]，很少用于求解柔性作業(yè)車間調(diào)度問題[18]。因此，本文將灰狼優(yōu)化算法應(yīng)用于柔性作業(yè)車間低碳調(diào)度問題，主要完成的工作為：采用兩段式的個體位置編碼/解碼機(jī)制和基于啟發(fā)式算法的種群初始化方法；設(shè)計(jì)了收斂因子非線性調(diào)整策略和帶權(quán)重系數(shù)的個體位置更新方法；嵌入了局部搜索算法，加強(qiáng)了算法局部搜索能力。最后，通過大量仿真數(shù)據(jù)驗(yàn)證了本文算法在求解柔性作業(yè)車間低碳調(diào)度問題方面的有效性。

1 柔性作業(yè)車間低碳調(diào)度問題

1.1 問題描述

某車間配備m臺機(jī)器完成n個工件的待加工任務(wù)。對于任一工件i，可包含多道工序，且各工序間的加工順序固定已知。由于工序具有柔性的加工路徑，其加工時間取決于被分配機(jī)器的生產(chǎn)能力。通常情況下，車間內(nèi)所有工件的最大完工時間是評價該車間調(diào)度性能的重要指標(biāo)之一，由其引起的成本為完工時間成本。然而，在當(dāng)今低碳經(jīng)濟(jì)的大環(huán)境下，企業(yè)在完成生產(chǎn)任務(wù)的同時，還必須重視車間內(nèi)的能耗成本。

本文主要考慮車間內(nèi)機(jī)器的兩種工作狀態(tài)，即加工和空載，其所對應(yīng)的能耗分別為負(fù)載能耗和空載能耗。為了描述車間內(nèi)的能耗成本，可預(yù)先定義各工序在不同機(jī)器上單位時間內(nèi)的平均加工能耗成本及機(jī)器空載運(yùn)行單位時間內(nèi)的平均能耗成本。對于本文的低碳調(diào)度問題，由于不同機(jī)器加工工序的單位時間能耗成本不同，首先要為工序分配合適的機(jī)器。此外，還應(yīng)合理安排機(jī)器上工序的加工順序，從而盡可能地減少機(jī)器空載能耗成本。因此，本文柔性作業(yè)車間低碳調(diào)度問題與一般柔性作業(yè)車間調(diào)度問題類似，均包含機(jī)器分配和工序排序兩個子問題。

對于該問題，存在以下假設(shè)：①工件和機(jī)器在初始零時刻均處于可用狀態(tài);②每臺機(jī)器同時只可加工一個工件;③工件加工過程具有不可中斷性;④假設(shè)不同工件間相互獨(dú)立，僅考慮同工件不同工序間的先后約束關(guān)系;⑤不考慮工序加工前機(jī)器的準(zhǔn)備時間;⑥車間內(nèi)各機(jī)器空閑時不停機(jī)。

1.2 模型建立

根據(jù)問題描述，確定本文低碳調(diào)度問題的優(yōu)化目標(biāo)是使車間內(nèi)完工時間成本和能耗成本二者的加權(quán)和最小，建立如下數(shù)學(xué)模型：

(1)

s.t.

(2)

STi(j+1)≥CTij,

i=1,2,…,n,j=1,2,…,Ji-1;

(3)

STi′j′+ξ(1-ziji′j′k)≥CTij,i,i′=1,2,…,n,j,

j′=1,2,…,Ji,k=1,2,…,m;

(4)

STij+ξziji′j′k≥CTi′j′,i,i′=1,2,…,n,j,

j′=1,2,…,Ji;k=1,2,…,m,

(5)

(6)

yijk∈{0,1},i=1,2,…,n,j=1,2,…,Ji,

k=1,2,…,m;

(7)

ziji′j′k∈{0,1},i,i′=1,2,…,n,

j,j′=1,2,…,Ji,k=1,2,…,m。

(8)

其中：式(1)表示使車間內(nèi)的總成本最小，其中第一項(xiàng)表示能耗成本，第二項(xiàng)表示完工時間成本；式(2)表示工序一旦開始加工不可中斷；式(3)表示同工件的各工序間先后約束關(guān)系；式(4)和式(5)表示各機(jī)器同時只能加工一個工件；式(6)表示各工序只可被分配至一臺機(jī)器；式(7)和式(8)均表示0-1變量。式中:n為車間內(nèi)工件數(shù)；m為車間內(nèi)機(jī)器數(shù)；Ji為工件i的總工序數(shù)；OPij為工件i的第j道工序；pijk為工序OPij在機(jī)器k上的處理時間；λijk為工序OPij在機(jī)器k上加工時單位時間平均能耗成本；θk為機(jī)器k空載時單位時間平均能耗成本；κ為車間內(nèi)單位時間完工成本；STij為工序OPij的開始時間；CTij為工序OPij的完工時間；ξ為較大的常數(shù)；CS為車間內(nèi)加權(quán)總成本；CTk為機(jī)器k的完工時間；Wk為機(jī)器k的負(fù)載；CTmax為所有工件的最大完工時間；μ1,μ2為權(quán)重系數(shù)，無特殊說明時，本文取為(0.7,0.3)；yijk為0-1變量，若OPij在機(jī)器k上加工yijk為1，否則為0；ziji′j′k為0-1變量，若工序Oij先于工序Oi′j′在機(jī)器k上加工則ziji′j′k=1，否則ziji′j′k=0。

2 基本灰狼優(yōu)化算法

灰狼優(yōu)化算法是一種基于群智能的元啟發(fā)式算法，它是通過模擬狼群的社會等級及捕食行為機(jī)制而提出的[13]。一個狼群的社會等級可劃分為頭狼α、下屬狼β、普通狼δ和底層狼ω四層，其中α負(fù)責(zé)領(lǐng)導(dǎo)狼群，β協(xié)助α做出決策，δ聽從α和β的指令，也可以指揮底層個體ω。灰狼優(yōu)化算法中的α,β和δ分別表示歷史最優(yōu)解、次優(yōu)解和第三最優(yōu)解，ω表示其余個體。算法進(jìn)化過程中，α,β和δ負(fù)責(zé)定位獵物的位置，并引導(dǎo)其他個體完成靠近、包圍和攻擊等行為，最終達(dá)到捕食獵物的目的,該過程可表示為：

D=|C·Xp(t)-X(t)|;

(9)

X(t+1)=Xp(t)-A·D;

(10)

A=2ar1-a;

(11)

C=2r2;

(12)

Dα=|C1·Xα(t)-X(t)|,

Dβ=|C2·Xβ(t)-X(t)|,

Dδ=|C3·Xδ(t)-X(t)|;

(13)

X1=Xα(t)-A1·Dα,

X2=Xβ(t)-A2·Dβ,

X3=Xδ(t)-A3·Dδ;

(14)

(15)

其中:D表示獵物與灰狼間的距離；t表示當(dāng)前迭代次數(shù)；A和C表示協(xié)同系數(shù)向量；Xp表示獵物位置向量；X表示灰狼的個體位置向量；a中元素在迭代過程中由2線性遞減到0；r1和r2均表示隨機(jī)數(shù)向量。由式(13)和式(14)計(jì)算出個體與α,β和δ的距離，然后由式(15)確定個體向獵物移動的方向。限于篇幅，灰狼優(yōu)化算法的具體原理和步驟詳見文獻(xiàn)[13]。

3 改進(jìn)灰狼優(yōu)化算法

3.1 編碼機(jī)制

由于同樣包含機(jī)器分配和工序排序兩個子問題，本文算法中灰狼個體采用長度相等的兩段編碼，前后段分別表示機(jī)器分配方案和工序排序方案，即若個體位置向量的長度為2l，則X={x(1),x(2),…,x(l),x(l+1),…,x(2l)}，各元素可在一定范圍內(nèi)任意取值。假設(shè)現(xiàn)有3個待加工工件，各工件均包含兩道工序，則X的總長度為12，各元素在[-2,2]中任意取值，并按照固定的順序存儲，個體位置向量如圖1所示。

3.2 解碼機(jī)制

3.3 種群初始化

根據(jù)個體位置向量的基本形式，分別針對機(jī)器分配和工序排序兩部分進(jìn)行種群初始化。機(jī)器分配部分采用文獻(xiàn)[20]中的啟發(fā)式算法，即全局搜索、局部搜索和隨機(jī)生成3種方式相結(jié)合來獲得初始機(jī)器分配方案，而工序排序部分則采用文獻(xiàn)[21]中基于搜索的方法，即對任意一個已獲得的機(jī)器分配方案，根據(jù)工件和工序的數(shù)量隨機(jī)生成多個排序方案，然后評價每一個排序方案與該機(jī)器分配方案的組合，選擇最優(yōu)的一組作為一個初始調(diào)度解，不斷重復(fù)前述過程，直到生成初始種群為止。

3.4 收斂因子非線性調(diào)整策略

根據(jù)文獻(xiàn)[13]可知，灰狼優(yōu)化算法中的參數(shù)A對算法性能起著非常重要的作用。當(dāng)|A|>1時，狼群可通過擴(kuò)大包圍圈來尋找更好的解，此時算法具有較強(qiáng)的探索能力；當(dāng)|A|<1時，狼群可通過收縮包圍圈對獵物發(fā)起攻擊，此時算法具有較強(qiáng)的開發(fā)能力[13]。根據(jù)式(11)可知，A的值取決于收斂因子a的值的變化。然而在基本灰狼優(yōu)化算法中，a在0和2之間隨迭代次數(shù)的增加而線性地減小，無法更好地協(xié)調(diào)算法探索和開發(fā)的能力。因此，收斂因子非線性調(diào)整策略的目的是使算法在運(yùn)行初期能夠側(cè)重于全局搜索，并在運(yùn)行后期側(cè)重于局部搜索。對此，本文將文獻(xiàn)[22]中3種慣性權(quán)重非線性調(diào)整策略(正弦曲線、正切曲線和對數(shù)曲線)應(yīng)用于灰狼優(yōu)化算法收斂因子的調(diào)整，并定義相應(yīng)算法為SinGWO,TanGWO和LnGWO。

3.5 個體位置更新方法

在基本灰狼優(yōu)化算法的搜索過程中，個體由α,β和δ引導(dǎo)進(jìn)行自身位置信息更新，但卻未能體現(xiàn)出三者在狼群中處于不同等級而發(fā)揮不同的領(lǐng)導(dǎo)作用，如式(15)所示。對此，本文采用文獻(xiàn)[23]帶權(quán)重系數(shù)(τ1,τ2,τ3)的個體位置更新策略，如式(16)～式(18)所示，其中α,β和δ的個體適應(yīng)度值fα,fβ和fδ根據(jù)式(19)進(jìn)行計(jì)算:

X(t+1)=τ1X1+τ2X2+τ3X3;

(16)

(17)

F(t)=fα(t)+fβ(t)+fδ(t);

(18)

(19)

3.6 局部搜索

為了避免算法陷入局部最優(yōu)解，將局部搜索算法嵌入到灰狼優(yōu)化算法中，并在每次迭代中均作用于α，β和δ3個個體，從而改善算法性能。局部搜索算法中，針對個體位置向量設(shè)計(jì)3種鄰域結(jié)構(gòu)：

(1)鄰域結(jié)構(gòu)N1在工序排序中任選兩個元素，所選元素需對應(yīng)不同工件的工序，然后對所選元素進(jìn)行交換操作。

(2)鄰域結(jié)構(gòu)N2在工序排序部分中任選兩個元素，然后將后一元素插入到前一元素之前的位置。

(3)鄰域結(jié)構(gòu)N3在機(jī)器分配部分任選一個元素，該元素對應(yīng)工序的可選機(jī)器應(yīng)多于一臺，然后將該工序分配至不同的機(jī)器上，并根據(jù)文獻(xiàn)[19]中的方法生成新的元素值。

基于上述鄰域結(jié)構(gòu)，局部搜索算法的具體步驟如下：

步驟1獲取初始解X，并設(shè)置閾值ψ>0，ρ←1，υ←1及終止迭代次數(shù)ρmax。

步驟2若υ=1，則X′←N1(X)∪N3(X)；若υ=0，則X′←N2(X)∪N3(X)。

步驟3判斷CS(X′)-CS(X)≤ψ是否滿足。若是，則X←X′；否則,設(shè)置υ←|υ-1|。

步驟4令ρ←ρ+1，并判斷ρ>ρmax是否滿足。若是，則X′←X，轉(zhuǎn)步驟5；否則，轉(zhuǎn)步驟2。

步驟5算法結(jié)束。

3.7 算法步驟

本文灰狼優(yōu)化算法的具體步驟如下：

步驟1設(shè)置算法參數(shù)并根據(jù)3.3節(jié)中的方法創(chuàng)建初始種群。

步驟2評估種群中個體的適應(yīng)度值，并按照適應(yīng)度值從大到小確定α,β和δ。

步驟3對α,β和δ執(zhí)行局部搜索，然后根據(jù)適應(yīng)度值的大小對其進(jìn)行更新。

步驟4根據(jù)式(13)、式(14)和式(16)更新個體位置信息。

步驟5判斷算法是否達(dá)到最大迭代次數(shù)。若是，則轉(zhuǎn)步驟6；否則，轉(zhuǎn)步驟2。

步驟6終止算法并輸出最優(yōu)結(jié)果。

為了更清晰地描述算法步驟，本文算法流程如圖3所示。

4 算例仿真

采用Fortran程序設(shè)計(jì)語言，在WinXP系統(tǒng)下、內(nèi)存2 G的Pentium CPU G2030 @3.00 GHz, 2.99 GHz計(jì)算機(jī)上運(yùn)行。由于本文算法參數(shù)較少，采用通用的實(shí)驗(yàn)法進(jìn)行參數(shù)設(shè)置，即種群大小為100，最大迭代次數(shù)為800，局部搜索終止迭代次數(shù)ρmax=10。對于本文算例，按照隨機(jī)生成的方法獲得10個算例(RM01～RM10)進(jìn)行仿真，各算法針對不

同算例分別獨(dú)立運(yùn)行10次后取平均值進(jìn)行比較。對于RM01～RM10，機(jī)器數(shù)和工件數(shù)如表1～表3所示，其他數(shù)據(jù)取值服從一定范圍內(nèi)的離散型均勻分布，即工件工序數(shù)在[1,5]內(nèi)取值，工序加工時間pijk在[1,20]內(nèi)取值，機(jī)器負(fù)載單位時間平均能耗成本λijk在[10,15]內(nèi)取值，機(jī)器空載單位時間平均能耗成本θk在[10,15]內(nèi)取值。此外，車間單位時間完工成本κ=30。采用隨機(jī)的方式確定各工序的可加工機(jī)器集，即對于一臺機(jī)器，若隨機(jī)產(chǎn)生的隨機(jī)數(shù)大于0.5，則該機(jī)器為對應(yīng)工序的一臺可加工機(jī)器。

表1 不同收斂因子下算法性能分析

表2 算法其他改善機(jī)制有效性分析

表3 算法有效性分析

續(xù)表3

首先對采用不同收斂因子的算法的性能進(jìn)行分析，其中LGWO，SinGWO，TanGWO和LnGWO分別對應(yīng)按線性遞減、正弦曲線、正切曲線和對數(shù)曲線調(diào)整收斂因子，對比結(jié)果如表1所示，其中粗體表示算法在相應(yīng)算例下表現(xiàn)相對最優(yōu)。由表1中數(shù)據(jù)可以看出，SinGWO,TanGWO和LnGWO 3種算法在多數(shù)情況下均優(yōu)于LGWO算法，且三者中SinGWO算法的計(jì)算結(jié)果最好。

基于表1的數(shù)據(jù)，在SinGWO的基礎(chǔ)上驗(yàn)證算法其他改善機(jī)制的有效性，即種群初始化方法、個體更新策略和局部搜索操作，對比結(jié)果如表2所示。其中SinGWO1表示將SinGWO算法中的種群初始化方法改為隨機(jī)生成的方式；SinGWO2表示將SinGWO算法中的個體更新策略改為按照式(15)進(jìn)行；SinGWO3表示在SinGWO算法中去除局部搜索算法。由表2數(shù)據(jù)可以看出，SinGWO算法在大多數(shù)情況下能夠獲得相對較好的結(jié)果，由此驗(yàn)證了本文算法改善機(jī)制的有效性。此外，圖4和圖5分別給出了SinGWO算法所獲得的RM05和RM06算例的調(diào)度方案甘特圖，每個方框表示一道工序，方框下方表示工序編號，例如“15-1”表示工件15的第1道工序。

為了進(jìn)一步測試算法的性能，分別針對不同權(quán)重系數(shù)下的目標(biāo)函數(shù)進(jìn)行計(jì)算，并將SinGWO算法與文獻(xiàn)[18]中的有效型遺傳算法(Effective Genetic Algorithm, EGA)進(jìn)行對比，如表3所示。其中，EGA算法參數(shù)為種群大小為100，交叉率為0.8，變異率為0.1，最大迭代次數(shù)為2 000。由表3數(shù)據(jù)可以看出，SinGWO算法結(jié)果明顯優(yōu)于EGA算法。

為了充分驗(yàn)證本文算法的有效性，以最小化工件最大完工時間為目標(biāo)，將本文算法用于求解傳統(tǒng)柔性作業(yè)車間調(diào)度問題。在基準(zhǔn)Brandimarte算例[24]的基礎(chǔ)上，算法獨(dú)立運(yùn)行10次獲取最佳值，然后與其他已有算法進(jìn)行比較，如表4所示。其中，粗體表示相同算例下各算法結(jié)果中的最佳值，“-”表示相關(guān)文獻(xiàn)中沒有給出對應(yīng)的結(jié)果。從表4的數(shù)據(jù)可以看出，在算例個數(shù)相同的情況下，SinGWO算法與文獻(xiàn)[25-26]算法獲得最佳值的個數(shù)相同，文獻(xiàn)[24]算法的結(jié)果最差。

為了能夠更清晰地體現(xiàn)本文算法的優(yōu)越性，將上述4種算法的相對百分比偏差值進(jìn)行比較，如表5所示。令RPD表示相對百分比偏差，RPD=100×(Min-Best)/Best，其中：Best表示4種算法所獲各算例結(jié)果的最佳值，Min表示各算法10次運(yùn)行中獲得的最佳值，Mean表示各算法RPD的平均值。由表5可以看出，SinGWO算法的Mean值最小。

表4 Brandimarte算例的計(jì)算結(jié)果

表5 RPD值的比較結(jié)果

5 結(jié)束語

本文針對柔性作業(yè)車間低碳調(diào)度問題進(jìn)行了研究，并對新型灰狼優(yōu)化算法進(jìn)行了一系列設(shè)計(jì)和改進(jìn)，用于該問題的求解。主要內(nèi)容概括如下：

(1)采用兩段式編碼機(jī)制及基于啟發(fā)式算法的種群初始化方法；設(shè)計(jì)了種群初始化方法，以確保種群的質(zhì)量和多樣性；設(shè)計(jì)了收斂因子非線性調(diào)整策略和帶權(quán)重系數(shù)的個體位置更新方法，作用于算法進(jìn)化過程；引入嵌入局部搜索策略，用于加強(qiáng)局部搜索能力。

(2)針對10個隨機(jī)生成的算例進(jìn)行仿真，驗(yàn)證了算法改善機(jī)制的有效性，并通過與其他文獻(xiàn)算法比較，進(jìn)一步測試了算法解決該問題的有效性。

(3)針對傳統(tǒng)柔性作業(yè)車間調(diào)度問題基準(zhǔn)算例進(jìn)行仿真，充分現(xiàn)了本文算法的優(yōu)越性。

下一步將把灰狼優(yōu)化算法擴(kuò)展至更復(fù)雜車間調(diào)度問題中，并結(jié)合車間特點(diǎn)，設(shè)計(jì)出更有效的算法。