基于帶隨機網絡的多種群粒子群優化算法求解多資源受限柔性作業車間調度問題

2022-04-23 04:44:40崔航浩張春江李新宇

重慶大學學報 2022年4期

崔航浩，張春江，李新宇

(華中科技大學機械科學與工程學院，武漢 430070)

多資源受限柔性作業車間調度問題(MRC-FJSP，multi-resource constrained flexible job shop scheduling problems)是一種由經典柔性作業車間調度問題(FJSP，flexible job shop scheduling problems)擴展而來的NP-hard問題。在許多現實的生產環境中，不僅需要考慮加工機器的分配，還要考慮用于服務加工機器的各類受限附資源的分配[1]。MRC-FJSP正是為了解決這一類生產調度問題而被提出的，自2004年提出以來就備受專家學者和工程技術人員的關注。

與傳統FJSP相比，MRC-FJSP增加了機器準備時間和附資源約束，是比傳統FJSP更為復雜的NP-hard問題。近似方法可以在一個合理的時間范圍內求得一個較優解，在MRC-FJSP的科學研究和工程實踐中得到廣泛的應用。在過去的十多年里，隨著計算機科學與技術的發展，大量元啟發式算法(如遺傳算法[2-3]、果蠅算法[4]、候鳥優化算法[5]等)被用于求解MRC-FJSP，取得了不錯的效果。Wu等[2]采用遺傳算法(GA，genetic algorithm)求解以最小化最大完工時間為目標的MRC-FJSP；Hao等[6]采用合作分布估計算法(CEDA，cooperative estimation of distribution algorithm)求解MRC-FJSP，通過引入分治策略擴展了合作進化的框架，充分考慮了群體決策過程中相互依賴關系的影響。

隨著人工智能技術的突飛猛進，近幾年涌現出許多更加高級的群智能算法，這些新算法為MRC-FJSP的求解提供了新的技術思路。Wang等[7]提出采用基于知識庫的多智能體進化算法(KMEA，knowledge-based multi-agent evolutionary algorithm)求解MRC-FJSP，使用混合初始化機制來平衡初始智能體群的多樣性和質量，并使用知識庫來存儲搜索過程中獲取的有用信息；Cao等[8]提出采用一種基于強化學習和代理模型的布谷鳥搜索算法(CSRS，cuckoo search algorithm with reinforcement learning and surrogate modeling)求解MRC-FJSP。但是目前大多文獻只是停留在算法層面的革新，并沒有深入挖掘MRC-FJSP的特征信息。

粒子群優化算法(PSO，particle swarm optimization)是Eberhart等[9]在1995年首次提出的，受自然界中鳥群覓食行為的啟發，被成功應用到各種組合優化問題上[10-11]。筆者針對MRC-FJSP問題特點，對PSO算法進行改進，設計基于關鍵路徑的鄰域結構，引入基于隨機網絡結構的多種群策略和重新初始化策略，成功將PSO算法應用于求解MRC-FJSP，取得了較好的結果。

1 MRC-FJSP問題描述

多資源柔性作業車間調度問題是傳統FJSP的拓展[12]，主要在FJSP的基礎上增加了機器準備時間和附資源約束。MRC-FJSP包含機器分配子問題、工序排列子問題和機器配置子問題。MRC-FJSP可以被描述如下：

1)有n個工件(J1，J2，…，Jn)要在m臺機器(M1，M2，…，Mm)上加工[13]；

2)每個工件包含ni道工序，工序的順序是預先確定的；

3)每道工序Oij都可以從可選加工機器集Ωij中任選一臺機器進行加工；

4)工序Oij在機器Mk上的加工時間是恒定且預知的；

5)在車間有r類附資源(R1，R2，…，Rr)，每類附資源的數量是預先確定的；

6)同一臺機器在同一時刻只能加工一道工序[14]；

7)同一個附資源在同一時刻只能服務一臺機器；

8)同一工件的同一道工序在同一時刻只能被一臺機器加工；

9)每一道工序一旦開始加工就不允許中斷[15]；

10)同一工件的不同工序之間有優先級約束，不同工件的不同工序之間沒有優先級約束[16]；

11)所有工件在零時刻都可以被加工，所有機器和附資源在零時刻都可以被使用；

12)考慮機器準備時間[3]。

以最小化最大完工時間為目標函數，其公式表示形式如下:

minCmax=min(max(Ci)),1≤i≤n。

(1)

式中Ci為工件i的加工完成時間。

2 基于MPSO-RDnet求解MRC-FJSP

2.1 編碼與解碼

2.1.1 編碼

由于不考慮同一類附資源的單件之間的差異性，單獨編寫機器配置向量會導致搜索空間過大，使算法的尋優效率降低。因此，MRC-FJSP只編寫工序排列向量和機器分配向量，各加工機器的附資源配置在解碼階段動態決策。

對于工序排列向量，采用FJSP研究文獻中常用的基于工件編號的表示方法。使用相同的工件編號來表示同一個工件的所有工序。從左到右，第k次出現的工件編號，表示對應工件的第k道工序。以圖1為例，工序排列向量{1,3,2,1,2,4,1}表示的加工序列為{O11,O31,O21,O12,O22,O41,O13}。

圖1 粒子個體編碼Fig. 1 Encoding of individual particles

機器分配向量采用基于機器編號的表示方法，其長度與工序排列向量相同。從左到右，依次表示1號工件第1道工序至最后一道工序的所選機器、2號工件第1道工序至最后一道工序的所選機器、…、n號工件第1道工序至最后一道工序的所選機器。以圖2為例，機器分配向量{1,3,1,1,2,2,3}表示的各工序與所選機器的對應關系為{(O11,1), (O12,3), (O13,1), (O21,1), (O22,2), (O31,2), (O41,3)}。

2.1.2 解碼

解碼的過程就是確定每道工序在所選機器上的開始加工時間。對于MRC-FJSP而言，如果要開始加工某一道工序，需要同時滿足3個條件：

1)工件已到達所選機器；

2)所選機器處于空閑狀態，且已完成加工前的準備工作；

3)所選機器需要配置的所有附資源均可以立刻投入使用。

基于上述約束條件，MRC-FJSP中各工序的開始加工時間可以通過公式(2)計算得到：

sij=max(sij-1+pij-1k′,Ak+tk′k,Ahk)。

(2)

式中：sij表示工序Oij的開始加工時間；pij-1k′表示工序Oij-1在機器k′上的加工時間，sij-1+pij-1k′表示工件i的最早可用時間；Ak表示機器k的釋放時間，tk′k表示機器k的準備時間，Ak+tk′k表示機器k的最早可用時間；Ahk表示機器k所需的附資源h的釋放時間。

機器配置子問題采用啟發式規則進行處理：在sij時刻，如果同一類附資源有多個單件可供選擇的話，選擇釋放時間最接近sij的單件。這一選擇不會推遲當前工序的開始加工時刻，但為后續工序的盡早加工留出了余地。

2.2 種群初始化

種群初始化方式影響算法的收斂速度和求解質量。工序排列向量采用隨機初始化方式，機器分配向量采用混合初始化方式，通過試錯法設定針對機器分配向量的3種初始化策略的選擇概率。其中選擇隨機初始化的概率為60%，選擇最早完工時間(ECT，earliest completion time)優先的概率為20%，選擇準備時間與加工時間之和最短(SSPT，shortest setup plus process time)優先的概率為20%。

2.3 子種群“社會認知”階段

“社會認知”階段是子種群內部的信息交互，是子種群內較差粒子向較優粒子靠近的過程。子種群“社會認知”階段的具體操作步驟如下。

第1步：對每個子種群中的粒子按照適應度值排序，找到每個子種群中最優的2個粒子和最差的2個粒子；

第2步：最優粒子與次劣粒子交互。交互時，工序排列向量采用改進優先工序交叉(IPOX，improved precedence operation crossover)算子，機器分配向量采用多點保留交叉(MPX，multi-point crossover)算子。從交叉得到的2個新粒子中隨機選取一個，替換粒子對中的較差粒子；

第3步：次優粒子與最差粒子交互，交互和替換方法與第2步相同。

IPOX算子和MPX算子的具體執行過程如圖2和圖3。圖中J1和J2表示工件集合，P1和P2表示父代1和父代2，C1和C2表示交叉得到的子代1和子代2。

圖3 MPX算子操作示例Fig. 3 Example of MPX operator operation

2.4 子種群“自我認知”階段

“自我認知”階段是粒子的鄰域搜索過程。如果在附資源約束下進行鄰域搜索，可行的移動方案會非常少，在尋找可行鄰域解的過程中會消耗大量的計算資源，得不償失。因此MRC-FJSP的鄰域移動分為兩步，先進行帶準備時間的FJSP的鄰域移動，得到一個中間解；再使用2.1.2節中所述方法完成各機器的附資源配置，得到一個可行鄰域解。

定理1：當機器準備工作的完成時刻與工序的開始加工時刻相等時，機器時間利用率最大[17]。

證明：當準備工作完成后，當前機器已被某個工件鎖定，不能再加工其他工件，只能等候該工件到達。如果延長這一等待時間，最大完工時間可能不會變大，但一定不會變小。當機器準備時間與工序加工時間無縫銜接時，時間利用率最高。

關鍵路徑的變化是改變最大完工時間的關鍵，也是構造鄰域結構的重要組成部分。關鍵路徑的定義是從0時刻到終止時刻，順次滿足公式(3)的工序所組成的路徑：

sOij-(sKPJ[Oij]+pKPJ[Oij]k[KPJ[Oij]])≤tk′k。

(3)

式中：KPJ[Oij]表示工序Oij所在關鍵路徑上的緊前工序；sKPJ[Oij]+pKPJ[Oij]k[KPJ[Oij]]表示KPJ[Oij]的完工時間(開始時間+加工時間)。

以MRC-FJSP的問題特征為導向，設計出MRC-FJSP的2個鄰域結構：換機器的鄰域結構(N-CM，neighborhood of changing machine)和同機器的鄰域結構(N-SM，neighborhood of the same machine)。

2.4.1 換機器的鄰域結構

基于N-CM的鄰域移動可以歸納為以下步驟：

1)從當前解的某條關鍵路徑中隨機選取一道工序，判斷該工序是否有2個以上(含2個)的可選機器。若有，則進行步驟3；若沒有，則重新選取工序，直至找到滿足條件的工序Oij。

2)把工序Oij從它當前機器的加工序列中刪除。

3)從工序Oij的其他可選機器中隨機選擇一個，把Oij插入到所選機器的加工序列中，并保證插入后的解依然為可行解。

可行插入

一個可行的插入，是要保證插入后的加工路線不存在閉合回路。

Lk：Lk=(Oxy∈Qk|sxy

(4)

Rk：Rk=(Oxy∈Qk|sxy+pxyk>sij-1+pij-1k′)。

(5)

式中：Qk表示在機器k上加工的所有工序的集合；對于集合Lk里的工序而言，不存在從Oij到Oxy的加工路徑；對于集合Rk里的工序而言，不存在從Oxy到Oij的加工路徑。

定理2：把Oij插入到Lk-Rk所含工序之后和Rk-Lk所含工序之前，都是可行插入[18]。

用Fijk表示把Oij插入機器k的加工序列中得到的可行解集。定理2的可視化示例見圖4。

圖4 可行插入的可視化示例圖Fig. 4 Visual examples of feasible insertion

最優插入

在所有可行插入中，可以獲得最好解的插入就是最優插入。

示例1：當Lk∩Rk≠Φ時，把Oij插入到Lk-Rk所含工序之后和Rk-Lk所含工序之前，會有一個最優插入。

示例2：當Lk∩Rk=Φ時，把Oij插入到Lk所含工序之后和Rk所含工序之前，都是最優插入。

2.4.2 同機器的鄰域結構

N-CM在進行鄰域移動之前，必須事先確定Lk和Rk，通過二進制搜索算法獲得Lk和Rk的時間復雜度為O(log |Qk|)。為了提高算法的運行速度，降低時間開銷，對于不換機器的鄰域移動，采用一種更加簡單高效的方法。

基于N-SM的鄰域移動也是在關鍵路徑上進行的。在介紹N-SM之前，首先說明關鍵塊的含義。關鍵塊指的是在同一臺機器上的關鍵工序組成的最大序列。

基于N-SM的鄰域移動，就是交換同一關鍵塊的塊首和塊尾2道工序(圖5)。但是在交換過程中，需要滿足下列條件：

1)首關鍵塊只交換塊尾2道工序，尾關鍵塊只交換塊首2道工序；

2)如果把工序Oij移動到工序Oi′j′之后，則必須保證Oij+1在Oi′j′之后；

3)如果把工序Oij移動到工序Oi′j′之前，則必須保證Oij-1在Oi′j′之前；

4)同一個工件的工序之間不得交換。

圖5 基于N-SM的鄰域移動Fig. 5 Neighborhood mobilizing based on N-SM

子種群“自我認知”階段的具體操作步驟如下：

第1步：找到當前解的一條關鍵路徑；

第2步：執行基于N-CM的鄰域移動；

第3步：執行N-SM的鄰域移動2次，確保2次選擇的關鍵塊分別屬于不同的加工機器；

第4步：存檔鄰域解1，調用解碼算法計算其最大完工時間Cmax；

第5步：重復第1步到第3步1次；

第6步：存檔鄰域解2，調用解碼算法計算其Cmax；

第7步：比較鄰域解1和鄰域解2的Cmax，用較優的鄰域解替換當前粒子。

2.5 子種群間信息交互

MRC-FJSP的工件數量和機器數量都相對較多，導致解空間比較龐大，如果僅僅依靠單個種群進行迭代搜索，算法的效率比較低。多種群并行搜索機制既可以滿足單次迭代搜索方向的多元化需求，也在客觀上維護了種群的多樣性，在復雜優化問題中被廣泛應用。目前文獻中常用的多種群策略是離散重組和基于網絡結構通信的多種群策略。

離散重組大體操作如下：在每次迭代完成后，打破原有的子種群束縛，將所有個體重新歸為一個大種群；根據適應度值高低，將種群劃分為若干個層次；每個層次隨機選取一定數量的個體填充入各子種群中；新組建的子種群再依據相應的規則進行下一輪迭代搜索。雖然離散重組起到了保持種群多樣性的作用，但每次重組后，原有子種群個體之間建立的關系被打破，新子種群個體之間需要重新磨合，導致算法后期收斂的精度不高。

目前應用比較廣泛的網絡結構圖有3種：無標度網絡[19]、分塊對角網絡[19]和隨機網絡[20]。隨機網絡是指度分布滿足均勻分布的網絡結構，見圖6。各節點之間的連接關系通過連接概率(CP，connection probability)進行調節。當CP取值較大時，各節點的度數普遍較高；當CP取值較小時，各節點的度數普遍較低。隨機網絡由于連接概率的可變性，適應能力較強，能夠應對許多具有不同性質的復雜問題。

圖6 隨機網絡結構圖Fig. 6 Random network structure

本研究中采用基于隨機網絡結構的多種群策略，在數值實驗環節會給出帶有不同多種群策略的PSO算法的對比結果。

為避免算法早期精英片段在子種群之間傳播過快，導致早熟收斂，特設計了自適應信息交互控制因子Pc：

(6)

式中：Inow表示當前迭代次數；Imax表示最大迭代次數；R為傳播頻率，在數值實驗環節進行設置。

子種群間信息交互階段的具體操作步驟如下。

第1步：生成一個位于區間(0,1)內的隨機數。如果該隨機數小于Pc，則進行第2步到第4步；否則，本次迭代不進行子種群間信息交互；

第2步：根據連接概率CP獲取用以指導子種群交互的關系矩陣A。A是一個二維矩陣，里面存儲著0-1變量。當變量取值為1時，表示矩陣橫縱坐標編號代表的2個子種群存在交互關系；當變量取值為0時，表示矩陣橫縱坐標編號代表的2個子種群不存在交互關系；

第3步：按照關系矩陣A，2個需要交互的子種群里適應度值居中的粒子分別與另一個子種群的最優粒子進行交互，得到2個新位置。交互時，工序排列向量采用IPOX算子，機器分配向量采用MPX算子；

第4步：在2個新位置中隨機選取1個替換中間粒子的當前位置。

2.6 子種群重新初始化

有些時候會出現某個子種群連續多次迭代中最優解未得到更新的情況，此時子種群已陷入局部最優。為了避免浪費計算資源、提高算法的魯棒性，對連續T次都未更新最優解的子種群執行重新初始化操作。子種群重新初始化操作是對搜索停滯的子種群中適應度值靠后的3個個體初始化。

2.7 算法流程

結合上文對算法各組件的論述，MPSO-RDnet的算法流程如圖7所示。

圖7 MPSO-RDnet算法流程圖Fig. 7 Flow chart of improved MPSO-RDnet algorithm

3 數值實驗與結果分析

3.1 標準測試算例

目前MRC-FJSP的研究者都采用Wu等[2]在2008年提出的SFTSP算例測試自己算法的性能，該算例可以在決策分析實驗室門戶網站的子頁：https:∥dalab.ie.nthu.edu.tw/newsen_content.php?id=0上找到。SFTSP算例共包含5個large-scale算例(LS1、LS2、LS3、LS4和LS5)和5個wide-range算例(WR1、WR2、WR3、WR4和WR5)。large-scale算例包含100個工件、36臺機器，每臺機器需要配置3類附資源，加工時間位于區間[1,15]內，機器準備時間位于區間[1,5]內；wide-range算例包含60個工件、36臺機器，每臺機器需要配置3類附資源，加工時間位于區間[1,50]內，機器準備時間位于區間[1,15]內。

MPSO-RDnet算法在MATLAB R2016a軟件上編寫，運行環境為Core 4C+6G 1.9GHz CPU及Windows10系統。

3.2 性能評價指標與參數設置

3.2.1 性能評價指標

為了綜合評估算法的收斂性和穩定性，提出了平均相對優勝偏差(ARSD，average relative success deviation)的概念。在介紹ARSD之前，首先給出相對優勝偏差(RSD，relative success deviation)的定義。

(7)

(8)

式中：RSDbm為算法求解第bm個算例的相對優勝偏差；BM表示SFTSP的總算例數，取值為10。

ARSD越小，說明算法的綜合性能越好。

3.2.2 性能評價指標

為了后面算法對比的公平性，參考了文獻中其他算法的參數設置，MPSO-RDnet把解的最大評估次數10 000次作為迭代終止條件，種群規模設為60。算法運行中，對子種群規模、連接概率、傳播頻率和子種群重新初始化閾值進行多次調整，得到使運行效果最佳的值分別為5、0.1、0.6、10。

3.3 基于隨機網絡結構的多種群策略的有效性驗證

多種群策略在維護種群多樣性方面有顯著的優勢。為了找到最適合的多種群策略，采用實驗設計法。在保證其他參數不變的前提下，PSO在不同多種群策略下針對每一個算例獨立運行10次，得到的ARSD如表1所示。

表1 帶有不同多種群策略的PSO求得的ARSD

從表中可以看出，帶隨機網絡的多種群PSO算法在求解MRC-FJSP上效果最好。這是因為隨機網絡結構中的連接概率可以根據問題需要進行調節，使算法的魯棒性更高。

3.4 算法對比

為了驗證MPSO-RDnet在求解MRC-FJSP上的適用性和有效性，特將MPSO-RDnet算法與目前求解MRC-FJSP最先進的5個算法(nFOA[4]、KMEA[7]、SM2-MBO[5]、CCIWO[21]、WSA[22])進行比對。與這5個算法一樣，MPSO-RDnet也針對每一個算例獨立運行10次，得到的對比結果見表2。從表中可以看出MPSO-RDnet得到了所有算例的上界，均值刷新了除WR4以外的原有保持記錄，標準差(SD)方面也表現不錯。這說明了MPSO-RDnet的魯棒性非常高。但在運行時間(tCPU)上，MPSO-RDnet位于中等水平，這說明MPSO-RDnet的求解效率還有待提升。