基于灰狼算法的多目標(biāo)車間調(diào)度優(yōu)化*

馮麟皓，方喜峰,2，李 俊

(1.江蘇科技大學(xué)機械工程學(xué)院，鎮(zhèn)江 212100；2.江蘇省先進(jìn)制造技術(shù)重點實驗室，淮安 223003)

0 引言

在智能制造飛速發(fā)展的今天，車間調(diào)度問題是目前制造企業(yè)面臨的一個核心問題，車間調(diào)度問題的合理解決可以有效提高制造企業(yè)的生產(chǎn)效率，為企業(yè)的敏捷制造提供方向。作業(yè)車間調(diào)度問題(JSP)[1]是生產(chǎn)調(diào)度的典型問題，在滿足車間現(xiàn)有的生產(chǎn)資源前提下，以加工約束為前提，對工序進(jìn)行排序以實現(xiàn)生產(chǎn)節(jié)拍的最小化，提升企業(yè)的生產(chǎn)和加工效率具有重要的現(xiàn)實意義。

為響應(yīng)國家提出的“碳中和”等戰(zhàn)略目標(biāo)，我國許多的制造業(yè)將能耗問題也納入到企業(yè)的核心優(yōu)化指標(biāo)，因此如何在提升車間效率的前提下，盡可能地降低能源消耗和機械負(fù)載等多個問題成為了學(xué)者研究的熱門話題[2-3]。顧九春等[4]對車間的節(jié)能問題，提出了一種節(jié)能調(diào)度模型，使用并行搜索方法對總能耗和最大完工時間進(jìn)行尋優(yōu)，有效平衡了算法全局和局部搜索能力。張朋等[5]考慮了訂單的準(zhǔn)時交付問題，同時引入了懲罰交叉聚合函數(shù)和非支配解集，使的算法獲得了良好的目標(biāo)解集。NASRUDDIN等[6]采用神經(jīng)網(wǎng)絡(luò)和多目標(biāo)遺傳算法的方式，對熱舒適和能耗這兩個相互排斥的目標(biāo)進(jìn)行優(yōu)化，算法在最大限度減少能耗的同時提高了熱舒適度。ZHANG等[7]為減小車間的能源消耗，提出了一種智能調(diào)度系統(tǒng)，通過將零散的空閑期進(jìn)行整合，對空閑期內(nèi)的機器采用關(guān)閉機器的策略，有效節(jié)省了能耗。高滔等[8]對多個目標(biāo)融合遺傳和貪婪算法思想，兩種算法對工序和機器分別尋優(yōu)，證明其算法的有效性。張麗等[9]為解決車間的多目標(biāo)優(yōu)化問題，提出了一種融合粒子群的遺傳算法，同時引入Pareto解[10-11]使解集保持多樣性。

大多數(shù)學(xué)者主要聚焦于加工時間和能耗這兩個目標(biāo)，且傳統(tǒng)的群優(yōu)化算法或神經(jīng)網(wǎng)絡(luò)求解多目標(biāo)問題時無法獲取到合適的解集，導(dǎo)致出現(xiàn)目標(biāo)函數(shù)數(shù)值跳動大、算法優(yōu)化效果較差等問題，結(jié)合國家“智能制造”和“碳中和”的戰(zhàn)略目標(biāo)，本文從車間調(diào)度中的加工時間、機械負(fù)載、車間能耗等關(guān)鍵指標(biāo)出發(fā)，提出了一種MSS-GWO算法，實現(xiàn)了減小加工時間的同時對其余關(guān)鍵指標(biāo)的優(yōu)化。

1 問題描述及模型

1.1 作業(yè)車間調(diào)度問題

作業(yè)車間的問題可描述為，一批訂單中有多個不同型號的n個工件需要加工，記為{J1,J2,…,Jn}；共計m臺機器，記為{M1,M2,…,Mm}；工件i的工序可用集合Oi表示，{Oi1,Oi2,…,Oij}；各工序在滿足加工要求的前提下可任意選取機器，在現(xiàn)實的加工車間中，由于每臺機器的使用頻率、年限等不同，每臺機器上的加工時的功率和加工時間也不盡相同，因此本文考慮以最小化最大加工時間[12]、機械負(fù)載、以及加工能耗為目標(biāo)進(jìn)行作業(yè)車間調(diào)度研究。

1.2 問題模型

(1)條件假設(shè)

①同一臺機器同一時刻只能加工一個工件；

②同一工件的同一道工序在此時只能在一臺機器上加工；

③任意工件的工序在加工開始后不能中止；

④不同工件之間不存在先后順序；

⑤同一工件的工序之間有加工先后關(guān)系，必須在前置工序完成后才能加工；

⑥在零時刻所有工件都可開始加工。

(2)數(shù)學(xué)模型構(gòu)建

MinMakespan=MaxMakespann

(1)

(2)

(3)

式(1)～式(3)為目標(biāo)函數(shù)，式(1)表示最小完工時間以最晚結(jié)束的加工機器所對應(yīng)的時間為準(zhǔn)；式(2)表示設(shè)備的負(fù)載，為其所有機器的加工時間之和；式(3)表示該批工件加工的能源消耗。

針對以上目標(biāo)函數(shù)，給出本文研究過程中的約束條件：

(4)

(3)參數(shù)定義

相關(guān)參數(shù)以含義如表1所示。

表1 相關(guān)變量及含義

2 改進(jìn)灰狼算法

2.1 灰狼算法簡介

灰狼算法是由MIRJALILI等[13]提出的一種模擬灰狼的社會等級制度和狩獵行為的一種啟發(fā)式算法，其主要是將灰狼群按照其適應(yīng)度依次分為α、β、δ、ω四類，分別由α、β、δ在狩獵過程中引導(dǎo)ω狼進(jìn)行獵物的搜尋，從而獲得最優(yōu)解。

D=CXp(t)-X

(5)

X(t+1)=Xp(t)-AD

(6)

式中，

A=2ar1-a

(7)

C=2r2

(8)

式中，t為迭代次數(shù)；X(t)為當(dāng)前灰狼的位置；Xp為獵物的位置；A、C分別為協(xié)同系數(shù)；r1、r2為介于[0,1]的隨機數(shù)；a的數(shù)值隨著迭代次數(shù)的增加線性遞減，最終變?yōu)?。

在狩獵過程中，其主要依靠各具有領(lǐng)導(dǎo)能力的α、β、δ狼提供指引，ω狼向著獵物存在的方向進(jìn)行搜尋，進(jìn)而更新種群的位置，其數(shù)學(xué)模型如下：

(9)

(10)

(11)

式中，Xα、Xβ、Xδ分別為α、β、δ狼當(dāng)前的位置；Dα、Dβ、Dδ分別為其余個體距離α、β、δ狼的距離；X為當(dāng)前灰狼的位置。

2.2 改進(jìn)策略

2.2.1 編碼和解碼

本文中的柔性作業(yè)車間數(shù)據(jù)由工序序列、加工機器序列、以及加工時間序列構(gòu)成。首先，對訂單中各序列進(jìn)行提取，采用基于工序的ROV的升序編碼方式，按照加工工序生成工序編碼，其次產(chǎn)生[0,1]的隨機數(shù)，與加工工序編碼數(shù)量保持一致，依照隨機數(shù)的大小進(jìn)行ROV升序排列，得到了初始化的加工工序編碼，如圖1所示。

圖1 工序的編碼方式

工序編碼中重復(fù)出現(xiàn)的數(shù)字表示該工件的第n道工序，通過生成的加工機器矩陣和時間矩陣能夠獲取該到該道工序的可選加工設(shè)備和在該設(shè)備上的加工時間。如表2所示，表中第一列中的工序編碼2第一次出現(xiàn)，表示第2個工件的第1道工序，其可選的加工機器分別是機器3和5，所對應(yīng)的加工時間分別是5和4。

表2 工序的解碼方式

2.2.2 混合交叉的搜索策略

為解決傳統(tǒng)灰狼算法存在的無法快速收斂，算法容易陷入局部最優(yōu)解的問題。提出一種混合交叉的搜索策略(mixed-cross search strategy，MSS)，引入遺傳算法中的混合交叉原理，由此增加種群的多樣性。該策略可以使得整個空間得到充分的搜索，同時算法在后期能夠快速收斂，避免陷入局部最優(yōu)解的情況。

MSS策略主要是針對3個階段的改進(jìn)，初始化種群階段、獵物搜尋階段、以及狼群更新階段。

初始化種群：對于給定的搜索區(qū)域，對灰狼種群采用均勻分布的初始化方式：

(12)

式中，N為灰狼種群的初始種群個數(shù)；Xi(t)={x1,x2,x3…,xi}為迭代t次后灰狼i的位置。同時，當(dāng)某一道工序?qū)?yīng)多臺加工機器時，本文引入一個選擇系數(shù)Q，當(dāng)隨機數(shù)大于Q時，對該道工序的加工機器進(jìn)行隨機選擇；否則選用當(dāng)前工序中加工時間最大的加工機器。

獵物搜尋階段：在原始GWO算法的獵物搜尋過程中，下一次迭代后的具體位置由α、β、δ狼的位置Xα、Xβ、Xδ決定，但僅服從α、β、δ三只領(lǐng)導(dǎo)狼的引導(dǎo)進(jìn)行搜索，當(dāng)領(lǐng)導(dǎo)狼陷入局部最優(yōu)解時，狼群則會陷入局部最優(yōu)解。在MSS策略中，引入遺傳算法中的混合交叉原理，有效的提升了算法的搜索能力，灰狼個體搜索范圍的表達(dá)式如下：

(13)

式中，Xi(t)為當(dāng)前灰狼的位置坐標(biāo)；Xi-GWO(t+1)為采用原始GWO算法計算出的候選灰狼的坐標(biāo)。以式(13)計算出的值為半徑，對鄰域半徑的狼群進(jìn)行混合交叉處理，重新計算鄰域中狼群的適應(yīng)度，適應(yīng)度最高的作為候選位置，其坐標(biāo)表示為Xi-MSS。

狼群更新階段：通過對比傳統(tǒng)GWO算法生成的候選灰狼坐標(biāo)Xi-GWO(t+1)以及采用MSS策略生成的灰狼坐標(biāo)Xi-ISS(t+1)在種群中的適應(yīng)度，將其作為最終的候選灰狼，表達(dá)式為：

(14)

算法每進(jìn)行一次迭代，都會產(chǎn)生傳統(tǒng)GWO以及采取MSS策略篩選出的候選灰狼，通過選出適應(yīng)度高的個體，能夠更好的幫助種群找到更合適的候選灰狼，以增強算法的效果。

2.2.3 非線性參數(shù)策略

在GWO算法中，當(dāng)|A|>1，種群進(jìn)行全局搜索；當(dāng)|A|<1，種群進(jìn)行局部搜索。由此可見，參數(shù)a的設(shè)置直接影響了算法搜索的性能。傳統(tǒng)GWO算法中參數(shù)a隨迭代過程由2線性減小至0，無法適應(yīng)復(fù)雜的搜索過程，為此本文提出了一種非線性參數(shù)策略，該策略可以更好的對全局搜索和局部搜索進(jìn)行調(diào)整，有效保持了種群的多樣性。

為了能夠找到最佳的函數(shù)，如圖2所示，本文對非線性函數(shù)以最小化最大加工時間為目標(biāo)，種群大小設(shè)置為100，選擇系數(shù)Q為0.6，進(jìn)行50次迭代，結(jié)果如圖3所示。

圖2 參數(shù)a變換過程 圖3 非線性函數(shù)對比圖

通過對比可知，在初期設(shè)置參數(shù)a時，為了種群能在領(lǐng)導(dǎo)狼的引導(dǎo)下盡可能進(jìn)行全局搜索，a取得盡可能大一些，而在算法搜索的中后期，為了使算法快速收斂，盡可能的使a的下降速度更快，最終參數(shù)a的函數(shù)可表示為：a=2-2x3。

2.2.4 動態(tài)權(quán)重搜索策略

在傳統(tǒng)的GWO算法設(shè)置中，候選灰狼的位置僅由α狼影響，該方法會使得在α狼陷入局部最優(yōu)解時降低種群的尋優(yōu)能力，使算法在搜索過程中收斂緩慢，為了保證前期狼群的多樣性，本文提出一種動態(tài)權(quán)重搜索策略，在前期搜索中，使得狼群受α、β、δ狼共同影響，增強種群多樣性和搜索能力，防止陷入局部最優(yōu)；在搜索后期，提高α狼的權(quán)重，降低β、δ狼的權(quán)重，使得算法能夠快速收斂，其表達(dá)式可表示為：

X(t+1)=q1X1+q2X2+q3X3

(15)

式中，參數(shù)之間的約束關(guān)系應(yīng)滿足：

q1≥q2≥q3

(16)

q1+q2+q3=1

(17)

因此對q1、q2、q3分別進(jìn)行了非線性函數(shù)的設(shè)計：

q1=cosμ

(18)

(19)

q3=1-q1-q2

(20)

為進(jìn)一步對函數(shù)進(jìn)行約束，本文引入角度μ和τ，當(dāng)Gen從0到Max_Gen時，根據(jù)余弦函數(shù)和正弦函數(shù)的特性，設(shè)計了角度μ和τ的函數(shù)以保證本文中參數(shù)的變化范圍。

(21)

(22)

綜上所述，給出灰狼中α、β、δ狼權(quán)重q1、q2、q3在迭代過程中的變化過程，如圖4所示。

圖4 權(quán)重系數(shù)的變化過程

2.3 pareto排序

對于多目標(biāo)優(yōu)化，常見的方法是進(jìn)行加權(quán)處理和pareto解的形式，在以往大量的學(xué)者研究中，采用結(jié)合自身問題進(jìn)行權(quán)重賦值，具有主觀性，權(quán)重的賦值不同會對最終結(jié)果產(chǎn)生巨大的差異，影響最優(yōu)解的準(zhǔn)確獲取。

因此本文采用pareto解集對其最大加工時間、加工及設(shè)備的負(fù)載以及能源消耗進(jìn)行優(yōu)化，通過外部存儲保存每次迭代后的解集，通過計算非支配解集以獲得最優(yōu)的解。

2.4 算法流程

MSS-GWO算法的主要流程如圖5所示。主要步驟為：

圖5 算法流程圖

步驟1：設(shè)置種群規(guī)模N，選擇系數(shù)Q，迭代次數(shù)Max_Gen；

步驟2：利用隨機系數(shù)Q完成種群的初始化；

步驟3：判斷是否達(dá)到迭代次數(shù)，是的話跳至步驟8，否則計算初始化種群的適應(yīng)度，按照其適應(yīng)度進(jìn)行排序，記錄Pareto最優(yōu)解，分別將最好的3個個體依次賦值給狼α、β、δ；

步驟4：更新當(dāng)前種群的權(quán)重系數(shù)等參數(shù)；

步驟5：判斷是否達(dá)到其種群規(guī)模，是則利用灰狼算法求出其候選狼，否則調(diào)制步驟3；

步驟6：根據(jù)候選狼計算出其鄰域，同時對鄰域內(nèi)的個體進(jìn)行混合交叉，篩選出新的候選狼；

步驟7：對比灰狼算法求出的候選狼與混合交叉后的候選狼，選出適應(yīng)度高后候選狼更新種群，替換外部解集；

步驟8：算法結(jié)束，獲得最終解集。

3 實驗及結(jié)果分析

為了測試本文所提出的MSS策略的有效性，采用Python驗證本文提出的算法，計算環(huán)境為CPU：5600X，內(nèi)存16 G，實驗驗證主要包括仿真數(shù)據(jù)測試對比以及具體案例Pareto解集分析兩部分組成。

3.1 數(shù)據(jù)對比

仿真測試數(shù)據(jù)來源為MK01-MK07算例[14-15]，其中包含了不同總數(shù)、不同加工機器總數(shù)、不同工序數(shù)的作業(yè)車間測試數(shù)據(jù)，同時，每臺機器由于使用年限、類型不同等原因，分別對應(yīng)了不同的加工功率和空載功率，如表3所示。由此使用算例對比本文提出的MSS-GWO算法、傳統(tǒng)的GWO算法、以及文獻(xiàn)[9]中所使用的FNSGA算法，驗證本文提出算法的可行性。

表3 機器型號機器功率表

本文中算法的迭代次數(shù)為100，初始化種群數(shù)為200，隨機系數(shù)Q設(shè)置為0.6。對比結(jié)果如表4所示。

表4 算法對比表

表中(44.0,163.0,348.2)分別表示MK01算例在MSS-GWO算法得到的最小加工時間為44，機械負(fù)載為163，加工能耗為348.2，通過對其他幾組算例進(jìn)行算法對比可知，本文所設(shè)計的MSS-GWO算法在最小化最大加工時間、機械負(fù)載、以及加工能耗相較于文獻(xiàn)中采用的FNSGA有較大提升，同時相較于雙目標(biāo)優(yōu)化目標(biāo)，本文進(jìn)行了3個目標(biāo)的優(yōu)化；對比傳統(tǒng)GWO算法，對于實際車間加工中的加工時間這一關(guān)鍵數(shù)據(jù)，算法保持了較優(yōu)解，在實際的加工生產(chǎn)中可有效提高車間的效率。

3.2 Pareto解集對比

在Pareto解集方面，以MK02算例為例，對文獻(xiàn)中的Pareto解集以及本文采用的MSS-GWO策略進(jìn)行對比，繪制前沿對比圖；同時對比GWO算法繪制Pareto解集，如圖6和圖7所示，從圖中可以看出在相同的算例下，本文所設(shè)計的策略整體上保持了較優(yōu)的性能，首先是獲取的解集數(shù)量上更多，保持了多樣性；其次在算法搜尋的最優(yōu)解上，整體由于文獻(xiàn)的解集；最后是在對于實際加工生產(chǎn)過程中的最小化最大加工時間均保持了較大優(yōu)勢，由此本文所設(shè)計的算法的搜索性能更好。

圖6 兩目標(biāo)對比圖 圖7 多目標(biāo)Pareto解集對比圖

最后給出MK02算例的調(diào)度甘特圖，如圖8所示。

圖8 MK02算例調(diào)度方案

4 結(jié)束語

為解決車間柔性調(diào)度問題，本文從考慮到車間最小化最大加工時間、機械負(fù)載、以及加工能耗等關(guān)鍵指標(biāo)出發(fā)，構(gòu)建優(yōu)化目標(biāo)的數(shù)學(xué)模型。同時提出了一種混合交叉原理的MSS-GWO調(diào)度策略，同時為了使算法能夠獲得更好的Pareto解集，進(jìn)行了非線性函數(shù)的設(shè)計，最終對車間的常用的MK系列數(shù)據(jù)集進(jìn)行了算法驗證，實驗表明本文提出的混合交叉原理的MSS-GWO策略能夠較好的解決車間的多目標(biāo)優(yōu)化問題。

后續(xù)研究將繼續(xù)緊扣車間調(diào)度問題，吸收其他算法的優(yōu)點，進(jìn)行車間的動態(tài)調(diào)度研究，使得車間調(diào)度問題能夠得到更好的解決。