混合粒子群算法求解作業車間調度問題

劉鳳杰，薛仁政

混合粒子群算法求解作業車間調度問題

劉鳳杰，薛仁政

（齊齊哈爾大學 計算機與控制工程學院，黑龍江 齊齊哈爾 161006）

針對最小化完工時間的作業車間調度問題，提出混合的粒子群優化算法. 針對作業車間調度中隨機交換2個工件鄰域變換存在盲目性，采用機器空閑時間的關鍵工序鄰域搜索算法，結合粒子群算法收斂速度快和遺傳算法變異操作增加全局搜索能力的優點，將2種算法結合. 通過標準JSP問題測試庫驗證了算法的有效性．

粒子群算法；車間調度；關鍵路徑；鄰域搜索

智能優化算法被廣泛應用于作業車間調度問題．薛玲玲[1]采用基于工序的編碼方法，在編碼后的個體上進行鄰域構建的基于塊結構鄰域搜索的遺傳算法，求解作業車間調度最小化最大完工時間．劉麗娜[2]等針對求解后期易陷入局部最優，利用量子計算、正余弦搜索和警戒者數量遞減策略對麻雀搜索算法進行改進，優化作業車間調度問題．王玉芳[3]等提出加入自適應調整的遺傳操作以及精英替換策略的改進混合遺傳模擬退火算法，應用于作業車間調度問題求解．何斌[4]等提出動態交叉與變異概率的一種改進的遺傳算法優化作業車間調度的最小化最大完工時間．Nouiri[5]等以最小化最大完工時間為目標，提出了一種混合離散粒子群優化算法，用于求解具有資源柔性的雙資源約束作業車間調度問題．Amin[6]等研究了基于周期事件調度問題的周期作業車間調度問題，提出了一種基于粒子群優化和模擬退火算法的混合算法．呂媛媛[7]等提出一種新的改進多目標粒子群算法優化最小化最大完工時間和最小化總拖延時間．

本文結合JSP的特點，提出結合遺傳算法改進的粒子群算法．該算法自適應慣性權重和學習因子，提高了搜索能力．基于工序的編碼方式，采用混沌動力學模型初始化粒子，使粒子均勻分布解空間，引入關鍵路徑鄰域搜索，克服隨機交換工序的盲目性．此算法在JSP基準算例上進行測試，驗證了算法的有效性．

1 作業車間調度模型

JSP模型被定義為

適應值是評價一個粒子所處位置優劣程度的函數，適應值越高，粒子所在位置越優秀，適應度值越低，粒子所處位置越差，粒子的適應度值評價公式為

2 混合粒子群求解JSP

2.1 改進粒子群優化算法

2.1.1 標準粒子群算法 粒子群算法（Particle Swarm Optimization，PSO）是通過研究鳥類群體覓食活動提出的一種群智能優化算法．由于該算法形式簡單，參數少，收斂速度快等優點，因此獲得了國內外學者的廣泛關注．

2.1.2 自適應慣性權重和學習因子 在粒子群算法中，既要考慮全局搜索能力，又要考慮局部搜索能力，全局搜索能力能夠增加搜索范圍，局部搜索能力能夠搜索最優值．當粒子靠近最優值時增加局部搜索能力，否則增加全局搜索能力，基于此方案提出自適應慣性權重計算方法，自適應慣性權重進行更新

本文改進粒子群算法的速度和位置公式為

2.2 改進遺傳算法

遺傳算法（Genetic Algorithm，GA）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，有較強的局部和全局搜索能力，在很多領域得到應用．遺傳算法通過建立初始種群，計算適應度，按照一定方法進行選擇、交叉和變異操作進行搜索最優解．選擇、交叉、變異操作是遺傳算法的關鍵性操作.

在遺傳算法中，交叉操作提高收斂速度，但其在局部尋求最優解；變異操作收斂速度慢，但能夠增加全局尋求最優解．結合交叉和變異操作的優勢，在初期增加全局尋優能力，在算法后期增加局部尋優能力，提出一種自適應交叉、變異的遺傳算法．

2.2.1 交叉操作 交叉操作是對種群中染色體進行隨機配對，對種群中選中的染色體以一定的概率交換種群的基因片段，產生新的染色體．交叉的方式包括：單點交叉、多點交叉、均勻交叉．交叉操作增加了局部搜索能力，本文的交叉操作每次交叉隨機選用3種交叉方式中的一種，對染色體的工件進行交叉操作．

2.2.2 變異操作 變異操作是模擬自然界生物變異的過程，采用文獻[8]自適應變異概率改變染色體的基因片段來改變基因，增加種群的多樣性．變異操作采用兩點交換、基因段逆序、隨機插入工序、打亂互換4種操作．

2.2.3 選擇操作 選擇操作是將父代個體的信息傳遞給子代的過程，在選擇操作過程中希望將適應度高的父代以較高的概率進行傳遞．通過選擇操作，使后代個體中優秀的個體數量增加，有利于后代整體向更好的方向進化．根據適應度決定父代個體被選擇的概率為

2.3 編碼與解碼

在作業車間調度問題中由于基于工序的編碼方式簡單、直觀，所以本文采用基于工序的編碼方式．基于工序的編碼方式，采用隨機初始種群會產生較多劣解和重復解，影響了算法的搜索能力．本文采用混沌動力學模型logistic[9]77生成初始種群，生成初始種群的公式為

在確定工序的加工順序后，通過從左到右的順序對工序編碼安排加工，工件號第１次出現，表示該工件第１道工序被加工，工件號第２次出現，表示該工件第２道工序被加工進行解碼．

2.4 關鍵路徑鄰域搜索

在作業車間調度中，由于工件加工受加工工序的限制，導致最大完工時間增加的原因是由機器空閑時間造成的．在一個可行調度中，工序之間無時間間隔的最長路徑稱為關鍵路徑，關鍵路徑上的工序為關鍵工序．車間調度中最大完工時間取決于關鍵路徑的長度，關鍵路徑由關鍵工序組成，調整關鍵工序的加工順序將影響最大完工時間．通過搜索機器空閑時間，調整關鍵工件加工順序，減少機器空閑時間，能夠減小最大完工時間．

2.5 混合粒子群算法

本文采用混沌動力學模型初始化粒子，將改進的粒子群算法與遺傳算法相結合，引入關鍵路徑鄰域搜索，求解作業車間調度最小化最大完工時間．該算法流程見圖1．

3 實驗結果與分析

本文采用JSP標準問題測試庫中選取FT類：FT06，FT10，FT20，LA類：LA01，LA06，LA11，LA16共7個算例進行求解，每個算例求解20次．

實驗環境為：操作系統為Windows10，編程語言為Python3.6，CPU為Intel（R）Core（TM）i7-11800H 2.30 GHz，內存為32 G，最大迭代次數為200，種群數量為200，程序獨立運行20次，與標準粒子群算法和IPSO算法[9]80及文獻[10]的F&F算法進行比較，結果見表1．

圖1 混合粒子群算法流程

表1 算法測試結果對比

由表1可知，本文提出的混合粒子群算法共找到6個算例的最優解，且結果穩定，20次求解均可找到最優解；對于未找到最優解的FT20問題，其20次求解的最優解相比其他算法也表現良好．因此，本文所提出的算法具有良好的性能．

4 結語

本文結合粒子群算法收斂速度快和遺傳算法變異操作增加全局搜索能力的優點，將2種算法結合，設計了混合粒子群優化算法．為了使初始化粒子均勻分布解空間，采用混沌動力學模型生成初始種群，采用機器空閑時間的關鍵工序鄰域搜索算法解決了隨機交換工件存在的盲目性的缺點．通過標準JSP問題測試庫驗證了算法的有效性，優化了作業車間調度最小化最大完工時間．未來將探索其改進算法解決FJSP．

[1] 薛玲玲．作業車間調度的塊結構鄰域搜索遺傳算法[J]．計算機集成制造系統，2021，27（10）：2848-2857．

[2] 劉麗娜，南新元，石躍飛．改進麻雀搜索算法求解作業車間調度問題[J]．計算機應用研究，2021，38（12）： 3634-3639．

[3] 王玉芳，繆昇，馬銘陽，等．改進混合遺傳算法的作業車間調度研究[J]．現代制造工程，2021（5）：32-38．

[4] 何斌，張接信，張富強．一種求解作業車間調度問題的改進遺傳算法[J]．制造業自動化，2018，40（8）：113-117．

[5] Nouiri M，Bekrar A，Jemai A，et al．An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem[J]．Journal of Intelligent Manufacturing，2018，9（3）：603-615．

[6] Amin J，Shafia M A，Moghaddam R T．A hybrid algorithm based on particle swarm optimization and simulated annealing for a periodic job shop scheduling problem[J]．The International Journal of Advanced Manufacturing Technology，2011，54（1）：309-322．

[7] 呂媛媛，樊坤，瞿華，等．多目標粒子群算法求解混合多處理機任務作業車間調度問題研究[J]．小型微型計算機系統， 2022，43（1）：218-224．

[8] Rinivas M，Patnaik L M．Adaptive probabilities of crossover and mutation in genetic algorithm[J]．IEEE Transactions on Systems， Man，and Cybernetics，1994，24（4）：656-667．

[9] 劉洪銘，曾鴻雁，周偉．基于改進粒子群算法作業車間調度問題的優化[J]．山東大學學報（工學版），2019，49（1）： 75-82．

[10] REDO C，DUARTE R．A filter-and-fan approach to the job shop scheduling problem[J]．European Journal of Operational Research，2009，194（3）：660-662．

Hybrid particle swarm optimization for solving job-shop scheduling problem

LIU Fengjie，XUE Renzheng

（School of Computer and Control Engineering，Qiqihar University，Qiqihar 161006，China）

Aiming at the job-shop scheduling problem of minimizing completion time，a hybrid particle swarm optimization algorithm is proposed．Aiming at the blindness of neighborhood transformation of randomly exchanging two workpieces in job-shop scheduling，the key process neighborhood search algorithm of machine idle time is adopted．Combined with the advantages of fast convergence speed of particle swarm optimization algorithm and mutation operation of genetic algorithm to increase the global search ability，the two algorithms are combined．The effectiveness of the algorithm is verified by the standard JSP problem test library．

particle swarm optimization algorithm；job-shop scheduling；critical path；neighbor search

TP399

A

10.3969/j.issn.1007-9831.2022.06.007

1007-9831（2022）06-0038-06

2022-03-20

黑龍江省省屬高等學校基本科研業務費科研項目（135409224）

劉鳳杰（1978-），女，黑龍江克山人，助理實驗師，從事計算機應用研究．E-mail：liufengjie@126.com