李　解　任魏翔　秦永彬

(貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院　貴陽　550025)

混合流水車間調(diào)度問題的IPSO算法

李解任魏翔秦永彬

(貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院貴陽550025)

摘要混合流水車間調(diào)度問題又稱柔性流水車間調(diào)度問題,廣泛存在于現(xiàn)代工業(yè)之中。它是對傳統(tǒng)流水車間的擴展。其中,每道工序可能有多臺機器負責(zé)處理。針對混合流水車間調(diào)度問題,論文以最小化最大完成時間為目標(biāo)建立整數(shù)規(guī)劃模型,將經(jīng)典粒子群優(yōu)化算法進行改進,并同教與學(xué)算法(Teaching-Learning Based Optimation,TLBO)相結(jié)合,提出了一種用于解決該問題的改進的粒子群算法(Improved Particle Swam Optical Algorithm,IPSO)。算法在產(chǎn)生初始種群的過程中,首先將原問題轉(zhuǎn)化為一系列置換流水車間調(diào)度問題,并求得其解。之后,將得到的解作為初始種群的一部分。由于現(xiàn)有的粒子群算法具有易收斂于局部最優(yōu)解的缺點。因此為防止算法收斂于局部最優(yōu)解,引入變異操作。此外,在粒子群優(yōu)化算法的基礎(chǔ)上引入適用于求解混合流水車間的TLBO算法的老師階段和學(xué)生階段。設(shè)計正交試驗對算法參數(shù)設(shè)置進行分析,并確定了較優(yōu)的參數(shù)組合。通過基于算例的仿真實驗,并與現(xiàn)有的解決混合流水車間調(diào)度問題的算法進行比較,驗證所提出IPSO算法是有效的。

關(guān)鍵詞流水車間調(diào)度; 粒子群算法; TLBO; IPSO; 最大完成時間

Class NumberTP312

1引言

混合流水車間調(diào)度問題是置換流水車間調(diào)度問題的擴展?；旌狭魉囬g由一系列生產(chǎn)階段組成。其中,至少一個階段包括多臺并行機器。每個待處理任務(wù)包含相同的工序,并且每個任務(wù)工序順序相同。任務(wù)的每道工序只由相應(yīng)生產(chǎn)階段中的一臺機器處理。混合流水車間調(diào)度問題作為置換流水車間調(diào)度問題的擴展,其研究成果不僅應(yīng)用于電子[1]、汽車[2]等制造行業(yè),而且在實時圖像分析技術(shù)[3]等計算機領(lǐng)域的前沿發(fā)揮了重要作用。由于具有兩個生產(chǎn)階段,第一個生產(chǎn)階段機器數(shù)為1,第二個生產(chǎn)階段機器數(shù)為2的混合流水車間調(diào)度問題已是強NP-hard[4]。因此,在問題規(guī)模增加的情況下,合理的時間內(nèi)已無法精確求得條件更為復(fù)雜的混合流水車間調(diào)度問題的最優(yōu)解。Wittrock[5]首次提出以最小化最大完成時間為目標(biāo)且生產(chǎn)階段數(shù)大于3的混合流水車間調(diào)度問題,并為該問題提出了一種分支定界算法。為更加有效地得到該類問題的近似解,并且使其更接近于最優(yōu)解蟻群算法[6]、模擬退火算法[7]、禁忌搜索[8]等智能優(yōu)化算法及其混合算法[9～10]被用于混合流水車間調(diào)度問題。其中,蟻群算法通過模擬蟻群搜索食物求解調(diào)度問題。該算法的并行性高且不易收斂于局部最優(yōu)解。但是由于蟻群算法相對復(fù)雜。因此,該算法的收斂速度慢。模擬退火算法來源于固體有高溫降溫至常溫過程中分子由無序狀態(tài)到基態(tài)的物理原理。該算法能夠搜索到較接近于最優(yōu)解的近似解,并且易于實現(xiàn)。但是模擬退火算法對參數(shù)的選擇較敏感,且對問題的解搜索速度慢。禁忌搜索算法是一種模擬人類思考過程中的記憶功能避免對問題的一些解的迂回搜索的算法。該算法的運行結(jié)果對初始解具有較強的依賴性。與以上智能優(yōu)化算法不同的是,粒子群算法具有簡潔性、易實現(xiàn)以及快速收斂性等優(yōu)點。但是該算法在已陷入局部最優(yōu),并且其理論基礎(chǔ)不完善。因此,該算法仍存在大量的研究空間。

粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法最早是為解決連續(xù)非線性函數(shù)而提出的一種智能優(yōu)化算法[11]。該算法通過模擬鳥群等動物群體的遷移活動來解決各種優(yōu)化問題?，F(xiàn)階段對PSO算法的改進主要集中在與其他算法相結(jié)合、改進編碼方式,利用其他算法的解作為初始種群的一部分等方面。

教與學(xué)優(yōu)化算法(Teaching and Learning Based Optimation,TLBO)來源于學(xué)校教學(xué)過程中老師對學(xué)生的教與學(xué)過程以及學(xué)生之間的相互學(xué)習(xí)過程。在教學(xué)過程中,老師通過教學(xué)提升學(xué)生的知識水平。同時,學(xué)生之間能夠通過相互學(xué)習(xí)來提高自身的知識水平。教與學(xué)算法首先在文獻[12]中被提出,并且成功地應(yīng)用于求解優(yōu)化問題。教與學(xué)算法被提出以來已經(jīng)成功地運用于各種優(yōu)化問題之中。

本文針對混合流水車間調(diào)度問題,提出一種新的初始種群產(chǎn)生方法,并引入變異操作,并引入教與學(xué)優(yōu)化算法中適用于求解混合流水車間調(diào)度問題的老師階段和學(xué)生階段,從而提出一種改進的粒子群優(yōu)化算法(Improved Particle Swam Optimization Algorithm,IPSO)。通過仿真實驗驗證所提出算法能夠在合理的時間內(nèi)得到混合流水車間調(diào)度問題較優(yōu)的近似解。

2問題描述

具有m(m≥2)階段混合流水車間調(diào)度問題描述如下:生產(chǎn)系統(tǒng)所包括生產(chǎn)階段數(shù)為m(m≥2),各生產(chǎn)階段由多臺具有相同加工功能且性能不一定相同的并行機器組成。n個待加工工件在生產(chǎn)系統(tǒng)中按照相同的工序順序進行加工,并且不同工件在相同機器上的處理時間相互獨立。工件的第r(r=1,2,…,m)道工序只能由第r個生產(chǎn)階段的并行機器中的一臺機器處理。問題的優(yōu)化目標(biāo):對待處理工件排序并為各工件分配機器,使得生產(chǎn)系統(tǒng)處理完成所有工件的最大完成時間最小。該調(diào)度問題以文獻[13]所提出的三元組α|β|γ方式可以表示為F(k1,k2,…,km)‖Cmax。其中,第一部分F(k1,k2,…,km)表明該問題的機器環(huán)境是具有r個階段,每個階段具有ki(i=1,2,…,m)臺并行機器的混合流水車間;第二部分描述與任務(wù)相關(guān)的特征和約束,此處為空表示沒有相應(yīng)的約束限制;第三部分Cmax描述問題的優(yōu)化目標(biāo)為最小化最大完成時間。

基于以上描述,問題目標(biāo)為:確定負責(zé)處理所有待處理任務(wù)的各道工序的機器以及各臺機器處理任務(wù)的順序,即調(diào)度S,使得最大完成時間Cmax最小。由于每個工件工序順序相同,并且同一生產(chǎn)階段上的機器性能不一定相同。所以,Cmax為調(diào)度S中所有任務(wù)在第m個階段的完成時間的最大值,即maxCjm(j=1,2,…,n)。

3數(shù)學(xué)模型

假設(shè)生產(chǎn)系統(tǒng)需要處理n個工件,各工件的處理包括順序相同的m道工序。生產(chǎn)系統(tǒng)中第r個生產(chǎn)階段負責(zé)處理工件的第r道工序,并且該生產(chǎn)階段上機器數(shù)為kr。工件的每道工序由相應(yīng)生產(chǎn)階段上的一臺機器進行處理。

基于以上假設(shè)、問題描述以及相關(guān)符號說明,可以將F(k1,k2,…,km)‖Cmax混合流水車間調(diào)度問題轉(zhuǎn)換為如下整數(shù)規(guī)劃問題:

min max{Cjm}

(1)

(2)

(3)

(4)

(5)

xijhr,xi0hr,x0jhr,xjhr∈{0,1}

(6)

其中,i=1,2,…,n;j=1,2,…,n;h=1,…,kr;r=1,2,…,m。

整數(shù)規(guī)劃問題的目標(biāo)為min max{Cjm},即最小化最大完成時間。

約束(1)確保每個任務(wù)的每道工序只能由一臺機器進行處理,約束(2)確保每臺機器同一時刻只能處理一個工件,約束(3)確保任何一臺機器上處理的每一個任務(wù)最多只能有一個前趨任務(wù)、約束(4)用于計算任務(wù)的完成時間、約束(5)確保每個工件的工序順序相同;約束(6)為4個指示變量,每個變量取值涵義如下:

4IPSO算法

粒子群優(yōu)化算法模擬捕食行為的一種進化算法。其在執(zhí)行過程中保存了若干個可行解,每個可行解稱為一個粒子,若干個粒子構(gòu)成一個種群。算法在執(zhí)行的過程中,各粒子通過不斷調(diào)整各自的速度和位置信息向問題的最優(yōu)解移動。為防止粒子群算法在執(zhí)行過程中陷入局部最優(yōu)解,本文在標(biāo)準粒子群算法的基礎(chǔ)上引入變異操作。

4.1粒子的編碼

4.2種群初始化

在算法的第一次迭代之前,產(chǎn)生初始種群。本文所設(shè)計算法的初始種群由三部分組成。假設(shè)算種群規(guī)模為popsize。初始種群的第一部分為原問題轉(zhuǎn)化而成的Fm|(perm)|Cmax調(diào)度問題的解。第二部分為將原問題轉(zhuǎn)換為m-1個F2|(perm)|Cmax問題的解。第三部分的初始解以均勻分布隨機生成popsize-m個解。

初始種群的剩余部分以均勻分布隨機生成。

4.3粒子速度和位置的更新

粒子群算法在執(zhí)行過程中,各個粒子通過各自的局部最優(yōu)解以及全局最優(yōu)解更新自身的速度和位置信息,向問題的最優(yōu)解的位置靠近。傳統(tǒng)的粒子群算法中粒子的位置和速度更新公式如下

v(t+1)=ω×v(t)+c1×r1×(p(t)-x(t))

+c2×r2×(g(t)-x(t))x(t+1)

=x(t)+v(t+1)

其中,ω為慣性因子;v(t+1)為該粒子在算法的第t+1次迭代的速度;x(t+1)為粒子在算法的第t+1次的位置;c1為局部最優(yōu)解對速度更新影響的權(quán)重;c2為全局最優(yōu)解對速度更新影響的權(quán)重;r1、r2為0～1之間的隨機數(shù);p(t)為粒子在算法的第t次迭代的局部最優(yōu)解;g(t)為算法第t次迭代的全局最優(yōu)解。

但是由于F(k1,k2,k3,…,km)‖Cmax問題解的采用矩陣方式進行編碼,所以以上粒子速度和位置的更新方法已不適用。基于以上原因,本文采用另一種方式對粒子速度和位置進行更新。對粒子的速度隨機地進行交換方式或者插入方式的更新。將各粒子與全局最優(yōu)解或者局部最優(yōu)解進行交叉操作來更新粒子的位置信息。

粒子以交換方式或者插入方式進行速度更新的具體過程如圖1、圖2所示:在當(dāng)前解的矩陣中隨機選取兩行。粒子若以交換方式進行速度更新,則將隨機選取的兩行的內(nèi)容進行交換。粒子若以插入方式進行更新,則將其中一行插入到另外一行之前。

圖1　交換方式更新速度

圖2　插入方式更新速度

粒子以交叉操作進行位置更新的具體過程為:在當(dāng)前解中隨機選取兩個交叉點i,j(1≤i

4.4變異

為防種群中粒子的多樣性降低,從而造成算法的早熟收斂,對進入局部最優(yōu)的粒子進行變異操作。本文算法首先判斷在最近的若干次迭代中各個粒子的局部最優(yōu)解是否發(fā)生變化。若存在局部最優(yōu)解沒有變化的粒子,則認為算法陷入局部最優(yōu)解并對該粒子進行變異操作。

執(zhí)行變異操作的粒子隨機選擇某一工件,并以均勻概率分布將負責(zé)處理該工件各道工序的機器改為生產(chǎn)系統(tǒng)中相應(yīng)生產(chǎn)階段的其他機器。

4.5老師階段

教與學(xué)算法的老師階段中,老師通過教授學(xué)生知識來提高學(xué)生的知識水平或者成績,使學(xué)生的知識水平或成績接近于老師的知識水平或成績。算法在老師階段的執(zhí)行過程中如下:

1) 在粒子群中選擇若干適應(yīng)值最高的粒子作為老師,其他的粒子作為老師。

2) 被選為老師之外的每個粒子,隨機選擇一個老師,與其進行交叉操作。采用交換方式進行交叉操作。

3) 若交叉結(jié)果對應(yīng)的適應(yīng)值優(yōu)于交叉之前的適應(yīng)值,那么更新當(dāng)前粒子為交叉所得的結(jié)果。

4.6學(xué)生階段

該階段的執(zhí)行過程中,每個學(xué)生通過同學(xué)之間的相互學(xué)習(xí)來提高自身的知識水平或者成績。算法在學(xué)生階段的執(zhí)行過程:每個學(xué)生選擇高于其適應(yīng)值的學(xué)生進行交叉操作,并更新當(dāng)前學(xué)生粒子為交叉結(jié)果。

4.7終止條件

當(dāng)算法迭代次數(shù)達到指定值后,算法停止運算,并輸出結(jié)果。

4.8IPSO算法的具體步驟

IPSO算法:

Input:P,PT//PT為各個生產(chǎn)階段包含的機器的數(shù)量

Output:S,Cmax

Begin:

Step1初始化算法最大迭代次數(shù)eranum、慣性系數(shù)InertiaCoef、學(xué)習(xí)系數(shù)LearnCoef、種群規(guī)模popsize,目標(biāo)值未改變的次數(shù)unchangedTimes等參數(shù)。

Step2產(chǎn)生粒子數(shù)量為popsize的初始種群。在3維矩陣Schedule中記錄初始種群中每個粒子的編碼矩陣。在矩陣ValForGB中記錄種群的全局最優(yōu)值,并用矩陣GB記錄全局最優(yōu)值對應(yīng)的矩陣編碼。在矩陣ValForPB中記錄各粒子的局部最優(yōu)值,并在矩陣PB中記錄局部最優(yōu)值對應(yīng)的矩陣編碼。

Step3如果算法迭代次數(shù)小于最大遺傳代數(shù)eranum,則轉(zhuǎn)Step4,否則,轉(zhuǎn)Step7

Step4種群Schedule中每個粒子以概率InertiaCoef更新速度,以概率LearnCoef更新根據(jù)局部最優(yōu)值ValForPB更新位置,或者根據(jù)全局最優(yōu)值ValForGB更新位置信息。計算更新后各個粒子對應(yīng)的目標(biāo)函數(shù)值,并將計算結(jié)果存入矩陣ValForSchedule中。

Step5如果ValForSchedule中最小值小于ValForGB中的值,則更新ValForGB為ValForSchedule中的最小值,同時更新GB為ValForSchedule中的最小值對應(yīng)的編碼矩陣;否則,不更新GB和ValForGB。如果粒子更新后對應(yīng)的目標(biāo)函數(shù)值小于其局部最優(yōu)值,則更新該粒子局部最優(yōu)值ValForPB為當(dāng)前粒子對應(yīng)的目標(biāo)函數(shù)值,同時更新PB為當(dāng)前粒子對應(yīng)的編碼矩陣。

Step6在Schedule中選擇對應(yīng)ValForSchedule值最小的若干個粒子作為老師teacherSchedule。

Step7對于每個粒子,在teacherSchedule中隨機選擇一個粒子作為老師,并與其進行交叉操作。若交叉結(jié)果的適應(yīng)值優(yōu)于當(dāng)前粒子的適應(yīng)值,則更新當(dāng)前粒子為交叉結(jié)果。

Step8對于每個粒子,隨機選擇種群中的另外一個適應(yīng)值更高的粒子,并與其進行交叉操作。更新當(dāng)前粒子為交叉操作所得的結(jié)果。

Step9計算各個粒子對應(yīng)目標(biāo)函數(shù)值連續(xù)未改變的算法迭代次數(shù)。若未改變的算法迭代次數(shù)超過unchangedTimes的值,則對該粒子進行變異操作;否則,不進行變異。轉(zhuǎn)Step3。

Step10輸出GB和ValForGB,算法結(jié)束運行。

End

5實驗設(shè)計與結(jié)果

5.1實驗設(shè)計

本文提出的算法在Matlab 2014環(huán)境下實現(xiàn),并運行于在CPU為Inter Core 3.20GHz的計算機。為確定算法中種群規(guī)模、學(xué)習(xí)因子、慣性因子等參數(shù)的取值,利用文獻[14]中實例的數(shù)據(jù)設(shè)計因子數(shù)為3,因子取值水平數(shù)為4,參數(shù)組合數(shù)為16,即規(guī)模為L16(43)的正交試驗。正交試驗中各個任務(wù)的加工時間如表1所示。其中每個參數(shù)取值即正交試驗的因子取值包括三個水平,如表2所示。每種參數(shù)組合各進行30次試驗,并計算目標(biāo)函數(shù)的平均值。算法最大迭代次數(shù)為1000次。正交試驗的結(jié)果如表3所示。

表1　正交試驗中各個任務(wù)的加工時間

表2　算法參數(shù)取值水平

表3　正交試驗具體結(jié)果

表4　各參數(shù)取值水平的影響

由正交試驗的具體結(jié)果可得出種群規(guī)模、學(xué)習(xí)因子、慣性因子這三個參數(shù)的不同取值水平對算法的影響,如表4所示。通過觀察各參數(shù)不同取值水平對目標(biāo)值的影響,發(fā)現(xiàn)當(dāng)種群規(guī)模、學(xué)習(xí)因子、慣性因子取值水平分別為150、0.2、0.5時,所對應(yīng)的目標(biāo)函數(shù)值最小。因此,設(shè)定算法的種群規(guī)模為150,學(xué)習(xí)因子為0.2,慣性因子為0.5。

本文選取文獻[15]和文獻[16]的不同規(guī)模的測試數(shù)據(jù)驗證本文提出算法的有效性。第1組實驗數(shù)據(jù)包括12個任務(wù),4個生產(chǎn)階段。其中,每個生產(chǎn)階段分別包括3臺、3臺、2臺、2臺并行機器。各個任務(wù)在每道工序中的每臺機器上的加工時間如表5所示。第2組實驗數(shù)據(jù)的任務(wù)數(shù)為12,生產(chǎn)階段數(shù)為3,機器數(shù)為8,。其中第1個生產(chǎn)階段包括3臺機器,第2個生產(chǎn)階段的包括3臺機器,第三個生產(chǎn)階段包括2臺機器。各個任務(wù)在每臺機器上處理所需時間如表6所示。

表5　第1組實驗任務(wù)處理時間數(shù)據(jù)

表6　第2組實驗任務(wù)處理時間數(shù)據(jù)

5.2實驗結(jié)果與分析

利用所提出算法求解分別第1組實驗實例和第2組實驗實例各10次,實驗結(jié)果如表7和表8所示。

表7　第1組實驗結(jié)果

表8　第2組實驗結(jié)果比較

本文提出算法10次運算第1組實驗實例的最優(yōu)解為302,最差解為320。而文獻[15]所提出方法所得最優(yōu)結(jié)果為347?；谝陨戏治?本文提出算法優(yōu)于文獻[15]提出的方法。

通過對表8中數(shù)據(jù)的分析可得,文獻[16]的算法最優(yōu)解為14,本文提出算法的最優(yōu)解為12。并且本文所提算法每次運算結(jié)果均優(yōu)于文獻[16]中算法的結(jié)果。因此,所提出IPSO算法優(yōu)于文獻[16]所提出的方法。

6結(jié)語

本文在研究混合流水車間調(diào)度問題的基礎(chǔ)上,將粒子群優(yōu)化算法和教育學(xué)優(yōu)化算法相結(jié)合,提出了用于求解該類問題的IPSO算法。初始解產(chǎn)生過程中,將原問題轉(zhuǎn)換為Fm|(perm)|Cmax以及多個F2|(perm)|Cmax流水車間調(diào)度問題,并將所轉(zhuǎn)換問題的解作為初始解的一部分。通過正交試驗設(shè)置合適的算法參數(shù)。設(shè)計仿真實驗并與已有的文獻中計算結(jié)果進行比較。仿真實驗的結(jié)果表明,本文所提出的IPSO算法能求得混合流水車間相對較優(yōu)的近似解。

下一步的研究方向:改進所提出的算法或提出更為高效的算法用于求解具有隨機故障的混合流水車間調(diào)度問題。

參 考 文 獻

[1] Kurz M E, Askin R G. Scheduling flexible flow lines with sequence-dependent setup times[J]. European Journal of Operational Research,2004,159(1):66-82.

[2] Wilson J M. Henry Ford vs. assembly line balancing[J]. International Journal of Production Research,2014,52(3):757-765.

[3] Ercan M F, Fung Y F. Real-time image interpretation on a multi-layer architecture[C]//TENCON 99. Proceedings of the IEEE Region 10 Conference. IEEE,1999,2:1303-1306.

[4] Hoogeveen J A, Lenstra J K, Veltman B. Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard[J]. European Journal of Operational Research,1996,89(1):172-175.

[5] Wittrock R J. Scheduling algorithms for flexible flow lines[J]. IBM Journal of Research and Development,1985,29(4):401-412.

[6] Sioud A, Gagné C, Gravel M. An ant colony optimization for solving a hybrid flexible flowshop[C]//Proceedings of the 2014 conference companion on Genetic and evolutionary computation companion. ACM,2014:17-18.

[7] Mirsanei H S, Zandieh M, Moayed M J, et al. A simulated annealing algorithm approach to hybrid flow shop scheduling with sequence-dependent setup times[J]. Journal of Intelligent Manufacturing,2011,22(6):965-978.

[8] Shahvari O, Salmasi N, Logendran R, et al. An efficient tabu search algorithm for flexible flow shop sequence-dependent group scheduling problems[J]. International Journal of Production Research,2012,50(15):4237-4254.

[9] Niu Q, Zhou T, Ma S. A Quantum-Inspired Immune Algorithm for Hybrid Flow Shop with Makespan Criterion[J]. J. UCS,2009,15(4):765-785.

[10] Janiak A, Kozan E, Lichtenstein M, et al. Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion[J]. International Journal of Production Economics,2007,105(2):407-424.

[11] Eberhart R C, Kennedy J. A new optimizer using particle swarm theory[C]//Proceedings of the sixth international symposium on micro machine and human science,1995,1:39-43.

[12] Rao R V, Savsani V J, Vakharia D P. Teaching-learning-based optimization: a novel method for constrained mechanical design optimization problems[J]. Computer-Aided Design,2011,43(3):303-315.

[13] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Annals of Discrete Mathematics,1979,5:287-326.

[14] 周輝仁,唐萬生,魏穎輝.柔性Flow Shop調(diào)度的遺傳算法優(yōu)化[J].計算機工程與應(yīng)用,2009,45(30):224-226.

ZHOU Renhui, TANG Wansheng, WEI Yinghui. Genetic algorithm optimization of flexible Flow Shop scheduling[J]. Computer Engineering and Applications,2009,45(30):224-226.

[15] 崔建雙,李鐵克,張文新.混合流水車間調(diào)度模型及其遺傳算法[J].北京科技大學(xué)學(xué)報,2005,27(5):623-626.

CUI Jianshuang, LI Tieke, ZHANG Wenxin. Hybrid flow shop scheduling model and genetic algorithm[J]. Journal of University of Science and Technology Beijing,2005,27(5):623-626.

[16] 董婷婷.基于遺傳算法的混合流水車間調(diào)度問題研究[D].阜新:遼寧工程技術(shù)大學(xué),2008.DONG Tingting. The Study Based on the Genetic Algorithm of Hybrid Flow Shop Scheduling Problem[D]. Fuxin: Liaoning Technical University,2008.

Improved Particle Swam Optimization Algorithm for Hybrid Flow Shop Scheduling

LI JieREN WeixiangQIN Yongbin

(College of Computer Science and Technology, Guizhou University, Guiyang550025)

AbstractFor the hybrid flow shop scheduling problem which aims to minimize makespan, an integer program model is established. The improved particle swarm optimization algorithm with a new method of generating initial population, which is based on the study of classic particle swarm optimization algorithm, is presented. The new method transforms the hybrid flow shop scheduling problem into m-machine permutation flow shop scheduling problem. Parts of initial solutions consist of the transformed scheduling problem solution. The teacher phase and student phase of TLBO for solving hybrid flow shop scheduling problem is introduced into the proposed algorithm. The phenomenon that the particle converging on local optimum is avoided by mutation operation. Suitable parameters are suggested by perpendicular experiments on influence of parameter setting. Simulation experiments and comparisons with existing algorithms show the presented algorithm is effective.

Key Wordsflow shop, particle swarm optimization, teaching-learning based optimization, improved particle swarm optical algorithm, makespan

收稿日期:2015年12月4日,修回日期:2016年1月19日

基金項目:國家自然科學(xué)基金(編號:61262006,61540050);貴州省重大應(yīng)用基礎(chǔ)研究項目(編號:黔科合JZ字[2014]2001);貴州省科技廳聯(lián)合基金(編號:黔科合LH字[2014]7636號);貴州大學(xué)研究生創(chuàng)新基金(編號:研理工2015012)資助。

作者簡介:李解,女,碩士,研究方向:算法設(shè)計與分析。任魏翔,男,碩士,研究方向:算法設(shè)計與分析。秦永彬,男,副教授,碩士生導(dǎo)師,研究方向:智慧計算與智能計算、大數(shù)據(jù)管理與應(yīng)用等。

中圖分類號TP312

DOI:10.3969/j.issn.1672-9722.2016.06.001