基于改進(jìn)斑點(diǎn)鬣狗算法的作業(yè)車間協(xié)同調(diào)度*

董 海，范英建

(沈陽大學(xué)a.應(yīng)用技術(shù)學(xué)院；b.機(jī)械工程學(xué)院，沈陽 110044)

0 引言

如今在云制造的大背景下，制造企業(yè)通常采用分布式柔性作業(yè)車間進(jìn)行生產(chǎn)[1-2]，分布式柔性作業(yè)車間相比于其他作業(yè)車間，其更貼近于企業(yè)的綠色制造模式，實(shí)現(xiàn)經(jīng)濟(jì)與環(huán)境的高度平衡。

分布式作業(yè)車間調(diào)度問題(distributed job-shop scheduling problem，DJSP)是典型的NP-hard問題。合理的調(diào)度方案能有效減少資源消耗和環(huán)境污染，因此DJSP問題也成為國內(nèi)外學(xué)者廣泛研究的熱點(diǎn)問題。目前，對于求解DJSP問題，精確算法已經(jīng)不適應(yīng)大規(guī)模通用性問題，近似算法中的智能算法因其求解效率高、求解速度快而被廣泛應(yīng)用[3]。吳銳等[4]提出一種改進(jìn)人工蜂群算法，設(shè)計(jì)了多種有效的進(jìn)化操作算子，并引入基于關(guān)鍵路徑的局部搜索算子。吳秀麗等[5]同時優(yōu)化模型的總成本和提前/延期懲罰，提出改進(jìn)的差分進(jìn)化算法，設(shè)計(jì)了兩種變異機(jī)制以及兩種交叉方式。郭晨等[6]提出了一種混合差分搜索及變鄰域搜索的分布估計(jì)算法，提出基于概率模型的相似系數(shù)和兩種變異算子，并且設(shè)計(jì)了5種變鄰域結(jié)構(gòu)。孟磊磊等[7]提出一種混合蛙跳算法解決DFJSP，引入變鄰域搜索算法提升蛙跳算法的局部搜索能力。CHAOUCH等[8]建立一種新的工廠作業(yè)動態(tài)分配規(guī)則，提出一種結(jié)合局部搜索的混合蟻群算法解決DJSP。XIE等[9]提出一種多目標(biāo)人工蜂群算法，構(gòu)造混合整數(shù)規(guī)劃模型，使其完工時間和總能耗兩目標(biāo)達(dá)到平衡。MAHMOODJANLOO等[10]設(shè)計(jì)了一種自適應(yīng)差分進(jìn)化算法，提出2個基于位置和序列的決策變量MILP模型。ZHANG等[11]基于分布式裝配車間調(diào)度問題，提出一種元啟發(fā)式算法，將蟻群算法的局部搜索能力提高。XU等[12]針對考慮作業(yè)外包的分布式柔性作業(yè)車間調(diào)度問題，提出一種具有三層編碼的混合遺傳禁忌搜索算法。MOU等[13]提出了一種基于學(xué)習(xí)機(jī)制的雙種群協(xié)同搜索機(jī)制，同時解決最大完工時間和能源消耗的雙控問題。

斑點(diǎn)鬣狗算法最早是由DHIMAN等[14]提出的一種優(yōu)化算法，其主要模擬了斑點(diǎn)鬣狗的狩獵行為。近年來，斑點(diǎn)鬣狗算法在電網(wǎng)調(diào)度[15]、旅行商問題[16]等方面展開應(yīng)用，然而針對本文DJSP，鮮有研究。

因此，本文根據(jù)DJSP特性，設(shè)計(jì)一種離散型斑點(diǎn)鬣狗算法(discrete spotted hyena optimization，DSHO)應(yīng)用于求解DJSP問題。利用斑點(diǎn)鬣狗算法的聚集特性控制多樣性，使得在斑點(diǎn)鬣狗算法的搜索空間中創(chuàng)建各種候選解，提高算法的局部搜索能力，并且將貪婪啟發(fā)式方法應(yīng)用到作業(yè)排序階段，消除冗余排列，提供更好的作業(yè)排序，縮短相關(guān)設(shè)施的完工時間，減少機(jī)器能耗。

1 分布式作業(yè)車間調(diào)度

1.1 問題描述

分布式作業(yè)車間調(diào)度問題(DJSP)主要面臨兩大挑戰(zhàn)，第一是將合適的作業(yè)分配給合適的設(shè)備；第二是對機(jī)器上作業(yè)進(jìn)行排序，達(dá)到最小化最大完工時間的目標(biāo)。分布式作業(yè)車間調(diào)度問題(DJSP)可描述為如下：云數(shù)據(jù)庫里有n個工件需要加工，協(xié)調(diào)分配給f個工廠，工件交給m臺機(jī)器進(jìn)行加工制造，工件在特定機(jī)器上操作具有固定的時間預(yù)計(jì)值，且加工時間和能耗各不相同。為方便建立數(shù)學(xué)模型和分析問題，給出如下假設(shè)：

①所有機(jī)器與工件都是相互獨(dú)立且在0時刻都可工作或被加工；

②一個工件只能在一個時間被一臺機(jī)器加工；

③一臺機(jī)器只能加工一個工件，并且一旦加工不可中斷；

④一個工件只可選擇一個工廠進(jìn)行加工，不可跨工廠進(jìn)行操作；

⑤不同工件之間無優(yōu)先級排序，同一工件有工序順序約束；

⑥忽略工件在工廠的設(shè)備的運(yùn)輸時間，只計(jì)算機(jī)器加工時間。

1.2 符號說明

本文以最大完工時間及總能耗最小化建立數(shù)學(xué)模型。為便于模型的建立和描述，定義符號和變量如表1所示。

表1 符號和變量

續(xù)表

1.3 DJSP數(shù)學(xué)模型

針對DJSP問題，本文構(gòu)建了一種MILP數(shù)學(xué)模型，實(shí)現(xiàn)工序的可排序化，相關(guān)公式如下：

Min(Cmax,TEC)

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(Si,t+Wi,t,z)yi,j,t≤Si,j,?i,t,j≠t,z

(8)

Sr,j+Wr,j,z≤Si,j+U(1-xr,i,j,k),?r>0,i≠r,j,k,z

(9)

Sj,k≤Si,j+U(1-x0,i,j,k),?i,j,k

(10)

(11)

Si,j+Wi,j,z≤Qi,j,?i,j,z

(12)

Qi,j≤Cmax,?i,j

(13)

(14)

(15)

EIj=ψj/4

(16)

(17)

xr,i,j,k∈{0,1}

(18)

yi,j,t∈{0,1}

(19)

hi,j,z∈{0,1}

(20)

其中，式(1)表示目標(biāo)函數(shù)，式(2)表示每個工件只能分配到一個工廠的約束，式(3)、式(4)用來約束同一工作的所有操作必須分配到滿足加工路線的同一工廠中，式(5)表示每臺機(jī)器上的第一個作業(yè)，式(6)表示在任何機(jī)器上，任何一個工件不能在另一個作業(yè)之前和之后相鄰，式(7)、式(8)表示在同一時間，一個工件最多只能在一臺機(jī)器上進(jìn)行處理，式(9)表示在同一時間，一臺機(jī)器最多只能處理一個工件，式(10)確定每臺機(jī)器的啟動時間，式(11)表示每個工廠的完工時間約束，式(12)、式(13)用來約束最大完工時間，式(14)用來約束每個操作都以同一種速度進(jìn)行，式(15)表示機(jī)器加工能耗，式(16)表示機(jī)器閑置下的能耗，式(17)表示生產(chǎn)總能耗，式(18)～式(20)定義決策變量。

2 斑點(diǎn)鬣狗算法求解DJSP

2.1 斑點(diǎn)鬣狗算法介紹

斑點(diǎn)鬣狗算法是一個基于生物模仿的元啟發(fā)式算法，描述了斑點(diǎn)鬣狗的社會關(guān)系和狩獵技術(shù)，模仿斑點(diǎn)鬣狗在自然界的行為[17]。通過式(21)在預(yù)定的搜索空間里隨機(jī)均勻生成斑點(diǎn)鬣狗種群：

Pij=Lj+φ*(Hj-Lj)

(21)

式中，Pij為斑點(diǎn)鬣狗所在位置的第j維度；Lj為搜索空間的下限的第j維度；Hj為搜索空間的上限第j維度；φ為0～1中的隨機(jī)數(shù)值。斑點(diǎn)鬣狗算法分別使用了包圍、獵狩和攻擊三種手段，通過式(22)～式(26)進(jìn)行模擬。

A=2a·r1-a

(22)

C=2·r2

(23)

a=5-(t*(5/tmax))

(24)

D=|C·P*-P|

(25)

P(t+1)=P*(t)-A·D

(26)

圖1 斑點(diǎn)鬣狗種群獵狩

式中，D表示斑點(diǎn)鬣狗到獵物的距離矢量；P*表示獵物的位置矢量；P表示斑點(diǎn)鬣狗的位置矢量；A、C表示系數(shù)向量；t表示當(dāng)前迭代次數(shù)；tmax表示最大迭代次數(shù)；a表示每次迭代由5減少到0；r1和r2為0～1中的隨機(jī)數(shù)值。同時斑點(diǎn)鬣狗是一個群體獵狩種族，同伴間有著良好的信息交流能力，有時會召集同伴一起參與獵狩，如圖1所示。其行為通過式(27)～式(29)進(jìn)行模擬：

D=|C·Pbest-Pk|

(27)

Pk=Pbest-A·D

(28)

(29)

式中，Pbest表示迭代后斑點(diǎn)鬣狗最好的位置矢量；Pk表示斑點(diǎn)鬣狗的同伴位置矢量；Ch表示斑點(diǎn)鬣狗群體；M表示絕對值在0.5～0之間的隨機(jī)向量；N表示加上M之后最容易接近獵物的斑點(diǎn)鬣狗的位置矢量。在攻擊階段，所有的斑點(diǎn)鬣狗的動作通過式(30)進(jìn)行模擬。

P(t+1)=Ch/N

(30)

2.2 離散編碼

在斑點(diǎn)鬣狗算法中，斑點(diǎn)鬣狗位置的初始向量不是用離散值生成的，且其只能表示順序關(guān)系，并不能表示工作處理的順序，所以需要對斑點(diǎn)鬣狗的位置值進(jìn)行離散型編碼。本文采用一種隨機(jī)型離散編碼方法(RK)對斑點(diǎn)鬣狗進(jìn)行編碼，將連續(xù)變量映射到作業(yè)索引編碼方案中。假設(shè)現(xiàn)有兩個工件，每個工件需要3道工序，引入實(shí)數(shù)數(shù)值，采用RK方式將連續(xù)值轉(zhuǎn)換為離散值，如表2所示。

表2 作業(yè)編碼映射方案

在表2中，斑點(diǎn)鬣狗的連續(xù)值(Pij)位于第一行，排序索引(Sij)位于第二行，工序索引通過式(31)計(jì)算出來。

φij=(Sijmodn)+1

(31)

式中，φij表示工序索引中的第j維度的第i只斑點(diǎn)鬣狗；Sij表示第j維度的第i只斑點(diǎn)鬣狗的位置；n表示工件數(shù)量。

在這個離散化階段結(jié)束時，可以對操作序列進(jìn)行編碼，采用RK之后，操作向量的作業(yè)處理序列可以被正確映射。

2.3 工作負(fù)載規(guī)則

本文同時考慮機(jī)器的處理時間和機(jī)器的作業(yè)順序，以每臺機(jī)器的負(fù)載作為分配規(guī)則，并且將之稱為工作負(fù)載規(guī)則。在工作負(fù)載規(guī)則中，使用等式(32)評估機(jī)器的工作負(fù)載。

(32)

式中，m是每臺機(jī)器的索引；M是機(jī)器的集合；j是作業(yè)的索引；J是作業(yè)的集合；k是當(dāng)前機(jī)器的索引；PM是前面機(jī)器的集合；PT是處理時間矩陣。

為更好地描述并解釋DJSP中的工作負(fù)載規(guī)則，列舉出一個數(shù)值實(shí)例，其中f=2，n=5，m=3(f表示設(shè)備數(shù)量，n表示工序數(shù)量，m表示作業(yè)數(shù)量)。實(shí)例的處理時間和工序排列和作業(yè)處理的工作量分別如表3和表4所示。

表3 作業(yè)處理時間和工序

表4 作業(yè)處理的工作量

基于式(32)計(jì)算作業(yè)的總工作量，作業(yè)按降序排列為{2，3，4，1，5}，并在表4中列出。工作設(shè)施分配被編碼為一個向量，設(shè)施作業(yè)分配為{1，1，2，2，2}，則表明作業(yè)1和2將分配給第一個設(shè)施，作業(yè)3、4和5將分配給第二個設(shè)施。

2.4 設(shè)施中的作業(yè)排序

在DJSP中，工作負(fù)載規(guī)則確定后，需要對每個設(shè)施的作業(yè)進(jìn)行適當(dāng)排序。作業(yè)被編碼為操作向量，編碼向量中的第一個參數(shù)表示相關(guān)作業(yè)的第一次操作，在向量中再次看到相同參數(shù)的位置，其表示該作業(yè)的第二次操作，并繼續(xù)以此類推。

向量中所述作業(yè)的所有操作分別使用貪婪啟發(fā)式逐個執(zhí)行。貪婪啟發(fā)式中存在兩個冗余狀態(tài)，如果α是通過交換兩個操作而產(chǎn)生的置換β，并且兩個操作屬于相同的作業(yè)，則其是冗余置換。如果α是通過交換不同機(jī)器處理中的不同作業(yè)的兩個操作或者兩個相鄰操作而產(chǎn)生的置換β，則也是冗余置換。在貪婪啟發(fā)式中，一些冗余排列不被評估以獲得計(jì)算時間優(yōu)勢。評估向量中操作的排列，選擇提供最小完工時間的最佳解決方案的排列，得到最終的工序排序。

2.5 算法流程

離散型斑點(diǎn)鬣狗算法的流程圖如圖2所示。首先錄入DJSP相關(guān)數(shù)據(jù)，根據(jù)工作負(fù)載規(guī)則，將具體作業(yè)分配給某一設(shè)備。然后使用RK作業(yè)索引將每個斑點(diǎn)鬣狗的連續(xù)位置轉(zhuǎn)換為操作向量，用貪婪啟發(fā)式重組設(shè)備的操作向量，以提高解決方案的質(zhì)量。計(jì)算每個設(shè)施的操作向量的最大完工時間和生產(chǎn)能耗，并將設(shè)施的最大完工時間和生產(chǎn)能耗確定為目標(biāo)函數(shù)(Cmax、TEC)。在分別達(dá)到指定的終止標(biāo)準(zhǔn)之前，更新斑點(diǎn)鬣狗的位置，通過RK作業(yè)索引使其離散化，使用貪婪啟發(fā)式改進(jìn)作業(yè)序列，并存儲最佳解。最后，當(dāng)滿足終止標(biāo)準(zhǔn)時，獲得的最小完工時間和能耗最小(Cmax、TEC)報告為最佳解決方案。

圖2 離散型斑點(diǎn)鬣狗算法流程圖

3 試驗(yàn)驗(yàn)證

算法程序是在MATLAB上進(jìn)行編碼的，仿真實(shí)驗(yàn)是在具有Windows Server 2016操作系統(tǒng)的Intel(R)Core(TM)i5-6700CPU3.4 GHz和8.00 GB內(nèi)存的PC機(jī)上進(jìn)行的。通過大量試驗(yàn)表明將迭代參數(shù)設(shè)置為500，c1和c2參數(shù)都設(shè)置為2時，算法性能較好，因此本文采用該參數(shù)組合。

為驗(yàn)證DSHO的優(yōu)劣性，本文將DSHO與離散型粒子群算法(discrete particle swarm optimization，DPSO)，動態(tài)局部蟻群算法(ant colony optimization and local search procedure and dynamic assignment，DAHACO)，局部蟻群算法(ant colony optimization and local search procedure，HACO)，蟻群算法(ant colony optimization，ACO)等算法進(jìn)行對比進(jìn)行比較，選用15個作業(yè)和15臺機(jī)器到500個作業(yè)和20臺機(jī)器，基準(zhǔn)實(shí)例的維度介于225～2000之間，設(shè)施數(shù)量使用2～7個工廠來解決DJSP問題。算法求解后采用相對百分比偏差(relative percentage deviation，RPD)用以比較DSHO和其他算法的性能差異。PRD 的值計(jì)算如下：

(33)

式中，alg是通過相關(guān)算法獲得的最大完工時間；min是給定實(shí)例的最小完工時間。為了評估算法在不同設(shè)施數(shù)量下的性能，圖3繪制了不同設(shè)施數(shù)量算法平均RPD結(jié)果。

圖3 不同設(shè)施數(shù)量下各種算法的RPD

如圖3所示，當(dāng)設(shè)施數(shù)量為2時，算法差異較大，隨著設(shè)施的數(shù)量增加，可以更有效地組織生產(chǎn)操作，算法之間的RPD差異減小。

在2個、3個和4個分布式設(shè)施的80個基準(zhǔn)案例上，DSHO都獲得了最佳解決方案；在5個分布式設(shè)施中，DSHO獲得了78個基準(zhǔn)問題的最佳解決方案；在6個分布式設(shè)施中，DSHO獲得了79個基準(zhǔn)問題的最佳解決方案；在7個分布式設(shè)施中，獲得了77個基準(zhǔn)問題的最佳解決方案。因此，DSHO在最大完工時間方面優(yōu)于DPSO、DAHACO、HACO和ACO。圖4為采用DSHO算法在7個分布式設(shè)備數(shù)量下Tai76案例第四分布式設(shè)備上的作業(yè)序列，設(shè)施4的最大完工時間值為1640。

圖4 分布式設(shè)備4的最佳調(diào)度方案

式(34)為Friedman測試中評價各算法的指標(biāo)函數(shù)，其中參數(shù)k和N分別是算法的數(shù)量和實(shí)例的數(shù)量，qa取3.091。

(34)

Friedman檢驗(yàn)同樣是在MATLAB上進(jìn)行，數(shù)據(jù)如表5所示，F(xiàn)riedman檢驗(yàn)等級如圖5所示，該圖表明DSHO明顯優(yōu)于其他比較算法。

表5 Friedman檢驗(yàn)平均值

圖5 Friedman檢驗(yàn)等級

4 結(jié)論

本文以云制造分布式柔性作業(yè)車間為研究對象，將工作負(fù)載規(guī)則和貪婪啟發(fā)式算法融合到離散型斑點(diǎn)鬣狗算法中，提出一種新的離散型斑點(diǎn)鬣狗優(yōu)化算法。經(jīng)驗(yàn)證得到以下結(jié)論：

(1)離散型斑點(diǎn)鬣狗算法應(yīng)用于分布式作業(yè)車間調(diào)度優(yōu)化是有效的，可以有效減少完工時間、車間總能耗。

(2)離散型斑點(diǎn)鬣狗算法在相對百分比偏差、最佳實(shí)驗(yàn)方案和算法穩(wěn)定性等指標(biāo)均優(yōu)于其他智能算法。