改進的協同粒子群算法求解流水車間調度問題

秦志偉

摘 要：針對協同粒子群算法容易早熟和停滯的問題，提出了一種基于精英綜合學習的協同粒子群（ECLCPSO）算法。該算法在協同粒子群算法的基礎上，采用精英庫種群和普通種群并行協同進化架構。精英庫種群由高適應度個體構成，進行自我綜合學習，普通種群中個體向精英庫種群進行精英學習。為了避免算法陷入局部最優，引入了擾動機制。將該算法應用于Flow shop調度問題上，和另外三種優化算法進行比較，仿真結果證明改進的算法收斂速度快且精度高，優化性能較好。

關鍵詞：協同；粒子群；精英學習；流水車間調度

1 引言

當今的制造技術正由自動化、數字化、網絡化向智能化方向發展，智能制造（Intelligent Manufacturing，IM）被工業界和學術界普遍認為代表了制造業的發展方向，隨之帶來的智能調度問題成為研究的熱點。特別是工業4.0的提出，使得智能調度在智能制造中的智能工廠和智能物流兩方面扮演著核心大腦的角色，是智能制造的基礎。而流水車間調度問題（Flow Shop Scheduling Problem，FSSP），作為許多實際流水線上的簡化模型，它已被是一個典型的NP-hard問題1[1]，因此其研究具有重要的理論意義和工程意義。

雖然協同粒子群算法可以有效地改善傳統算法效率低、魯棒性差的問題，但容易陷入局部極值。由此，本文以確定型無限中間存儲方式的流水車間作為研究對象，并以整個流水車間工件的加工時間Makespan為目標函數，在將精英策略和綜合學習策略有效地結合一起，并引入擾動機制，來改進協同粒子群算法，提高協同粒子群算法的收斂速度和精度。

2 數學描述

本文以流水車間工件加工時間 Makespan為目標函數。Makespan可以描述為從第一個加工工件開始加工到最后一個工件完工所經歷的時間，問題具體描述如下：

一個n x m的確定型流水車間調度問題就是n個工件在n臺機器上流水加工的過程，假設工件按機器1～m的順序依次加工，令tij表示工件i在機器j上的加工時間，Cij表示工件i在機器j上的加工完成時間，Cmax表示所有工件加工完成時間，即Makespan。任給一個調度方案，即工件的加工排序，按照工件加工的次序，任意工件ik在機器j上的完成時間可以分為以下3種情況：[2]

，

上述模型即是FSSP優化的一個目標，可以看出，流水車間調度問題就是尋找一種可行的調度方案，使得加工周期最小，也就是說，求解最小的makespan。

3 精英綜合學習的協同粒子群算法流程

Step 1 初始化。確定m和n的數量，m是加工機器的數量，n是工件的數量，設定算法的協同種群個數、初始的子群粒子位置及速率，將粒子的個體最優位置設置為粒子的當前位置，隨機選擇一個粒子作為種群最優位置。

Step 2 按照適應度大小對每個子群粒子的適應值進行升序排序。

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

Step 4 對于精英庫種群，每個個體隨機地向精英庫種群中的其他兩個個體學習，取適應度好的就更新當前個體。

Step 5 對于普通種群，每個個體都可以通過隨機地向精英庫種群中的某個個體學習，若適應度得到改善就更新當前個體。

Step 6 判斷 t-tn是否大于擾動因子n。若是，則重置粒子速率；否則繼續。

Step 7 重復 step 2～step 7，確定各粒子應選擇的 pbest值。

Step 8 更新迭代次數，若還在迭代范圍內，則轉到步驟step 2；否則，停止更新。

Step 9 輸出整個粒子群（包括精英庫種群）的全局最優適應度，算法運行結束。

4 仿真結果及分析

本文采用的編碼是實數編碼轉換為自然數編碼的策略。將一個隨機的粒子按照權重分量升序排列得到對應的新粒子序列，而新粒子序列所對應于原粒子的位置就可以組合成一個新的自然數序列。

取劃分因子為5，慣性權重ω=0.4，學習因子c1=c2=2，自主學習概率Pc=0.3，擾動因子n=150，種群規模popsize=150。分別將每種算法運行10次。

圖1中可以看出，對于確定型流水車間調度問題，無論在搜索最優值上還是收斂速度上，GA、PSO、CPSO的結果都沒有ECLCPSO好，這說明 ECLCPSO求解Flow shop問題的有效性。

5 結論

本文研究了Flow Shop調度問題，以工件的加工時間Makespan為目標函數。針對協同粒子群優化算法（CPSO） 容易早熟和停滯的問題的缺陷，本文提出一種精英綜合學習的協同粒子群算法（ECLCPSO）。該算法在 CPSO 算法的基礎上，將精英策略和綜合學習策略有效地結合一起，組成了新的學習機制，并引入了擾動機制，將其通過與GA、PSO、CPSO進行仿真比較分析，仿真結果表明改進的算法收斂速度快且精度高，優化性能好，驗證了其解決Flow shop問題的有效性。

參考文獻

[1]王凌.車間調度及其遺傳算法[M].清華大學出版社，2003（05）：109-110

[2]張順，徐震浩，顧幸生.用改進的協同免疫算法求解FlowShop調度問題[J].東南大學學報（自然科學版），2012，42（s1）：157-162.