基于NEM的置換流水車間調(diào)度算法

摘要：對類電磁機制算法進行優(yōu)化設(shè)計，提出基于NEM求解置換流水車間調(diào)度問題的算法。該算法將通過引入隨機鍵的編碼方式和對較差粒子進行變異的操作方式，以提高算法求解的精度和收斂的速度。最后將通過仿真實驗驗證該算法的有效性。

關(guān)鍵詞：類電磁機制算法;NEM;調(diào)度;變異

中圖分類號：TP3

文獻標識碼A

置換流水車間調(diào)度問題（Permutation Flow ShopScheduling Problem，PFSP）廣泛存在于生產(chǎn)系統(tǒng)和服務(wù)系統(tǒng)中，是典型的組合優(yōu)化問題，也是典型的NP難問題[1]。PFSP的求解方法很多：構(gòu)造型啟發(fā)式算法，能夠快速地構(gòu)造解，但解的質(zhì)量和算法通用性通常較差;基于物理或仿生學(xué)原理的改進型調(diào)度算法，能以較大概率在可行時間范圍內(nèi)求得該問題的近似最優(yōu)解，但其復(fù)雜度一般較大，并且算法的結(jié)構(gòu)和參數(shù)都需要進行合適的設(shè)定才能達到預(yù)期的效果[2]。針對上述情況，提出基于NEM求解置換流水車間調(diào)度問題的算法。該算法在求解PFSP時，將提出對較差粒子進行變異操作這一思想，以提高算法的求解精度并加快算法的收斂速度。最后將通過實驗仿真驗證基于NEM求解PFSP算法的有效性。

1 NEM算法簡介[3]

通過對EM算法的初始化、局部搜索、合力計算和粒子移動四個步驟分別進行改進，并在此基礎(chǔ)上提出一種實用的類電磁機制算法——歸一化類電磁機制算法（ Normalization Electromagnetism-likeMechanism，NEM）。對EM算法“復(fù)雜度較大”這一缺陷，采用歸一化方法，使得目標函數(shù)值都在某個小范圍內(nèi)，這樣就可以減少運算量。針對EM算法局部搜索和計算合力中的缺陷，采用去掉易產(chǎn)生溢出錯誤的分母部分‖x_j-x_i‖²，添加一個合力計算修

2 NEM算法的改進——變異操作

為了擴大有效搜索范圍，增強算法的全局搜索能力，根據(jù)優(yōu)勝劣汰原則，在不增加新粒子的情況下，將最差的幾個粒子進行變異操作后，選擇變異后的較優(yōu)粒子替換原來的最差粒子，以便得到更優(yōu)的解。當(dāng)粒子數(shù)不小于30時，選擇變異當(dāng)前粒子群中最差的5個粒子，當(dāng)粒子數(shù)小于30時，略過此步。這么做是由于當(dāng)粒子數(shù)過少時，變異步驟會擾亂類電磁機制算法的收斂趨勢，并且會降低算法的收斂速度。

實現(xiàn)這一步驟比較簡單，首先按目標函數(shù)值的大小將粒子進行排序，目標函數(shù)值較大的排在后面，然后選擇最后的5個粒子進行變異操作。變異操作方式分為交換變異、插入變異和反轉(zhuǎn)變異，三種變異方式如圖1所示。

對選出的5個最差粒子分別使用這三種方式進行變異操作，共產(chǎn)生15個新粒子。從中選取5個最優(yōu)的粒子替換原粒子隊列中最后的5個粒子，最后再計算目標函數(shù)值并進行重新排序，更新當(dāng)前最優(yōu)值。

3 隨機鍵的引入

在一些離散型的優(yōu)化問題中，為了方便對解直接進行數(shù)學(xué)操作，廣泛采用了隨機鍵的編碼方式[4]。本文在基于NEM算法解決PFSP問題時，也借用隨機鍵的編碼方式模擬工件的排序。

隨機鍵的編碼方式就是將解轉(zhuǎn)換表示為一串（0，1）之間的隨機數(shù)，并將這串隨機數(shù)用作解碼時的分類鍵。例如一個9工件問題的調(diào)度方案：[0.82， 0.23， 0.45， 0.74， 0.87， 0.11，0.56， 0.69， 0.78]，其中，編碼中的位置代表工件，處在位置的隨機數(shù)代表工件的排列順序。將這些隨機數(shù)按照升序（工件的加工順序）進行排列，可得下面的排序：8-2-3-6-9-1-4-5—7。這種編碼方式可以消除NEM算法在求解過程中產(chǎn)生的不可行解。

隨機鍵與工件排序的轉(zhuǎn)換方式如圖2所示。首先將搜索到的粒子進行隨機鍵轉(zhuǎn)換，然后計算其適應(yīng)值，接著再進行粒子的合力計算和移動操作，最后將移動后得到的粒子再進行隨機鍵轉(zhuǎn)換，進入下一輪的循環(huán)。

4 算法設(shè)計與實現(xiàn)

通過隨機鍵編碼方式的引入，將離散型工件排序編碼轉(zhuǎn)變成NEM算法可直接使用的連續(xù)型編碼。將總的完工時間看作目標函數(shù)，其值越小，則解的適應(yīng)度值就越高。使用隨機方式初始化種群粒子，當(dāng)算法迭代次數(shù)到達預(yù)先設(shè)定的某個值時自動停止。算法的局部搜索采用最簡單的方式一僅對最優(yōu)粒子采取局部搜索。在規(guī)定的最大迭代次數(shù)內(nèi)，對當(dāng)前最優(yōu)粒子的每一維隨機均勻地按照一定步長進行局部搜索。在此過程中，如果找到更優(yōu)的解，則用其替換當(dāng)前最優(yōu)粒子。基于NEM的PFSP算法的流程如圖3所示。

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

實驗選取29個應(yīng)用廣泛的Benchmark問題進行性能測試，并與傳統(tǒng)GA和NEH作比較。這29個Benchmark問題指Carlier（ 1978）提出的8個算例Carl，Car2，…，Car8和Tailland（ 1993）提出的21個算例Rec01，Rec03，…，Rec41。NEM和GA分別對每個算例獨立運行20次，最大迭代次數(shù)均設(shè)為300，粒子數(shù)均設(shè)為30。實驗仿真結(jié)果如表1所示。表中，m和n分別表示機器數(shù)和工件數(shù)，c*表示問題的最優(yōu)解，RE表示與最優(yōu)解c*的相對誤差（c heu max- c*）xl00%，BRE為最優(yōu)相對誤差，ARE為平均相對誤差。

從表1可以看出，加入變異操作改進后的NEM算法具有很好的優(yōu)化質(zhì)量。尤其對Carlier系列問題，均能得到已知最優(yōu)解，ARE也都小于GA。對Tailland系列問題也能夠得到良好的近似最優(yōu)解，且質(zhì)量明顯優(yōu)于方法GA和NEH，甚至NEM的最差結(jié)果都遠遠優(yōu)于NEH方法。由此可見，經(jīng)過改進的NEM算法在優(yōu)化質(zhì)量方面相對于方法NEH和GA具有很大的優(yōu)越性。

6 實例

某SMT生產(chǎn)線由高速貼裝機HS60和多功能貼裝機80F5組成，產(chǎn)品設(shè)計為單面貼裝。待貼裝元器件共有42種，根據(jù)封裝形式和組裝精度分別將這些元器件分配給HS60和80F5。分配給HS60的元器件為1～16，17～23必須分配到80F5上組裝，而24～42則兩者皆可。現(xiàn)需對24～42共計19種元器件進行EM算法優(yōu)化分配，要求總的貼裝時間最小，并且兩種貼裝機的貼裝時間差不大于0.35s。42種元器件的貼裝機分配、貼裝時間以及數(shù)量見表2-表4。

通過NEM算法的優(yōu)化，所求得最優(yōu)解為：（1，1，0，1，0，0，1，0，1，0，1，1，0，1，1，1，1，1，1）和（1，1，0，1，0，1，1，0，0，1，1，1，0，0，1，1，0，1，1），求解過程中獲得了兩個最優(yōu)解。兩個最優(yōu)解的總貼裝時間都是30.22s，T_HS60=15.26s，T_80ES=15.26s，實際貼裝時間差為ξ= 0.30s，符合生產(chǎn)線平衡的要求。

7 結(jié)束語

針對EM算法不能直接被用來解決流水車間調(diào)度這類離散型優(yōu)化問題的情況，通過引入隨機鍵的編碼方式將工序編碼方式進行了轉(zhuǎn)換，然后在NEM算法的基礎(chǔ)上增添了變異操作從而對算法進行了改進，最后將改進后的NEM算法應(yīng)用于解決離散型的流水車間調(diào)度問題。實驗仿真結(jié)果表明，改進后的NEM算法成功地解決了流水車間調(diào)度問題。

參考文獻

[1]劉敏，張超勇，張國軍，等，基于混合粒子群優(yōu)化算法的置換流水車間調(diào)度問題研究[J].中國機械工程，2011，22（17）： 2048-2053.

[2] CEN M，CHENG R.Cenetic algorithm and engineering design[M]. Beijing： Science Press， 2000.

[3]姜建國，王雙記，劉永青，等，一種實用的類電磁機制算法[J].西安電子科技大學(xué)學(xué)報，2013（02）：48-53.

[4]KOLISCH R，HARTMANN S. Heuristic algorithms for solving theresource -constrained project scheduling problem： classificationand computational analysis [M]. WECIARZ J （editor）： ProjectScheduling-Recent Models， Algorithms and Applications， KluwerAcademic Publishers. Boston. 1999：147.