范雅男，逄煥利

(長春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長春 130102)

0 引 言

車間調(diào)度問題[1](Job Shop scheduling， JSP)是對資源和時(shí)間路徑進(jìn)行整合分配達(dá)到實(shí)際生產(chǎn)需求的過程。流水車間調(diào)度問題[2]是生產(chǎn)制造業(yè)中極其重要的規(guī)劃問題，一般該類問題的研究任務(wù)數(shù)都需要大于3，被證明是NP-hard問題。在智能生產(chǎn)制造業(yè)高速發(fā)展的背景下，車間的柔性生產(chǎn)越來越受到重視，柔性流水車間調(diào)度問題[3](Flexible Flow Shop scheduling Problem， FFSP)已成為實(shí)際生產(chǎn)調(diào)度問題研究領(lǐng)域的新熱點(diǎn)，對提高企業(yè)生產(chǎn)效率具有重要意義。

粒子群算法(Particle Swarm Optimization， PSO)[4-5]的突出優(yōu)點(diǎn)在于容易實(shí)現(xiàn)，收斂效率較高，涉及到的可調(diào)整參數(shù)比較少。它可以利用實(shí)數(shù)進(jìn)行編碼，算法結(jié)構(gòu)不復(fù)雜的同時(shí)又適用于多個(gè)領(lǐng)域，既適合做理論研究，也能應(yīng)用到具體的工程問題中。因此，PSO算法得到了各領(lǐng)域研究者的廣泛關(guān)注，在被提出后的短短幾年內(nèi)便產(chǎn)生了許多科研成果，成為熱門的研究方向，并且被應(yīng)用到許多工程領(lǐng)域。

目前對FFSP問題的研究主要集中在采用精確算法、元啟發(fā)式算法[6]、啟發(fā)式算法[7]方向上。如Ihong Kuo等[8]將全新的編碼方式和個(gè)體更新方案融入PSO算法中以求解FFSP問題。 Marichelvam M K等[9]對布谷鳥搜索算法進(jìn)行優(yōu)化，將改進(jìn)的算法應(yīng)用于HFSP問題的求解。田野等[10]將多種元啟發(fā)式方法混合后用于PFSP問題的求解。裴小兵等[11]提出的一種基于NEH的混合螢火蟲算法在解決含有多個(gè)目標(biāo)的置換流水車間調(diào)度問題時(shí)效果良好。景會(huì)成等[12]針對搜索效率低、容易收斂于局部最優(yōu)解等問題，采用模擬退火算法、粒子群算法、遺傳算法三種算法融合的方式對FSSP問題進(jìn)行求解。

文中將禁忌策略和粒子群算法相結(jié)合形成一種新的優(yōu)化算法，并將其應(yīng)用于FFSP問題的求解。采用NEH算法產(chǎn)生初始種群，并引入非線性自適應(yīng)慣性權(quán)重因子和擾動(dòng)因子。最終通過仿真對比實(shí)驗(yàn)的分析結(jié)果驗(yàn)證了所提算法的有效性。

1 問題描述

柔性流水車間調(diào)度問題可以描述為：n個(gè)待加工工件Ji(i=1，2，…，n)在m臺機(jī)器Mk(k=1，2，…，m)上進(jìn)行加工，每個(gè)工件包括一道或多道工序Oij(j=1，2，…，Pi)。任何工件的每次操作都必須遵循相同的機(jī)器順序。FFSP存在以下假設(shè)：開始時(shí)刻所有的機(jī)器都可以執(zhí)行加工操作；各工件的每個(gè)操作可以在相應(yīng)階段上選擇任意一臺并行處理機(jī)進(jìn)行加工；工件中的任一操作每次只能在一臺機(jī)器上執(zhí)行；每臺機(jī)器在任何作業(yè)上一次只能執(zhí)行一次操作；機(jī)器上的操作一旦開始，就不得終止。文中涉及的模型參數(shù)見表1。

表1 模型參數(shù)表

問題目標(biāo)是調(diào)配工件的加工處理順序以及機(jī)器調(diào)度方案，使得最大完成時(shí)間指標(biāo)達(dá)到極小。因此該問題的數(shù)學(xué)公式描述如下：

minCmax=maxCmin;

(1)

Cijk=Sijk+tijk;

(2)

Sijk=max{S(i-1)(j-1)k+t(i-1)(j-1)k,Ci(j-1)(k-1)}；

(3)

Ck=Ci′j′k′。

(4)

式(1)為提出模型的目標(biāo)函數(shù)；式(2)表示工件操作完成時(shí)間由開始處理時(shí)間和處理過程花費(fèi)時(shí)間的總和；式(3)表示某工件上一個(gè)操作的完成時(shí)間，該機(jī)器上一次操作的處理完成時(shí)間決定了該工件開始處理的時(shí)間；式(4)表示某機(jī)器的處理完成時(shí)間為它上面最后一個(gè)操作的處理完工時(shí)間。

2 改進(jìn)粒子群算法設(shè)計(jì)

2.1 編碼與解碼

采用基于工序和機(jī)器的編碼方式。假設(shè)一個(gè)3×3問題解決方案是{1，3，2，1，2，1，2，3，2，3，1，3，2，1，2，1}，前半部分用來判斷各工序的先后加工順序，后半部分用來選擇各工件操作的加工機(jī)器。{1，3，2，1，2，1，2，3}為工序調(diào)度，其中最前面的 “1”代表工件1的第一道工序O11，第二個(gè)“1”代表工件1的第二道工序O12，依此類推。{2，3，1，3，2，1，2，1}為機(jī)器分配部分與工序調(diào)度相匹配，其中“2”代表操作O11被分配到機(jī)器2上進(jìn)行處理，“3”代表操作O31被分配到機(jī)器3上進(jìn)行處理，依此類推。解碼為編碼的逆過程可以確定各工件在機(jī)器上的加工順序。

2.2 種群初始化

傳統(tǒng)粒子群算法對種群進(jìn)行初始化時(shí)采用隨機(jī)策略，但隨機(jī)策略面對大規(guī)模實(shí)際組合優(yōu)化問題時(shí)效果不好，并且會(huì)使初始種群中粒子的質(zhì)量降低。因此，文中采用NEH啟發(fā)式算法生成初始種群，該算法假定在所有加工機(jī)器上總加工時(shí)間大的工件會(huì)獲得更高的優(yōu)先權(quán)。具體步驟為：

1)n個(gè)工件在加工機(jī)器上的加工時(shí)間總長按照由大到小的順序進(jìn)行排列;

2)取前兩個(gè)工件調(diào)度，使其最大流程時(shí)間達(dá)到最小;

3)從k=3到n,將第k個(gè)工件插入到k個(gè)可能的位置,求得最大流程時(shí)間。

2.3 粒子尋優(yōu)操作

粒子速度和位置更新公式為：

vij(t+1)=ωvij(t)+

c1r1(pbestij(t)-xij(t))+

c2r2(gbestij(t)-xij(t))+d,

(5)

xij(t+1)=xij(t)+vij(t+1),

(6)

式中:vij(t)----粒子速度;

xij(t)----粒子位置；

pbestij(t)----粒子的個(gè)體最優(yōu)位置;

gbestij(t)----粒子的群體最優(yōu)位置；

ω----慣性權(quán)重系數(shù)；

d----擾動(dòng)因子；

c1、c2----學(xué)習(xí)因子；

r1、r2----(0，1)之間的隨機(jī)數(shù)。

2.4 自適應(yīng)慣性權(quán)重系數(shù)

在PSO算法中慣性權(quán)重至關(guān)重要，它擁有平衡局部勘探和全局勘探的能力。因此，文中采用非線性的、自適應(yīng)的慣性因子調(diào)整方式，迭代開始階段算法在解空間內(nèi)的尋優(yōu)能力增強(qiáng)，不容易陷入局部極值，加快算法后期的收斂速度。

(7)

k=rand+Ε(0.5),

(8)

式中:t----當(dāng)前迭代次數(shù);

MaxDT----算法允許的最大迭代次數(shù);

Ε(0.5)----平均值為0.5的指數(shù)分布;

rand----(0，1)之間的隨機(jī)數(shù)。

ωstart通常取0.9，這使得在迭代初期算法擁有比較好的勘探能力，能夠擴(kuò)大搜索范圍。ωend一般取0.4，隨著迭代次數(shù)的不斷增加，算法的開發(fā)能力逐步增強(qiáng)，這促使粒子加速向全局最佳值逼近。慣性權(quán)重ω的曲線如圖1所示。

圖1 慣性權(quán)重ω的曲線

2.5 擾動(dòng)因子

經(jīng)典PSO算法在尋優(yōu)階段容易陷入局部極值，為此在原速度更新公式中加入了擾動(dòng)因子d，進(jìn)而促使粒子在解空間中繼續(xù)進(jìn)行搜索。將擾動(dòng)因子d設(shè)置為一個(gè)二進(jìn)制變量，它取0的概率比較大。當(dāng)粒子在種群中呈聚集狀態(tài)時(shí)，擾動(dòng)因子可以將其打散，防止算法收斂于局部最優(yōu)值；當(dāng)種群中的粒子呈分散狀態(tài)時(shí)，算法受擾動(dòng)因子的影響較小，可以忽略。

2.6 禁忌搜索

禁忌搜索算法[13](Tabu Search， TS)對局部搜索算法的優(yōu)化，它能夠避免傳統(tǒng)的局部搜索算法因粒子重復(fù)搜索固定區(qū)域(方向)而造成粒子收斂于局部極小值。通過建立禁忌表來記錄被禁止的局部極小點(diǎn)，使粒子更新時(shí)繞開這些點(diǎn)。并通過破禁準(zhǔn)則釋放一些在禁忌表中的點(diǎn)，保證多樣化、有效地探索。

文中引入一種基于位置相似度的禁忌搜索策略[14]，并將它與粒子群算法相結(jié)合。對于N維空間中有位置x1=(x11，x12，…，x1N)和位置x2=(x21，x22，…，x2N)，那么位置相似度可表示為λ=N′/N，其中N′為位置x1和位置x2中可行解數(shù)值相同的維數(shù)。首先建立一個(gè)長度為l的禁忌表，用以記錄粒子在搜索過程中所到達(dá)的位置。并根據(jù)位置相似度閾值更新禁忌表，規(guī)則如下：每當(dāng)粒子抵達(dá)全新的位置時(shí)，粒子都與禁忌表中的每個(gè)記錄做λ計(jì)算，超過相似度閾值的位置則被放棄，而小于閾值的粒子所在的位置將加入到當(dāng)前迭代的候選解隊(duì)列中，計(jì)算適應(yīng)度值并更新禁忌表。

2.7 算法流程

采用TIPSO求解FFSP的詳細(xì)流程如下：

1)設(shè)置算法的基本參數(shù)。給定問題規(guī)模，迭代次數(shù)M，學(xué)習(xí)因子c1和c2，種群規(guī)模N，禁忌表長度。

2)種群初始化，禁忌表初始化。結(jié)合NEH算法初始化種群。

3)判斷粒子是否在禁忌表中。若在禁忌表中則執(zhí)行5)，否則執(zhí)行4)。

4)更新禁忌表，計(jì)算適應(yīng)度值,并更新個(gè)體和種群最優(yōu)(將目標(biāo)函數(shù)作為適應(yīng)度評價(jià)指標(biāo))。

5)利用式(5)、式(6)指導(dǎo)種群中粒子速度以及位置更新。

6)判斷是否達(dá)到終止標(biāo)準(zhǔn)。若達(dá)到條件，則將最優(yōu)位置輸出；若不滿足,則重新執(zhí)行3)。

改進(jìn)粒子群算法流程如圖2所示。

圖2 改進(jìn)粒子群算法流程

3 仿真結(jié)果與分析

為驗(yàn)證文中提出的改進(jìn)算法有效性，以Matlab2016a為開發(fā)環(huán)境，分別使用標(biāo)準(zhǔn)粒子群算法、改進(jìn)型算法[14]和文中提出的算法在 LA01[15]、FT06[16]、FT10[16]三個(gè)不同規(guī)模的問題進(jìn)行了實(shí)驗(yàn)仿真。

算法參數(shù)設(shè)置如下：粒子個(gè)數(shù)N=50，LA01、FT06問題規(guī)模相對來說比較小，所以最大迭代次數(shù)設(shè)置為MaxIter=500，F(xiàn)T10問題復(fù)雜規(guī)模大，其最大迭代次數(shù)設(shè)置為MaxIter=1 000，學(xué)習(xí)因子c1=c2=2，ωmin=0.4，ωmax=0.9，禁忌表長度l=2，禁忌閾值η1=0.85，η2=0.95。

TIPSO算法在FT06問題上的最優(yōu)調(diào)度方案如圖3所示。

圖3 最優(yōu)甘特圖

由圖3可知,最短完工時(shí)間為47 s。

標(biāo)準(zhǔn)粒子群算法、改進(jìn)型PSO算法[14]和禁忌粒子群優(yōu)化算法(TIPSO)求解FT06基準(zhǔn)算例、LA01基準(zhǔn)算例、FT10基準(zhǔn)算例的收斂結(jié)果對比圖，分別如圖4～圖6所示。

圖4 收斂速度對比圖(FT06)

圖5 收斂速度對比圖(LA01)

圖6 收斂速度對比圖(FT10)

由上圖可知，TIPSO可以求出FT06算例的最優(yōu)解47、LA01算例的最優(yōu)解453和FT10算例的最優(yōu)解706，其他兩種算法均找不到最優(yōu)解。在搜索后期TIPSO得到的種群最大流程時(shí)間比較短，說明TIPSO算法具有較優(yōu)的收斂性能，而且TIPSO算法在面對大規(guī)模問題時(shí)表現(xiàn)依然良好。這是因?yàn)門IPSO 算法結(jié)合禁忌搜索策略對種群的初始化、權(quán)重因子進(jìn)行了改進(jìn)，保證了算法初始種群的多樣性，更接近全局最優(yōu)解，并且收斂效率也更好，而擾動(dòng)因子的引入能夠幫助跳出局部最優(yōu)解，繼續(xù)在解空間內(nèi)進(jìn)行搜索。

4 結(jié) 語

設(shè)計(jì)了一種禁忌粒子群優(yōu)化算法，在求解FFSP問題時(shí)表現(xiàn)出良好的性能。將基于位置相似度的禁忌策略和粒子群算法結(jié)合起來，自適應(yīng)慣性權(quán)重因子和擾動(dòng)因子的加入，可以有效地避免粒子過早收斂的情況，幫助粒子提高其全局搜索能力，同時(shí)將NEH 啟發(fā)式算法引入種群的初始化中，提高了粒子種群的多樣性，可以幫助算法在較短時(shí)間內(nèi)收斂于最優(yōu)解。最后通過仿真實(shí)驗(yàn)證明了該算法的可行性與有效性。