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

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

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

中圖分類號(hào)：TP3

文獻(xiàn)標(biāo)識(shí)碼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é)原理的改進(jìn)型調(diào)度算法，能以較大概率在可行時(shí)間范圍內(nèi)求得該問題的近似最優(yōu)解，但其復(fù)雜度一般較大，并且算法的結(jié)構(gòu)和參數(shù)都需要進(jìn)行合適的設(shè)定才能達(dá)到預(yù)期的效果[2]。針對上述情況，提出基于NEM求解置換流水車間調(diào)度問題的算法。該算法在求解PFSP時(shí)，將提出對較差粒子進(jìn)行變異操作這一思想，以提高算法的求解精度并加快算法的收斂速度。最后將通過實(shí)驗(yàn)仿真驗(yàn)證基于NEM求解PFSP算法的有效性。

1 NEM算法簡介[3]

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

2 NEM算法的改進(jìn)——變異操作

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

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

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

3 隨機(jī)鍵的引入

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

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

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

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

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

5 實(shí)驗(yàn)結(jié)果與分析

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

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

6 實(shí)例

某SMT生產(chǎn)線由高速貼裝機(jī)HS60和多功能貼裝機(jī)80F5組成，產(chǎn)品設(shè)計(jì)為單面貼裝。待貼裝元器件共有42種，根據(jù)封裝形式和組裝精度分別將這些元器件分配給HS60和80F5。分配給HS60的元器件為1～16，17～23必須分配到80F5上組裝，而24～42則兩者皆可?，F(xiàn)需對24～42共計(jì)19種元器件進(jìn)行EM算法優(yōu)化分配，要求總的貼裝時(shí)間最小，并且兩種貼裝機(jī)的貼裝時(shí)間差不大于0.35s。42種元器件的貼裝機(jī)分配、貼裝時(shí)間以及數(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），求解過程中獲得了兩個(gè)最優(yōu)解。兩個(gè)最優(yōu)解的總貼裝時(shí)間都是30.22s，T_HS60=15.26s，T_80ES=15.26s，實(shí)際貼裝時(shí)間差為ξ= 0.30s，符合生產(chǎn)線平衡的要求。

7 結(jié)束語

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

參考文獻(xiàn)

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

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

[3]姜建國，王雙記，劉永青，等，一種實(shí)用的類電磁機(jī)制算法[J].西安電子科技大學(xué)學(xué)報(bào)，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.