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

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

0 引言

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

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

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

1 問題描述及模型

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

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

1.2 問題模型

(1)條件假設(shè)

①同一臺(tái)機(jī)器同一時(shí)刻只能加工一個(gè)工件；

②同一工件的同一道工序在此時(shí)只能在一臺(tái)機(jī)器上加工；

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

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

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

⑥在零時(shí)刻所有工件都可開始加工。

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

MinMakespan=MaxMakespann

(1)

(2)

(3)

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

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

(4)

(3)參數(shù)定義

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

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

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

2.1 灰狼算法簡(jiǎn)介

灰狼算法是由MIRJALILI等[13]提出的一種模擬灰狼的社會(huì)等級(jí)制度和狩獵行為的一種啟發(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]的隨機(jī)數(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δ分別為其余個(gè)體距離α、β、δ狼的距離；X為當(dāng)前灰狼的位置。

2.2 改進(jìn)策略

2.2.1 編碼和解碼

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

圖1 工序的編碼方式

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

表2 工序的解碼方式

2.2.2 混合交叉的搜索策略

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

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

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

(12)

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

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

(13)

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

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

(14)

算法每進(jìn)行一次迭代，都會(huì)產(chǎn)生傳統(tǒng)GWO以及采取MSS策略篩選出的候選灰狼，通過選出適應(yīng)度高的個(gè)體，能夠更好的幫助種群找到更合適的候選灰狼，以增強(qiá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ù)策略，該策略可以更好的對(duì)全局搜索和局部搜索進(jìn)行調(diào)整，有效保持了種群的多樣性。

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

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

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

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

在傳統(tǒng)的GWO算法設(shè)置中，候選灰狼的位置僅由α狼影響，該方法會(huì)使得在α狼陷入局部最優(yōu)解時(shí)降低種群的尋優(yōu)能力，使算法在搜索過程中收斂緩慢，為了保證前期狼群的多樣性，本文提出一種動(dòng)態(tài)權(quán)重搜索策略，在前期搜索中，使得狼群受α、β、δ狼共同影響，增強(qiáng)種群多樣性和搜索能力，防止陷入局部最優(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)

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

q1=cosμ

(18)

(19)

q3=1-q1-q2

(20)

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

(21)

(22)

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

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

2.3 pareto排序

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

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

2.4 算法流程

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

圖5 算法流程圖

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)及結(jié)果分析

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

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

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

表3 機(jī)器型號(hào)機(jī)器功率表

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

表4 算法對(duì)比表

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

3.2 Pareto解集對(duì)比

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

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

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

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

4 結(jié)束語

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

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