改進(jìn)粒子群算法在求解柔性作業(yè)車間調(diào)度問題中的應(yīng)用

申麗娟

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

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

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）05-0000-00

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

1 標(biāo)準(zhǔn)粒子群算法

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

2 改進(jìn)粒子群算法求解FJSP

2.1 編碼

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

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

每道工序可選擇加工時(shí)間最少的機(jī)器，若是最小加工時(shí)間相同可隨機(jī)選擇機(jī)器。

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

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

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

3 算法結(jié)果比較

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

4 結(jié)語

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

參考文獻(xiàn)

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

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

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