董 海，范英建

(沈陽大學a.應用技術學院；b.機械工程學院，沈陽 110044)

0 引言

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

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

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

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

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

1.1 問題描述

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

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

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

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

④一個工件只可選擇一個工廠進行加工，不可跨工廠進行操作；

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

⑥忽略工件在工廠的設備的運輸時間，只計算機器加工時間。

1.2 符號說明

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

表1 符號和變量

續(xù)表

1.3 DJSP數(shù)學模型

針對DJSP問題，本文構建了一種MILP數(shù)學模型，實現(xià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)表示目標函數(shù)，式(2)表示每個工件只能分配到一個工廠的約束，式(3)、式(4)用來約束同一工作的所有操作必須分配到滿足加工路線的同一工廠中，式(5)表示每臺機器上的第一個作業(yè)，式(6)表示在任何機器上，任何一個工件不能在另一個作業(yè)之前和之后相鄰，式(7)、式(8)表示在同一時間，一個工件最多只能在一臺機器上進行處理，式(9)表示在同一時間，一臺機器最多只能處理一個工件，式(10)確定每臺機器的啟動時間，式(11)表示每個工廠的完工時間約束，式(12)、式(13)用來約束最大完工時間，式(14)用來約束每個操作都以同一種速度進行，式(15)表示機器加工能耗，式(16)表示機器閑置下的能耗，式(17)表示生產(chǎn)總能耗，式(18)～式(20)定義決策變量。

2 斑點鬣狗算法求解DJSP

2.1 斑點鬣狗算法介紹

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

Pij=Lj+φ*(Hj-Lj)

(21)

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

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 斑點鬣狗種群獵狩

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

D=|C·Pbest-Pk|

(27)

Pk=Pbest-A·D

(28)

(29)

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

P(t+1)=Ch/N

(30)

2.2 離散編碼

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

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

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

φij=(Sijmodn)+1

(31)

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

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

2.3 工作負載規(guī)則

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

(32)

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

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

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

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

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

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

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

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

2.5 算法流程

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

圖2 離散型斑點鬣狗算法流程圖

3 試驗驗證

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

為驗證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)等算法進行對比進行比較，選用15個作業(yè)和15臺機器到500個作業(yè)和20臺機器，基準實例的維度介于225～2000之間，設施數(shù)量使用2～7個工廠來解決DJSP問題。算法求解后采用相對百分比偏差(relative percentage deviation，RPD)用以比較DSHO和其他算法的性能差異。PRD 的值計算如下：

(33)

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

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

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

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

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

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

(34)

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

表5 Friedman檢驗平均值

圖5 Friedman檢驗等級

4 結論

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

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

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