申麗娟

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

關(guān)鍵詞：車間調(diào)度 粒子群算法 求解柔性

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

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

1 標準粒子群算法

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

2 改進粒子群算法求解FJSP

2.1 編碼

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

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

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

2.2 慣性權(quán)重的選取

本文采取自然指數(shù)自適應(yīng)的慣性權(quán)重選取策略：

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

3 算法結(jié)果比較

采用10個具有代表性的FJSP標準算例來測試，每個算例的最大迭代次數(shù)為200，分別獨立運行10次?？梢钥闯?，改進粒子群算法最優(yōu)解總體優(yōu)于其他三個算法得到的最優(yōu)解。如表1所示。

4 結(jié)語

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

參考文獻

[1]高亮，張國輝，王曉娟.柔性作業(yè)車間調(diào)度智能算法及應(yīng)用[M].武漢：華中科技大學(xué)出版社，2012.

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

[3]趙衛(wèi).模擬退火遺傳算法在車間作業(yè)調(diào)度中的應(yīng)用[J].計算機仿真，2011，28（7）：361-364.