混合候鳥優(yōu)化算法求解柔性作業(yè)車間調(diào)度問題

摘 要：針對最大完工時間最小化的柔性作業(yè)車間調(diào)度問題，提出一種混合候鳥優(yōu)化算法。結(jié)合輪盤賭策略生成初始種群，提高初始種群的質(zhì)量。在傳統(tǒng)候鳥優(yōu)化算法的基礎(chǔ)上對鳥類進(jìn)化階段進(jìn)行改進(jìn)，將共享鄰域解替換為共享基因片段，避免算法陷入局部最優(yōu)，設(shè)計了一種基于路徑的重連的鄰域結(jié)構(gòu)來引導(dǎo)跟飛鳥進(jìn)化。對進(jìn)化后的個體采用隨機(jī)爬山算法進(jìn)行局部搜索，對關(guān)鍵路徑上的關(guān)鍵工序的加工機(jī)器進(jìn)行替換，擴(kuò)大搜索范圍，從而獲得最優(yōu)解。設(shè)置正交試驗確定算法的重要參數(shù)組合，通過基準(zhǔn)算例的仿真試驗，使用相對百分比偏差與弗里德曼非參數(shù)配對檢驗來比較所提算法的有效性以及可行性。試驗結(jié)果表明，在10個算例中，所提算法在多個算例上均能獲得最優(yōu)值，平均RPD值最小，且與其他對比算法具有顯著性差異。

關(guān)鍵詞：柔性作業(yè)車間調(diào)度；最大完工時間；候鳥優(yōu)化算法；隨機(jī)重啟爬山算法

中圖分類號：TP 165" " 文獻(xiàn)標(biāo)志碼：A

作業(yè)車間調(diào)度優(yōu)化一直是生產(chǎn)管理與組合優(yōu)化等領(lǐng)域的熱門研究話題。柔性作業(yè)車間調(diào)度問題（Flexible Job Shop Scheduling Problem， FJSP）是JSP的延伸和擴(kuò)展，是一類復(fù)雜的NP-hard問題[1]。

計算機(jī)技術(shù)以及仿真技術(shù)的發(fā)展為FJSP問題的研究開辟了新的思路。智能優(yōu)化算法在調(diào)度問題上得到了廣泛應(yīng)用。其中，候鳥優(yōu)化算法[2]由于參數(shù)少、局部搜索能力強(qiáng)等優(yōu)點，常被用于處理車間調(diào)度問題。WEI L等[3]提出了一種基于博弈論的動態(tài)多目標(biāo)候鳥優(yōu)化算法，將博弈論引入算法中。ZHANG B等[4]提出一種改進(jìn)的離散遷鳥優(yōu)化（IDMBO）算法，以解決無等待流水線車間調(diào)度問題（NWFSSP）。

隨機(jī)重啟爬山算法（Randomly restart the hill climbing algorithm）可以在給定步驟數(shù)后從比原始跨度差的解決方案重新開始搜索，以逃避局部最小值。結(jié)合上述研究，將隨機(jī)重啟爬山算法與候鳥優(yōu)化算法進(jìn)行結(jié)合，提出一種混合候鳥優(yōu)化算法，以求解柔性作業(yè)車間調(diào)度問題。在傳統(tǒng)MBO的基礎(chǔ)上，對算法進(jìn)行改進(jìn)，引入隨機(jī)重啟爬山算法對進(jìn)化后的個體進(jìn)行局部搜索，擴(kuò)大搜索范圍。對標(biāo)準(zhǔn)測試案例進(jìn)行仿真試驗，成功證實了本文所提算法的效率和實用性。

1 問題描述與模型的建立

1.1 問題描述

FJSP可以這樣描述：n個工件在m臺不同機(jī)器上加工，每個工件可能需要經(jīng)過一道或多道工序才能完成。因為每臺機(jī)器的技術(shù)參數(shù)和型號都各不相同，所以同一個工件在不同機(jī)器上的加工時間也會有所不同。

1.2 模型建立

本文以最大完工時間最小化為優(yōu)化指標(biāo)，建立柔性作業(yè)車間調(diào)度模型。最大完工時間表示工件的最后一道工序完成加工所需的總時間。

FJSP的優(yōu)化目標(biāo)函數(shù)如公式（1）所示。

（1）

式中：j為工件序號；n為工件數(shù)目；Cj為第j個工件的完工時間。

2 混合算法設(shè)計

2.1 輪盤賭初始化

初始解的優(yōu)劣對算法的收斂速度和求解質(zhì)量有關(guān)鍵的影響。為了保證初始種群的質(zhì)量以及多樣性，通過更少的迭代次數(shù)得到問題的最優(yōu)解，針對本文的優(yōu)化目標(biāo)，采用隨機(jī)初始化的方式生成工序序列，針對機(jī)器分配采用考慮機(jī)器加工時間的輪盤賭初始化策略。

2.2 雙層編碼與最優(yōu)插入解碼

FJSP的編解碼針對工序排序和機(jī)器分配這2個子問題展開，采用融合工序與設(shè)備的并行雙鏈?zhǔn)骄幋a。這種編碼方法能確保染色體編碼含有充分的基因信息，避免發(fā)生死鎖。

解碼是將解空間轉(zhuǎn)化為問題空間。本文采用一種最優(yōu)插入法[5]對后續(xù)滿足條件的工序執(zhí)行“優(yōu)先處理”操作。在對應(yīng)機(jī)器上尋找滿足加工的加工間隙，將工序插入與工序的加工時間接近的間隙中。這種策略為后續(xù)工序的插入提供了更多的選擇，從而有機(jī)會得到更優(yōu)解。

2.3 鄰域結(jié)構(gòu)的設(shè)計

MBO算法是一種依賴鄰域搜索的元啟發(fā)式方法，單一的鄰域結(jié)構(gòu)容易使算法陷入局部最優(yōu)，不利于種群的多樣性。由于領(lǐng)飛鳥與跟飛鳥之間的質(zhì)量存在顯著差異，因此，對領(lǐng)飛鳥和跟飛鳥執(zhí)行不同的鄰域結(jié)構(gòu)。領(lǐng)飛鳥的鄰域解通過隨機(jī)從基于工序編碼的互換變異和基于工序編碼的前插變異中選擇一種來生成，以保證種群的多樣性

針對跟飛鳥設(shè)計一種基于路徑重鏈接的鄰域結(jié)構(gòu)。通過連接領(lǐng)飛鳥與跟飛鳥之間的搜索空間中的假設(shè)路徑來探索鄰域解決方案，融合初始解和引導(dǎo)解之間的一些特征來找到更好的解。如圖1所示，將xl跟飛鳥作為初始解，xf領(lǐng)飛鳥為引導(dǎo)解，逐漸檢查跟飛鳥與領(lǐng)飛鳥之間的對應(yīng)元素，逐漸對不同的元素進(jìn)行替換，跟飛鳥慢慢向領(lǐng)飛鳥靠攏，在此過程中產(chǎn)生規(guī)定數(shù)量的鄰域解xf1、xf2。

2.5 共享基因片段

在跟飛鳥的進(jìn)化階段，鳥類通過其共享機(jī)制與其跟隨鳥共享一些未使用的鄰域解，如圖2所示。如果后一只鳥的解決方案被前一只鳥的共享鄰域解替換，那么這只鳥包括的全部信息將會完全被丟棄。這種機(jī)制使鳥群朝一個方向進(jìn)化，導(dǎo)致種群過早收斂。

為了保留個體的優(yōu)秀基因片段，提出一種改進(jìn)的共享機(jī)制。如圖3所示，用共享基因片段來代替共享鄰域解，其中每個個體的進(jìn)化解集中的非當(dāng)前個體解是通過當(dāng)前個體的鄰域解與上一個相鄰個體的鄰域解進(jìn)行交叉產(chǎn)生的，交叉后產(chǎn)生的個體即包括上一個個體的基因片段，又包括當(dāng)前個體的基因片段，這樣能夠避免由個體被替換而導(dǎo)致優(yōu)秀基因喪失的情況，保證種群的多樣性。

2.8 RRHC局部搜索

為了增強(qiáng)種群尋優(yōu)能力、擴(kuò)大搜索范圍在，跟飛鳥進(jìn)化結(jié)束后，對種群中的個體執(zhí)行局部搜索，保證種群有更大概率找到最優(yōu)解。

RRHC是一種貪婪搜索算法，它可以從比原始的解決方案差的鄰域解開始，重新搜索，以逃避局部最小解。因此引入RRHC對進(jìn)化后的個體執(zhí)行局部搜索。其中，關(guān)鍵路徑[6]是甘特圖中無空閑時間的最長路徑，與調(diào)度方案的最大完工時間緊密相關(guān)。RRHC算法通過替換關(guān)鍵路徑上的關(guān)鍵工序的加工機(jī)器，以盡可能地縮短最大完成時間。

2.9 算法流程

本文算法提出的IMBO-RRHC框架流程圖如圖4所示。

3 仿真試驗

3.1 參數(shù)設(shè)置

在改進(jìn)算法中，RRHC的參數(shù)設(shè)置參考文獻(xiàn)[7]，IMBO算法的主要參數(shù)如下：初始規(guī)模N（51，101，151），鄰域解數(shù)量k，共享鄰域解數(shù)量x，巡回次數(shù)G（3，5，10），解齡閾值limit（5，10，15），總迭代次數(shù)T （100，140，200）。其中，由于k、x這2個參數(shù)之間相互約束，不適用于正交，將k設(shè)定為3，x設(shè)定為1。針對另外2個參數(shù)，根據(jù)其參數(shù)水平，通過正交試驗選出最佳的參數(shù)組合。

基于MK01算例進(jìn)行試驗，取目標(biāo)函數(shù)的平均值作為響應(yīng)變量，表1總結(jié)了所選的正交數(shù)組和相應(yīng)的AVG值。由表1可知，第6組參數(shù)組合下算法能夠得到更優(yōu)的解決方案，因此以下試驗均采用此參數(shù)設(shè)置。

3.2 改進(jìn)算法可行性分析

為驗證改進(jìn)算法的有效性，將3種主要的改進(jìn)策略依次從算法中單獨拿出，構(gòu)造了3種不同的變體算法。在相同條件下，在MK04算例上運行本文所提算法以及這3種變體算法，得到迭代進(jìn)化曲線圖，如圖5所示。

由圖5可知，在收斂速度以及算法取得的最優(yōu)值來看，IMBO-RRHC明顯優(yōu)于其他3種變體算法，證明了改進(jìn)策略的有效性。

3.3 與元啟發(fā)式算法對比

為驗證本文所提算法的優(yōu)越性，將本文算法與文獻(xiàn)[8]、文獻(xiàn) [9]、文獻(xiàn) [10]所提算法進(jìn)行對比（基于Brandimarte[11]算例設(shè)置試驗）。

種群規(guī)模與迭代次數(shù)保持一致，采用Brandimarte的10個算例（MK01～Mk10）設(shè)置對比試驗。在相同條件下，在每個算例的基礎(chǔ)上運行10次，取相對百分比偏差（RPD）和Frideman的非參數(shù)檢驗進(jìn)行比較。在每種情況下，獲得的最優(yōu)值加粗表示。

不同算法在每種算例的OPT和RPD的對比結(jié)果見表2。其中，RPD表示IMO-RRHC算法的最優(yōu)值與其他算法最優(yōu)值的相對百分比偏差，由公式計算出來。OPT表示10次結(jié)果中的得到的最優(yōu)值，BOV表示每種算法獲得的最優(yōu)解，BKV表示每個的歷史最優(yōu)解，如公式（2）所示。

（2）

可以看出，除少部分算例本文算法未獲得最優(yōu)的值外，其余算例都獲得優(yōu)于其他方法的解，獲得最優(yōu)算例的個數(shù)明顯比其他對比算法多。針對算例Mk05、Mk06、Mk09，雖然本文所提算法未獲得最優(yōu)解，但與最優(yōu)解的差距不大。在這10個算例中，本文算法的平均RPD值最小，表明算法求解結(jié)果與以往的最優(yōu)值差距最小。表3顯示了每種算法RPD的平均值排名以及非參數(shù)檢驗的弗里德曼配對檢驗的p值，將IMBO-RRHC與另外3種算法進(jìn)行對比，試驗結(jié)果表明，IMBO-RRHC在幾種算法中RGD均值排名第一，與另外3種對比算法存在顯著差異。證明該算法與對比算法相比存在顯著的優(yōu)勢。

為了進(jìn)一步說明本文算法的收斂效果，以MK04算例為例繪制求解過程收斂圖，如圖6所示。在這4條曲線中，本文所提算法所表示的曲線始終在其他對比曲線的下方且趨于穩(wěn)定。可以表明在較少迭代次數(shù)內(nèi)可以快速取得比另外3種對比算法更小的值，同時迭代曲線的下降速度更快，表明所提混合候鳥優(yōu)化算法具有更強(qiáng)的可搜索性和更快的收斂速度，可以在最少的迭代次數(shù)內(nèi)得到更好的解，因此可以證明本文所提算法在求解柔性作業(yè)車間調(diào)度問題上具有明顯的優(yōu)勢。

4 結(jié)語

本文對柔性作業(yè)車間調(diào)度問題進(jìn)行研究，在MBO算法的基礎(chǔ)上提出了一種混合候鳥優(yōu)化算法，從鄰域結(jié)構(gòu)、共享機(jī)制、局部搜索方面做出相應(yīng)改進(jìn)。領(lǐng)飛鳥與跟飛鳥采用差別鄰域結(jié)構(gòu)設(shè)計，共享基因片段替代共享鄰域解，結(jié)合RRHC算法對進(jìn)化后的個體進(jìn)行局部搜索，通過基準(zhǔn)算例在MATLAB上進(jìn)行對比試驗，驗證了算法的有效性以及可行性，與其他3種改進(jìn)算法對比，本文所提算法具有更快的收斂速度，更適用于求解柔性作業(yè)車間調(diào)度問題。在后續(xù)的研究中將圍繞柔性作業(yè)車間調(diào)度的多目標(biāo)優(yōu)化展開，同時在生成調(diào)度方案的過程中，將機(jī)器的動態(tài)擾動加入研究中，從而使生成的調(diào)度方案更符合實際的生產(chǎn)需求。

參考文獻(xiàn)

[1]BRUCKER P，SCHLIE R.Job-shop scheduling with multi-purpose machines[J].Computing，1990， 45（4）： 369-375.

[2]DENG G，XU M，ZHANG S，et al.Migrating birds optimization with a diversified mechanism for blocking flow shops to minimize idle and blocking time[J].Applied Soft Computing，2022，114（1）： 107834.

[3]WEI L，HE J，GUO Z，et al.A multi-objective migrating birds optimization algorithm based on game theory for dynamic flexible job shop scheduling problem[J].Expert Systems with Applications，2023， 227（1）： 120268.

[4]ZHANG B，PAN Q，GAO L，et al.An effective modified migrating

birds optimization for hybrid flow shop scheduling problem with lot

streaming[J].Applied Soft Computing，2017，52（3）： 14-27.

[5]陸科苗，何利力.基于改進(jìn)NSGA-Ⅱ混合算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題[J].智能計算機(jī)與應(yīng)用， 2022，12（7）： 46-51.

[6]吳樹景，游有鵬，羅福源.變鄰域保優(yōu)遺傳算法求解柔性車間調(diào)度問題[J].計算機(jī)工程與應(yīng)用， 2020， 56（22）： 236-243.

[7]COSTA C F F，DE OLIVEIRA A L M，COSTA M G F.Using random

restart hill climbing algorithm for minimization of component assembly time

printed circuit boards[J].IEEE Latin America Transactions，2010，8（1）： 23-29.

[8]王玉芳，繆昇，葛嘉榮.面向柔性作業(yè)車間調(diào)度的改進(jìn)混合蛙跳算法[J].組合機(jī)床與自動化加工技術(shù)， 2022 （5）： 187-192.

[9]張其文，王超.一種求解柔性作業(yè)車間調(diào)度問題的改進(jìn)灰狼優(yōu)化算法[J].蘭州理工大學(xué)學(xué)報， 2022， 48（3）： 103-109.

[10]杜凌浩，向鳳紅.改進(jìn)多鄰域候鳥優(yōu)化算法的柔性作業(yè)車間調(diào)度研究[J].兵器裝備工程學(xué)報，2022，43（12）： 299-306.

[11]BRANDIMARTE P.Routing and scheduling in a flexible job shop by tabu search[J].Annals of Operations Research，1993，41（3）：157-183.