秦志偉，黃友銳，徐善永

(安徽理工大學(xué)電氣與信息工程學(xué)院，安徽 淮南 232001)

置換流水車間調(diào)度問題(Permutation Flow Shop Scheduling Problem，PFSP) 是在流水車間調(diào)度的特例，即增加了每臺機器上所有作業(yè)的加工順序都相同這一約束。但當(dāng)機器數(shù)大于等于3時，置換流水車間調(diào)度問題還是屬于典型的 NP 問題[1]117。該調(diào)度問題被廣泛用于指導(dǎo)實際生產(chǎn)，可以有效提高企業(yè)生產(chǎn)效率與設(shè)備利用率。因此研究高效的求解算法具有重要的理論和工程意義。

粒子群算法[2](Particle Swarm Optimization，PSO)因為其通用性好、參數(shù)少、易實現(xiàn)等優(yōu)點，被廣泛應(yīng)用于模式識別、神經(jīng)網(wǎng)絡(luò)、生產(chǎn)調(diào)度等領(lǐng)域，PSO求解流水調(diào)度問題也成了研究的熱點。文獻(xiàn)[3]設(shè)計了一個基于隨機鍵最小位置值(Smallest position value，SPV)的規(guī)則，使得算法中的粒子由連續(xù)空間映射到離散空間。文獻(xiàn)[4]提出了一種混合粒子群算法來求解最小化中間存儲有限的調(diào)度問題的makespan，并在初始化中使用了啟發(fā)式規(guī)則，還加入了局部搜索以及模擬退火的思想，通過仿真表明此算法的有效性。文獻(xiàn)[5]將啟發(fā)式信息和激素調(diào)節(jié)機制結(jié)合，對粒子飛行方程進(jìn)行改進(jìn)，為解決PFSP提供了一個新的思路。文獻(xiàn)[6]將粒子群算法與迭代貪心算法混合，用來求解PFSP中的makespan，取得了很好的效果。文獻(xiàn)[7]將假設(shè)檢驗、模擬退火結(jié)合粒子群，用于解決分布式置換流水車間調(diào)度。文獻(xiàn)[8]提出一種基于Taguchi的粒子群算法并將其用于多目標(biāo)置換車間調(diào)度。

針對粒子之間信息交流不足、高維求解困難等的缺點，本文在協(xié)同粒子群算法(Cooperative Particle Swarm Optimization，CPSO)[9]的基礎(chǔ)上，將一種多粒子群協(xié)同學(xué)習(xí)算法(MPSO-CL)用于置換流水車間調(diào)度。該算法引入了精英策略，通過不同規(guī)模Taillard系列基準(zhǔn)實例的仿真分析，驗證該算法在求解PFSP的有效性與可行性。

1 相關(guān)問題數(shù)學(xué)描述

1.1 PFSP數(shù)學(xué)描述

PFSP的總體目標(biāo)就是合理地安排工件在每臺機器上的加工順序，使所有工件最大完工時間(Makespan)最短。在研究該類調(diào)度問題時經(jīng)常作以下假設(shè)：n個工件以相同的順序在m臺機器上加工；每臺機器上所有工件的順序是一樣的；每個工件在同一時刻只能在一臺機器上進(jìn)行加工；每臺機器同一時刻只能處理一個工件；工件在上一個機器加工完成后，立即送到下一臺機器加工；每臺機器加工工件的過程不允許中斷[10]。

令π={π1，π2，…，πn}為一個排序，Pπ，j和Cπ，j分別為πi在機器j上的加工時間和完成時間，則PFSP數(shù)學(xué)描述如下

min∶Cmax(π)

(1)

(2)

式中：Cmax(π)為最大完成時間。

1.2 協(xié)同粒子群算法數(shù)學(xué)描述

(3)

xi=xi+vi

(4)

式中：w(w≥0)為慣性權(quán)重，c1和c2為正的學(xué)習(xí)因子，r1、r2是[0，1]區(qū)間內(nèi)均勻分布的隨機數(shù)。

第j個子群粒子個體最優(yōu)位置更新公式如下

(1≤j≤k) (5)

第j個子群的全局最優(yōu)位置更新公式如下

(1≤i≤s，1≤j≤k) (6)

2 多粒子群協(xié)同學(xué)習(xí)算法

2.1 多粒子群協(xié)同學(xué)習(xí)算法模型

本文在文獻(xiàn)[11]的模型基礎(chǔ)上重新定義了學(xué)習(xí)交流機制，引入了綜合學(xué)習(xí)策略和精英策略，提出了一種經(jīng)驗指導(dǎo)的精英學(xué)習(xí)策略，其框架如圖1所示。

圖1 多粒子群協(xié)同學(xué)習(xí)算法模型

定義1精英庫種群Z0(t)=(P1Y1，P1Y2，…，PjYi)，PjYi表示第j個子種群的第i個代表。精英庫種群Z0是由按照Pareto 的精英理論中的 80/20 法則從普通種群中篩選組建成的，它保存了各普通種群在進(jìn)化過程中產(chǎn)生的優(yōu)良基因。利用綜合學(xué)習(xí)策略使精英庫種群內(nèi)部個體相互學(xué)習(xí)，保持其種群多樣性，防止出現(xiàn)早熟收斂現(xiàn)象。

定義2普通種群Z(t)=(P1，P2，…，PI)，其中I∈Z+，其中ZI(t)表示第I個子種群。在進(jìn)化過程，每一個普通種群中的個體都有概率向精英中的最好個體學(xué)習(xí)，否則只能學(xué)習(xí)自己的歷史經(jīng)驗。同時隔代引進(jìn)若干個精英庫種群的個體指導(dǎo)普通種群進(jìn)化，同時淘汰其適應(yīng)度最差的個體，實現(xiàn)了種群間的信息共享交流。

2.2 改進(jìn)的綜合學(xué)習(xí)策略

精英庫種群采用綜合學(xué)習(xí)粒子群算法(CLPSO)[12]更新，其速度更新公式如下

vid=wvid+c3r3(Pbestfi(d)-xid)

(7)

式中：fi=[fi(1)，fi(2)，…，fi(D)]表示粒子i學(xué)習(xí)的Pbest向量。通過選擇概率Pc來決定精英是否需要綜合學(xué)習(xí)，在[0，1]之間產(chǎn)生一個隨機數(shù)k1，當(dāng)k1

CLPSO算法由于速度更新中采用的是較優(yōu)的粒子，算法后期收斂速度變慢，甚至停滯。

所以在速度公式上加入柯西擾動項

vid=wvid+c3r3(Pbestfi(d)-xid)+

(8)

同時設(shè)置并設(shè)置進(jìn)化停滯閥值Tn

(9)

每當(dāng)CLPSO更新最優(yōu)不變，flag就會加1，當(dāng)達(dá)到預(yù)設(shè)閥值，就會產(chǎn)生一個擾動，使精英庫粒子擺脫停滯狀態(tài)，在新的鄰域里更好地尋優(yōu)。

2.3 經(jīng)驗指導(dǎo)的精英學(xué)習(xí)

本文在文獻(xiàn)[13]468的基礎(chǔ)上，提出了一種基于經(jīng)驗指導(dǎo)的精英學(xué)習(xí)策略來對普通種群中的每個子群個體極值進(jìn)行局部搜索。當(dāng)普通種群每次迭代更新個體極值時， 通過Pe進(jìn)行決策，當(dāng)大于Pe時，該子群將由精英庫種群的歷史最優(yōu)pbeste1來指導(dǎo)學(xué)習(xí)搜索，否則通過每次迭代更新歷史最優(yōu)pbest1、次優(yōu)pbest2的差分來指導(dǎo)個體極值來指導(dǎo)學(xué)習(xí)搜索。歷史經(jīng)驗指導(dǎo)的學(xué)習(xí)公式如下

(10)

式中：r為[-1， 1]之間隨機數(shù)，控制局部搜索的方向，d(t)為第t代時的縮放因子，控制局部搜索范圍。

進(jìn)化前期，pbest1距最優(yōu)解一般比較遠(yuǎn)，這時較大的d(t)進(jìn)行粗粒度局部搜索， 加快收斂速度； 進(jìn)化后期， pbest1距最優(yōu)解一般比較近， 這時通過較小的d(t)進(jìn)行細(xì)粒度搜索， 可以提高解質(zhì)量。 d(t)的設(shè)置給出一種非線性遞減的取值。

d(t)=d0·exp(-t/(Gennum-t))

(11)

最后對于學(xué)習(xí)后的結(jié)果進(jìn)行適應(yīng)度評價，若適應(yīng)度好于原有的，則替換原有的最優(yōu)極值。

(12)

2.4 隔代精英遷移

普通子種群內(nèi)部進(jìn)化過程中，每隔兩代需要進(jìn)行一次評價，若每一個子群的全局最優(yōu)個體的適應(yīng)度小于等于精英庫種群的全局最優(yōu)時，則從精英庫種群中隨機引入個體并淘汰該種群中適應(yīng)度最差個體。

通過隔代精英遷移，普通種群既傳承了精英庫種群優(yōu)良的基因模式，加快了其向最優(yōu)解的收斂性能，又增強了群體的多樣性，提高了尋優(yōu)能力。

2.5 粒子的編碼與解碼

本文采用了 SPV 法[1]118來對工件的加工順序進(jìn)行提取。粒子的每一維表示一個工件，所得到的隨機數(shù)表示粒子每一維的位置，對粒子每一維的位置進(jìn)行升序排序，然后將粒子排序好的新位置與原來維數(shù)進(jìn)行映射。

3 算法步驟

Step 1 初始化。設(shè)置種群規(guī)模psize、迭代次數(shù)Gennum、慣性權(quán)重w、學(xué)習(xí)因子c1、c2，綜合學(xué)習(xí)概率Pc、精英學(xué)習(xí)概率Pe、縮放因子初值d0。

Step 2 按照spv規(guī)則，獲取每維粒子對應(yīng)的工件加工序列，并由加工序列對其調(diào)度目標(biāo)進(jìn)行評價。

Step 3 根據(jù)Pareto 的精英理論中的 80/20 法則選擇每個子群的20%個體組建精英庫種群。

Step 4 對于精英庫種群，采用改進(jìn)綜合學(xué)習(xí)策略。

Step 5 對于普通種群，采用歷史經(jīng)驗指導(dǎo)的學(xué)習(xí)策略。

Step 7 若當(dāng)前迭代次數(shù)為偶數(shù)，執(zhí)行精英遷移策略，否則轉(zhuǎn)到step 8。

Step 8 循環(huán) step 2～step 7，根據(jù)式(2)、式(3) 更新普通種群各子群粒子的速率和位置， 根據(jù)式(8)、式(3)更新精英庫種群的粒子速率和位置。

Step 9 更新迭代次數(shù)Gennum，若還在迭代范圍內(nèi)，則轉(zhuǎn)到step 2；否則，停止更新。

Step 10 輸入全局最優(yōu)值和對應(yīng)調(diào)度方案，調(diào)度算法運行結(jié)束。

4 仿真結(jié)果及分析

為了驗證算法的有效性，本文選擇文獻(xiàn)[14]提出的Ta系列的基準(zhǔn)問題進(jìn)行仿真實驗。使用 Matlab2015b 軟件編程實現(xiàn)，參數(shù)設(shè)置與文獻(xiàn)[13]469相同，分裂因子為5，慣性權(quán)重w=0.4，學(xué)習(xí)因子c1=c2=2，精英庫種群綜合學(xué)習(xí)概率Pc=0.3，縮放因子初值d0=40，設(shè)置普通種群精英學(xué)習(xí)概率Pe時，分別使用0.1、0.3、0.5、0.7、0.9值求解Ta系列基準(zhǔn)算例Ta11、Ta21、T31、Ta41各10次，將平均值作為各算例的運算結(jié)果，再獲得所有算例求解結(jié)果的平均值并進(jìn)行比較，結(jié)果Pe取0.7較好。種群規(guī)模psize=150，迭代次數(shù)Gennum=500。設(shè)置好參數(shù)后，MPSO-CL與PSO、CPSO進(jìn)行比較，分別將每種算法運行10次，對每種算例運算所得的最好結(jié)果加粗顯示，得到仿真結(jié)果如表2所示。

表2中，最佳相對偏差BRE(Best Relative Error)和平均相對偏差A(yù)RE(Average Relative Error)的計算公式如下

(13)

(14)

由表1可知， PSO求解PFSP問題結(jié)果最差，CPSO運行結(jié)果比PSO有所改進(jìn)，除了Ta51三種算法，MPSO-CL的結(jié)果比PSO、CPSO都好，改進(jìn)效果很好， Ta01、Ta22、Ta35、T61都尋到了最優(yōu)結(jié)果。從穩(wěn)定性上可以看出， MPSO-CL的結(jié)果相對與其他三個算法比較穩(wěn)定。在處理大規(guī)模調(diào)度問題上，PSO與CPSO、MPSO-CL差距很大，說明協(xié)同進(jìn)化算法在解決大規(guī)模調(diào)度問題的優(yōu)勢，而改進(jìn)后MPSO-CL比CPSO在精度、穩(wěn)定性上都有提升。

為了更突出三種算法之間的差異，圖2給出了三種算法在求解Ta21、Ta71調(diào)度問題上的進(jìn)化曲線。

圖2中，三種算法在執(zhí)行的初始階段，PSO收斂速度被遠(yuǎn)遠(yuǎn)拉下，是由于CPSO和MPSO-CL都采用了“分而治之”[16]的協(xié)同思想；由于采用學(xué)習(xí)策略局部搜索， MPSO-CL的收斂速度有所下降，但不會陷入停滯，而CPSO易陷入“偽極值點”，卻無法跳出。以上說明MPSO-CL求解置換流水車間問題的有效性。

(a) Ta21

(b) Ta71圖2 PSO、CPSO和MPSO-CL進(jìn)化曲線

5 結(jié)論

本文針對置換流水車間調(diào)度中求解最小化最大完工時間問題進(jìn)行了研究，提出一種多粒子群協(xié)同學(xué)習(xí)粒子群算法來進(jìn)行優(yōu)化。該算法在協(xié)同粒子群算法的基礎(chǔ)上，將種群分為精英庫種群和普通種群，精英種群采用綜合學(xué)習(xí)策略，避免了早熟收斂；普通種群采用一種新的精英學(xué)習(xí)策略進(jìn)行局部搜索，提高了解的質(zhì)量；并且還引入精英遷移策略，增加了種群多樣性。通過不同規(guī)模Taillard系列基準(zhǔn)實例與PSO、CPSO進(jìn)行仿真比較，結(jié)果驗證該算法在求解PFSP上的有效性，在大規(guī)模調(diào)度上取得了不錯的效果。