改進粒子群算法在柔性作業車間調度中的應用

楊文理 李長云

（1、湖南工業大學 計算機學院，湖南 株洲412007 2、智能信息感知及處理技術湖南省重點實驗室，湖南 株洲412007）

近年來，在“中國制造2025”政策的支持下，制造業正迅速朝著信息化的方向發展，車間排產的復雜性、不確定性、多目標性、多約束性導致車間管理仍存在諸多問題，引發很多專家學者對其進行研究。

為了解決柔性車間調度中存在的諸多問題，國內外專家學者提出了一系列改進優化算法。如彭建剛[1]對多目標柔性作業車間調度算法進行了總結，主要采取加權聚合法和Pareto 優化方法對該問題進行求解，但是存在很難得到最有權重值、種群收斂性能等問題。孫麗珍[2]等人提出一種改進的遺傳算法，提出了MCGI 的解碼方案，但是沒有考慮復合動態調度問題。李傳鵬[3]等人討論了柔性作業車間調度現存問題及未來的發展趨勢，提出目前工作對工件生產批量不同的問題研究較少等問題。王艷[4]等人提出一種改進的多目標差分進化算法進行求解，在尋優能力和綜合決策方面表現較優。其中文獻[5]提出了一種對粒子位置狀態更新的改進粒子群優化算法獲得最優工序排序，但是結果受計算經驗限制，性能有待進一步提高。

綜上所述，借鑒研究學者們的經驗，設計了一種混合輪盤賭選擇算子的粒子群算法。通過算例分析，驗證了使用該方法改進的粒子群算法的有效性。

1 柔性作業車間調度模型

1.1 問題描述

在實際生產過程中，柔性作業車間調度問題可以描述為：有n 個工單在m 臺機器上進行生產排程，每個工單對應唯一的生產工藝路線，每條工藝路線包含不完全相同的工序，各工藝路線對應的工序之間具有嚴格的先后順序，每個工序可以選擇多臺機器進行生產，但是每道工序只能在對應的機器上加工一次，相同工序在不同機器上加工時間不同。

一般的車間調度需要滿足以下約束條件：（1）所有工單在生產開始前優先級相同，即不考慮其他因素的情況下，所有工單都有機會在開始時刻進行加工。（2）特定機器上生產某個工單對應工序的生產時間是不變的。（3）若當前生產工序沒用完成時，當前機器不能暫停進行其他任務生產。

1.2 模型構建

本文以最大完工時間最小化為優化目標，結合上述約束條件和數學符號，將柔性作業車間調度數學模型描述如下：

目標函數:

式（1）表示求所有訂單的生產時間之和的最小值，即本文的優化目標；式（2）表示一個工單有且僅有一條加工工藝路線與其匹配；式（3）表示所有訂單的初始優先級都相同；式（4）表示上一個訂單的開始加工時間小于下一個訂單的開始時間，即同一時刻，同一機器在完成當前生產任務前，不能加工其他生產任務。

2 改進的粒子群算法求解FJSP

2.1 粒子群算法

粒子群算法[6]是美國心理學家Kennedy 和電氣工程師Eberhart 在1995 年提出來的，該算法可以由兩個向量表示，它們分別是位置向量和速度向量。粒子所處的位置表示當前問題的可行解，速度則表示粒子在空間中的搜索方向。粒子在求解空間中不斷飛行，更新粒子優化位置，最終尋到全局最優解?？梢杂孟旅鎯蓚€公式表示：

其中，i 表示第i 個粒子；j 表示粒子的第j 維；vij(t)表示粒子i在t 時刻的第j 維飛行速度向量；xij(t)表示粒子i 在t 時刻的第j維的位置分量；pbestij(t)表示粒子種群在t 時刻最佳位置gbestij(t)表示粒子i 在t 時刻第j 維度的分量；c1,c2為學習因子，通常在[0,1]之間隨機取值。

2.2 基于輪盤賭的粒子群算法

為了解決算法早熟收斂問題，我們引入輪盤賭選擇算子對粒子群算法進行改進，具體步驟如下：

步驟5：重復步驟4，得到足夠多的新個體，構建一個新種群。

3 實驗結果與分析

本文選擇10*6 的算例對兩種算法進行實驗，截取其中一個工單的數據如表1 所示。

表1 工單的工序和生產時間表

表1 反映了一個工單對應的工藝路線中包含5 道工序，這5 道工序可以在6 臺機器上進行加工，每道相同工序在不同機器上的加工時間不完全相同。在該問題中，每個訂單對應的工藝路線包含了5 個工序，這些工序可以在全部或部分機器上進行加工，在不同機器上的加工時間不完全相同。

文章設置改進粒子群算法的種群規模為50，最大迭代次數為500，進行實驗，根據實驗結果可知，改進粒子群算法計算的最小完工時間為28，傳統方法為33，由此可知，改進的粒子群算法在全局尋優和種群適應度最小值變化上表現更好。實驗結果如圖1、圖2 所示。

4 結論

文章提出一種改進粒子群算法求解柔性作業車間調度問題，該方法引入了輪盤賭策略對粒子初始化進行改進。實驗表明，改進算法的收斂速度更快、全局尋優能力更強，驗證了本文改進粒子群算法對求解柔性作業車間調度問題的有效性。

圖1 改進算法的全局最優解的變化情況和種群適應度最小值的變化情況

圖2 傳統算法的全局最優解的變化情況和種群適應度最小值的變化情況