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

申麗娟

摘要：柔性作業車間調度問題是生產管理中的重要問題。由于建模和計算的復雜性，傳統優化方法往往難以得到最優解，而采用粒子群優化算法求解柔性作業車間的調度問題往往可以得到有效解。本文在標準粒子群算法的基礎上提出了改進的粒子群算法，在克服標準粒子群算法缺陷的基礎上有效提高了其性能，也為其它組合問題的求解提供了理論依據。

關鍵詞：車間調度 粒子群算法 求解柔性

中圖分類號：TP301 文獻標識碼：A 文章編號：1007-9416（2016）05-0000-00

柔性作業車間調度問題[1，2]（flexible Job shop scheduling Problem，FJSP），是指帶有機器可選柔性的車間調度問題。該類問題已經被證明為NP-hard問題，難以取得最優解。目前，學者們對柔性作業車間調度問題進行了廣泛的研究，并提出了許多算法。主要有模擬退火算法（SA）、禁忌搜索算法（TS）、蟻群算法（ACO）、粒子群算法（PSO）[3]和遺傳算法（GA）等。其中粒子群優化算法因其具有通用性強、全局尋優和方便實現等優點，在求解柔性作業車間調度領域有一定的應用。本文提出的一種改進的粒子群優化算法，有效提高了標準粒子群算法求解柔性作業車間調度問題時的性能。

1 標準粒子群算法

粒子群優化算法（Particle Swarm Optimization，PSO），也稱粒子群算法，是一類基于群體智能的進化搜索計算方法。最早是在1995年由美國的Kennedy和Ebehart在受到鳥群尋找食物行為的啟發下共同提出的。算法將所示問題的目標搜索空間與鳥群的飛行空間相類比，為每個粒子制定了與鳥類運動類似的簡單行為規則，使得整個粒子群的運動與鳥類覓食具有相似的運動特性，從而用于求解復雜的優化問題。

2 改進粒子群算法求解FJSP

2.1 編碼

編碼是應用粒子群算法求解柔性作業車間調度問題的關鍵問題，作業車間調度問題大多采用基于工序的編碼，如下所示為一個3個工件在4臺機器上加工的部分柔性作業車間調度實例的排序。

粒子的第一維實向量O可表示為（1 1 1 2 2 3 3 3）。其中第一個1表示工件1的第一道工序O11，依此類推；粒子的第二維實向量Xd表示粒子的位置矢量，這里設由（0，5）之間的數隨機生產。將粒子的位置矢量Xd按從小到大的順序進行排序，同時將粒子的第一維實向量O也隨著Xd的改變而改變，這樣粒子的第一維實向量就形成了一個如下加工工序序列：

每道工序可選擇加工時間最少的機器，若是最小加工時間相同可隨機選擇機器。

2.2 慣性權重的選取

本文采取自然指數自適應的慣性權重選取策略：

式中：G為當前迭代次數；Gmax為最大迭代次數。

3 算法結果比較

采用10個具有代表性的FJSP標準算例來測試，每個算例的最大迭代次數為200，分別獨立運行10次。可以看出，改進粒子群算法最優解總體優于其他三個算法得到的最優解。如表1所示。

4 結語

本文在標準粒子群算法的基礎上提出了改進的粒子群算法，通過與標準算例的結果進行對比，證明了本文提出的改進粒子群算法不僅提高了標準粒子群算法求解柔性作業車間調度問題時的性能，也對粒子群優化算法在求解其它組合問題時提供了理論依據，具有重要的理論價值與實際意義。

參考文獻

[1]高亮，張國輝，王曉娟.柔性作業車間調度智能算法及應用[M].武漢：華中科技大學出版社，2012.

[2]張國輝，高亮，李培根，張起勇.改進遺傳算法求解柔性作業車間調度問題[J].機械工程學報，2009，45（7）：145-151.

[3]趙衛.模擬退火遺傳算法在車間作業調度中的應用[J].計算機仿真，2011，28（7）：361-364.