基于混合麻雀搜索算法的作業(yè)車間調(diào)度研究

李保偉，喻明讓，陳 云

(1.中北大學(xué)航空宇航學(xué)院，山西 太原 030051) (2.北方自動控制技術(shù)研究院，山西 太原 030006)

作業(yè)車間調(diào)度問題(job-shop scheduling problem，JSP)是公認的最困難的組合優(yōu)化問題，是典型的NP-hard問題。調(diào)度問題的難點在于，在多項式時間里，無法找到一個確定的方法來求出該問題的最優(yōu)解。為了使車間內(nèi)的生產(chǎn)資源得到充分利用，提高能源利用率，高效的調(diào)度方案就顯得尤為重要。其中調(diào)度優(yōu)化算法是調(diào)度問題的關(guān)鍵點，也是調(diào)度問題的研究熱點。

群體智能優(yōu)化算法是調(diào)度優(yōu)化算法的研究熱點之一。其主要通過模仿群體的一些行為，在搜索空間內(nèi)進行全面搜索。因其并行性、穩(wěn)定性較強，在解決復(fù)雜的優(yōu)化問題時表現(xiàn)出較強的搜索能力[1]。因此，群體智能優(yōu)化算法被廣泛應(yīng)用到車間調(diào)度問題研究中。針對最小化完工時間的目標，李寶帥等[2]改進了鯨魚優(yōu)化算法，結(jié)合正余弦策略，采用兩段式編碼使鯨魚算法可用于解決離散性的JSP問題。徐雨等[3]提出用混合免疫遺傳算法求解JSP問題，解決了遺傳算法容易陷入局部最優(yōu)的缺點。陽光燦等[4]提出改進的遺傳算法(genetic algorithm，GA)，采用基于操作的編碼方式求解JSP問題。趙小惠等[5]采用均勻分布螞蟻初始位置、多種方式結(jié)合進行機器選擇的改進蟻群算法求解JSP問題。Ibrahim等[6]提出一種高效的人工藻類與差分進化混合算法來求解JSP問題。針對具有運輸時間的JSP問題，鮑薔等[7]提出一種改進的混合蛙跳算法。近年來，很多群智能算法及其混合算法被用到車間調(diào)度問題中，Xue等[8]在2020年提出一種新型群智能算法——麻雀搜索算法(sparrow search algorithm，SSA)，此算法模擬了麻雀覓食、反捕食等行為。目前，SSA及其改進算法已被用到很多研究中。例如，張偉康等[9]對SSA的種群初始化及個體位置更新策略進行改進，在種群初始化方面采用Circle映射策略，在發(fā)現(xiàn)者位置更新方面采用蝴蝶優(yōu)化算法中蝴蝶的飛行方式，從而提高了SSA的全局搜索能力。張曉萌等[10]結(jié)合正余弦搜索、多樣性變異處理等策略對SSA進行改進，提高了算法的收斂速度和跳出局部最優(yōu)的能力。劉麗娜等[11]采用量子計算、正余弦搜索等方法對個體位置更新方式進行改進，使算法在后期可以跳出局部最優(yōu)，在算法迭代過程中加入了高斯擾動、多鄰域搜索等策略，讓SSA表現(xiàn)出更優(yōu)越的性能。王建新等[12]采用離散型麻雀搜索算法，對食品安全檢查中的抽檢路徑進行優(yōu)化求解。此外，SSA還被應(yīng)用到圖像分割、無人機航跡優(yōu)化和故障診斷等領(lǐng)域。

基于以上研究成果，本文將SSA與GA相結(jié)合，并對部分過程進行改進，求解以最小化最大完工時間為目標的作業(yè)車間調(diào)度問題。

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

1.1 問題描述

作業(yè)車間調(diào)度問題就是：給定一組作業(yè)，其中包含n個工件，要求在m個機器上加工完成，為每道工序分配合適的加工機器以此達到一定的優(yōu)化目標。做以下假設(shè)：1)各個工序在各個機器上的加工時間給定；2)一臺機器同一時間僅能加工一道工序；3)一個作業(yè)在同一時間只能在一臺機器上加工，機器開始加工后不能被中斷；4)每臺機器在0時刻都可工作且各機器間是獨立的；5)每道工序在對應(yīng)機器上的加工時間是不可變的；6)一道工序的加工時間是連續(xù)的，不會出現(xiàn)缺料等情況。

1.2 數(shù)學(xué)模型

本文所優(yōu)化的JSP目標是最小化最大完工時間，采用下面的數(shù)學(xué)模型求解[13]：

f=min{makespan=min max{cik}}

(1)

cik-pik+M(1-aihk)≥cihi=1,2,…,n;h,k=1,2,…,m

(2)

cjk-pik+M(1-xijk)≥pjki,j=1,2,…,n;k=1,2,…,m

(3)

式中：makespan為最大完工時間；cik為工件i在機器k上的完工時間；cih為工件i在機器h上的完工時間；pik為工件i在機器k上加工時間；aihk為指示系數(shù)，當機器h先于機器k加工工件i時aihk=1，否則aihk=0；M為充分大正數(shù)；xijk為指示變量，若工件i先于工件j在機器k上加工則xijk=1，否則xijk=0；pjk為工件j在機器k上的加工時間；n為工件總數(shù)；m為機器總數(shù)。式(1)為目標函數(shù)，式(2)為工藝約束，式(3)為機器約束。

2 改進混合麻雀搜索/遺傳算法

2.1 算法介紹

1)SSA。

SSA模仿麻雀的覓食、反捕食行為進行最優(yōu)解的搜尋[1]，具有搜索精度高、魯棒性強、收斂速度快等優(yōu)點。

麻雀種群通過發(fā)現(xiàn)者搜尋食物并向參與者發(fā)出信息，參與者追隨發(fā)現(xiàn)者，偵察者進行反捕食，將危險信息傳遞給其他個體的行為來進行覓食?；谶@一原理，SSA通過發(fā)現(xiàn)者與追隨者來尋找全局最優(yōu)解，偵察者則用來防止算法過早收斂，而這些過程在算法中都是通過種群中個體位置更新來實現(xiàn)的。在算法求解過程中，發(fā)現(xiàn)者的個體位置更新公式為[1]：

(4)

(5)

(6)

2)遺傳算法。

遺傳算法模擬的是大自然中生物的進化規(guī)律。遺傳算法具有擴展性強、求解流程簡單、易與其他算法結(jié)合等優(yōu)點。但遺傳算法的搜索速度慢、對初始種群依賴性強，且易陷入局部最優(yōu)，故多與其他算法結(jié)合使用。

2.2 編碼及轉(zhuǎn)換機制

1)基于工序編碼。

本文采用基于工序的編碼，編碼由工件號組成，編碼的總長度為工序數(shù)量，工件號i第j次出現(xiàn)代表第i個工件的第j道工序，即Oij。如圖1所示的工序編碼所代表的工序序列為O31,O21,O11,O32,O33,O12,O22,O23,O13。

圖1 工序編碼示例

2)轉(zhuǎn)換機制。

JSP問題是離散性問題，SSA是在連續(xù)空間內(nèi)搜索最優(yōu)解，因此需要經(jīng)過編碼轉(zhuǎn)換來將SSA應(yīng)用于JSP問題，具體方法如下：

①麻雀個體位置編碼，X=[x1,x2,x3,…,xτ]，其中τ對應(yīng)工件總工序數(shù)，一只麻雀代表一條工藝路線，xi為搜索空間內(nèi)的實數(shù)；

②將編碼后的麻雀個體位置按實數(shù)xi的值從大到小排列，通過降序函數(shù)產(chǎn)生排序后的索引數(shù)組A；

③將數(shù)組A中的索引除以工件最大工序數(shù)，利用正無窮取整函數(shù)對結(jié)果進行取整，得到各麻雀所代表的工序編碼。

2.3 改進的混合麻雀搜索/遺傳算法

SSA求解問題的步驟如圖2所示。

圖2 麻雀搜索算法流程

在算法開始階段，選取種群中適應(yīng)度較高的麻雀作為發(fā)現(xiàn)者，參與者會向發(fā)現(xiàn)者學(xué)習(xí)。由于這一學(xué)習(xí)行為，使得種群趨于同一個地方，導(dǎo)致算法陷入局部最優(yōu)，而偵察者的反捕食行為就是為了防止搜索路徑陷入局部最優(yōu)而導(dǎo)致過早收斂。偵察者的數(shù)量一般為種群的10%～20%，其數(shù)量過大時，會影響算法的收斂速度；數(shù)量過少時，會陷入局部最優(yōu)。

遺傳算法主要通過交叉算子來進行尋優(yōu)，故筆者將交叉操作加入到發(fā)現(xiàn)者位置更新之后，用于增強SSA的搜索能力。交叉操作主要有單點交叉、多點交叉與均勻交叉等，本文采用兩點交叉的方式來提高SSA的收斂速度。由于GA變異算子的引入可以增強本文所提算法(ISSA/GA)跳出局部最優(yōu)的能力，故選擇逆序變異的方法將其加入到偵察者位置更新后，結(jié)合偵察者數(shù)量遞減策略，提高ISSA/GA跳出局部最優(yōu)的能力，避免算法過早收斂。

偵察者數(shù)量遞減策略：在迭代開始時，偵察者設(shè)置為較高的比例γ，偵察者數(shù)量較多時可以避免種群直接向某個適應(yīng)度較高的個體收斂，從而錯過其他適應(yīng)度較高的個體，導(dǎo)致種群過早收斂。隨著迭代次數(shù)增加，逐漸減少偵察者數(shù)量，比例降為λ，以保證迭代后期種群的收斂速度。偵察者數(shù)量的計算公式為：

(7)

式中：Ps為偵察者的數(shù)量；Pt為種群個體總數(shù)量；γ,λ為偵察者的數(shù)量占比，其中0<λ<γ<1。

混合算法求解JSP的流程如下：

1)設(shè)置相關(guān)參數(shù)，如工件、機器數(shù)目等，算法迭代次數(shù)、種群數(shù)目、交叉概率、變異概率、發(fā)現(xiàn)者與參與者數(shù)量等，γ和λ的值等。

2)初始化種群，計算個體適應(yīng)度值，找出當前種群最優(yōu)和最差個體位置。

3)開始算法迭代，判斷是否達到終止條件，若滿足條件則輸出最優(yōu)結(jié)果，否則重復(fù)步驟4)～6)至滿足條件為止。

4)根據(jù)發(fā)現(xiàn)者位置更新公式來更新發(fā)現(xiàn)者位置，加入交叉操作，搜索最優(yōu)解。

5)更新參與者位置。

6)偵察者根據(jù)更新公式更新位置，并加入變異操作，更新全局最優(yōu)個體。

3 實驗與結(jié)果

為了驗證本文所提算法(ISSA/GA)的有效性，通過FT系列算例對不同算法進行測試，比較各算法結(jié)果，判斷算法的優(yōu)缺點及性能。本文選取FT06、FT10、FT20為例，采用遺傳算法以及ISSA/GA等對算例進行30次求解，并與參考文獻[14]中算法的求解結(jié)果進行比較。然后對文獻[14]中兩個實例進行計算，驗證ISSA/GA求解JSP問題的可行性。

實驗設(shè)備的操作系統(tǒng)為64位Windows10，處理器為Intel(R)Core(TM)i5-8300H CPU@2.30 GHz，內(nèi)存為8.00 GB。編程環(huán)境為MATLAB R2020a。

3.1 算例計算結(jié)果分析

種群規(guī)模為100，最大迭代次數(shù)為300，以最小化最大完工時間為目標，對3個算例各獨立求解30次，所得結(jié)果見表1、表2。表中PSO為粒子群優(yōu)化算法。

表1 算法測試結(jié)果對比Ⅰ 單位：s

表2 算法測試結(jié)果對比Ⅱ 單位：s

從表1和表2的求解結(jié)果可以看出，在FT06算例中，各算法所得最小值均為55，只有SSA所求平均值為58，可知該算法穩(wěn)定性稍差。在規(guī)模較大的FT10 10×10和FT20 20×5算例中，SSA求得的最小值最差，ISSA/GA所得最小值最優(yōu)，可知ISSA/GA有較強的搜索能力和穩(wěn)定性，即在計算小規(guī)模問題時，4種算法均有較強的尋優(yōu)能力和穩(wěn)定性；在問題規(guī)模增大后，在保持較強穩(wěn)定性的同時，ISSA/GA的尋優(yōu)能力稍強于PSO、GA及SSA。

由圖3可得，在對FT06問題尋優(yōu)時，ISSA/GA收斂速度最快，最優(yōu)值與PSO、GA相同。由圖4可得，在FT10算例中，ISSA/GA迭代初期就有較快的收斂速度，且最終解最優(yōu)。綜上可得，ISSA/GA的收斂速度快、尋優(yōu)能力強、穩(wěn)定性強，是一種可有效解決JSP問題的算法。

圖3 FT06問題尋優(yōu)結(jié)果對比曲線

3.2 實例應(yīng)用分析

選擇參考文獻[14]中兩個不同規(guī)模的實例，使用ISSA/GA對其進行求解，以驗證所用算法的有效性。分別選取6×6和10×10的算例，運用ISSA/GA進行求解，算法參數(shù)設(shè)置與文獻一致，最大迭代次數(shù)為300，種群規(guī)模為50，算法各獨立運行30次，得到的結(jié)果見表3、表4。

圖4 FT10問題尋優(yōu)結(jié)果對比曲線

表3 6×6作業(yè)車間調(diào)度問題尋優(yōu)結(jié)果對比 單位：s

表4 10×10作業(yè)車間調(diào)度問題尋優(yōu)結(jié)果對比 單位：s

在求解6×6問題時，混合算法取得的最小完工時間是54 s，相較于SSA、LSO、改進LSO所求結(jié)果更優(yōu)。在10×10的實例中，ISSA/GA求得的最小值為121，求解結(jié)果明顯優(yōu)于其他3種算法。故而可知本文所用方法在求解JSP時是有效可行的。圖5和圖6是ISSA/GA所得的最優(yōu)結(jié)果的調(diào)度方案甘特圖。

圖5 6×6實例調(diào)度結(jié)果甘特圖

4 結(jié)束語

高效的調(diào)度優(yōu)化算法是解決JSP問題的關(guān)鍵。

圖6 10×10實例調(diào)度結(jié)果甘特圖

本文將麻雀搜索算法與遺傳算法相結(jié)合，并對其位置編碼進行轉(zhuǎn)換，用于解決作業(yè)車間調(diào)度問題。針對麻雀搜索算法容易出現(xiàn)早熟的問題，采用偵察者數(shù)量遞減策略并加入變異操作，提高算法性能。通過對FT經(jīng)典算例的計算結(jié)果對比與分析，驗證了所提混合麻雀搜索算法在求解作業(yè)車間調(diào)度問題時的可行性，且具有一定優(yōu)越性，為JSP的研究提供了一種新的混合算法。

本文所提的混合算法，在單目標JSP問題上可以生成優(yōu)異的調(diào)度方案。而在實際生產(chǎn)中，往往需要考慮多個優(yōu)化目標，在以后的研究中，可將混合算法用于多目標JSP或IPPS(integrated process planning and scheduling,工藝規(guī)劃與調(diào)度集成)求解。同時，可以采用其他的優(yōu)化策略來改進SSA，或者將麻雀搜索算法與其他算法相結(jié)合來生成更加高效的混合算法。