羅　哲

?

面向多目標(biāo)流水車間調(diào)度的混合遺傳算法

羅哲

（湖南科技學(xué)院 電子與信息工程學(xué)院，湖南 永州 425199）

建立最大完工時間、最大拖期時間及總流程時間三個調(diào)度目標(biāo)的多目標(biāo)流水車間調(diào)度問題模型，提出一種混合遺傳算法。該算法以灰熵并行關(guān)聯(lián)度作為遺傳算法的適應(yīng)度分配機制，以灰熵并行關(guān)聯(lián)度優(yōu)選個體，并建立Pareto外部檔案，以非劣排序及擁擠距離保持外部檔案中解的質(zhì)量及多樣性。通過與RWGA和NSGA-II算法進行標(biāo)準(zhǔn)問題的對比實驗，驗證了所提算法在解決多目標(biāo)流水車間調(diào)度問題中的有效性。

多目標(biāo)流水車間調(diào)度；遺傳算法；灰熵并行關(guān)聯(lián)度；適應(yīng)度分配；外部檔案

1　引　言

流水車間調(diào)度（flow shop scheduling，F(xiàn)SP）是生產(chǎn)調(diào)度問題的一個重要組成部分。許多實際的生產(chǎn)過程都可以抽象為流水車間調(diào)度模型。因此，F(xiàn)SP具有很強的理論研究和工程應(yīng)用價值，它是一類典型的NP-hard問題[1]。近幾十年來，F(xiàn)SP一直是個研究熱點。起初學(xué)者的研究主要集中于單目標(biāo)流水車間調(diào)度問題(single objective flow shop scheduling，SOFSP)，研究涉及的目標(biāo)大多為最大完工時間。如文獻[2,3]都以最大完工時間為調(diào)度目標(biāo)，研究了單目標(biāo)的流水車間調(diào)度問題。然而以上的單目標(biāo)流水車間調(diào)度問題研究結(jié)果并不能有效適用于現(xiàn)實的流水車間調(diào)度。一個主要原因是現(xiàn)實的流水車間調(diào)度往往受到很多因素的影響，如企業(yè)內(nèi)部生產(chǎn)率和外部客戶交貨期。僅考慮單個目標(biāo)的流水車間調(diào)度問題不能滿足多方的利益需求。故近年來的流水車間調(diào)度問題研究逐漸由單目標(biāo)向多目標(biāo)擴展。

多目標(biāo)流水車間調(diào)度問題(multi-objective flow shop scheduling，MOFSP)是單目標(biāo)流水車間調(diào)度問題的擴展，同樣是典型的NP-hard問題。針對此類問題，國內(nèi)外學(xué)者進行了深入研究，提出了大量求解方法。文獻[4]研究了最大完工時間和最大拖期時間的兩目標(biāo)流水車間調(diào)度問題，提出一種混合遺傳算法求解該問題；文獻[5]研究了最大完工時間、最大拖期時間、總流程時間、總庫存成本和總拖期成本的五目標(biāo)供應(yīng)鏈流水車間調(diào)度問題，并以基于灰熵并行分析的遺傳算法求解；文獻[6]研究了最大完工時間和總流程時間的兩目標(biāo)流水車間調(diào)度問題，以Pareto優(yōu)化的模擬退火算法求解該問題。

MOFSP的優(yōu)化求解屬于多目標(biāo)優(yōu)化(multi-objective optimization，MOO)范疇。目前求解多目標(biāo)優(yōu)化問題的主要方法為基于Pareto優(yōu)先支配關(guān)系與基于線性加權(quán)兩大類。與基于線性加權(quán)的優(yōu)化方法不同的是，Pareto優(yōu)化得到的最優(yōu)解不是單個解，而是一組Pareto均衡解集，決策者可以從解集中選擇合適的解。近年來基于Pareto的優(yōu)化技術(shù)已大量應(yīng)用于各種多目標(biāo)優(yōu)化問題，獲得了很好的優(yōu)化效果。

文章研究多目標(biāo)流水車間調(diào)度問題，以最大完工時間、最大拖期時間、總流程時間為優(yōu)化目標(biāo)，建立相應(yīng)的多目標(biāo)數(shù)學(xué)模型。提出一種混合遺傳算法(Hybrid Genetic Algorithm，HGA)，該算法以灰熵并行關(guān)聯(lián)度為適應(yīng)度值，并結(jié)合Pareto外部檔案技術(shù)，求解所提的多目標(biāo)流水車間調(diào)度問題。

2　問題描述及數(shù)學(xué)建模

2.1問題描述

經(jīng)典的流水車間調(diào)度問題可描述為：n個待加工工件需m臺不同的機器進行加工，每個工件都有m道工序，每個工件以相同順序訪問所有機器，工件在機器上的加工時間固定[7]。已知每個工件的交貨期，要求確定所有工件在機器上的加工順序，使一個或多個調(diào)度目標(biāo)整體最優(yōu)。

2.2數(shù)學(xué)建模

其中

3　面向多目標(biāo)流水車間調(diào)度的HGA算法實現(xiàn)

3.1遺傳編碼方式

由于多目標(biāo)流水車間調(diào)度方案為離散的可行解，算法實現(xiàn)之前需將解進行編碼。文章采用文獻[8]中的ROV(Ranked Order Value)隨機鍵編碼方式將HGA算法染色體個體編碼。

3.2多目標(biāo)適應(yīng)度值分配機制

多目標(biāo)適應(yīng)度值分配機制是影響多目標(biāo)優(yōu)化算法的一個重要因素[9,10]?，F(xiàn)有的多目標(biāo)適應(yīng)度值分配策略主要有Pareto優(yōu)先支配關(guān)系及目標(biāo)權(quán)重求和兩大類。參照文獻[11]的灰熵并行關(guān)聯(lián)度作為文章HGA算法的多目標(biāo)適應(yīng)度值分配機制?；异夭⑿嘘P(guān)聯(lián)度的適應(yīng)度值分配機制主要步驟如下：

Step2計算灰關(guān)聯(lián)系數(shù)：

Step 4求種群多目標(biāo)解的灰熵并行關(guān)聯(lián)度：

以灰熵并行關(guān)聯(lián)度作為種群中多目標(biāo)解的適應(yīng)度值，可客觀地表示當(dāng)前多目標(biāo)解與參考解的關(guān)聯(lián)度，或者說相似接近程度。一般灰熵并行關(guān)聯(lián)度值越大，則該多目標(biāo)解越逼近參考解。在HGA算法中根據(jù)灰熵并行關(guān)聯(lián)度的大小選出最優(yōu)個體，不斷更新全局最優(yōu)個體，引導(dǎo)算法進化逼近 Pareto 前端。

3.3Pareto外部檔案的建立及維護更新

（1）Pareto外部檔案的建立

在HGA算法的初始種群產(chǎn)生后，以式(1)-(3)計算種群個體的目標(biāo)函數(shù)值，得到Pareto多目標(biāo)解，同時計算個體Pareto多目標(biāo)解和參考解的灰熵并行關(guān)聯(lián)度。按灰熵并行關(guān)聯(lián)度的大小排序，由大到小選擇固定數(shù)量的Pareto多目標(biāo)解存入外部集合 ES中，生成外部檔案。

（2） Pareto外部檔案的維護更新

引用文獻[12]中非劣排序以及擁擠距離的概念對第二代開始的每代種群的Pareto多目標(biāo)解進行計算，將當(dāng)代種群的每個Pareto多目標(biāo)解與外部檔案ES中儲存的解進行比較。若當(dāng)代種群存在Pareto多目標(biāo)解比外部檔案ES中的某些解優(yōu)，則將該解添加到外部檔案，而原外部檔案的劣解被刪除，也就是對外部檔案進行維護更新。

3.4HGA算法流程

圖1為本文的HGA算法求解多目標(biāo)流水車間調(diào)度問題的流程圖，其具體步驟如下：

Step1：設(shè)置參數(shù)，初始化種群；

Step2：構(gòu)造參考解和每代種群的多目標(biāo)解；

Step3：計算灰關(guān)聯(lián)系數(shù)；

Step4：計算每代種群的多目標(biāo)解的比重、信息熵及熵值權(quán)重；

Step5：計算每代種群的多目標(biāo)解的灰熵并行關(guān)聯(lián)度；

Step6：選擇操作；

Step7：交叉操作；

Step8：變異操作；

Step9：Pareto外部檔案的建立及維護更新；

Step10：終止條件判斷。達(dá)到最大迭代代數(shù)則結(jié)束程序；否則，轉(zhuǎn)Step2；

Step11：輸出結(jié)果。

圖1.HGA求解多目標(biāo)流水車間調(diào)度問題流程圖

4　實驗及結(jié)果分析

為驗證HGA算法的性能，本文通過7個不同規(guī)模的標(biāo)準(zhǔn)問題進行測試，并與兩種多目標(biāo)算法進行對比。這兩種比較算法分別是文獻[13]的 RWGA(Random Weighting Genetic Algorithm)和文獻[14]的NSGA-II，其中NSGA-II是國際公認(rèn)的一種優(yōu)化算法。從多目標(biāo)優(yōu)化解、計算時間及解集評價指標(biāo)三個方面進行結(jié)果分析。

4.1參數(shù)設(shè)置

HGA、RWGA、NSGA-II三種算法的相關(guān)參數(shù)設(shè)置如表1 所示。三種GA算法都選用二進制交叉和多項式變異，所有算法重復(fù)5次，取平均值作為最終結(jié)果。

表1.參數(shù)設(shè)置

參數(shù)參數(shù)值 種群50 迭代代數(shù)100 外部檔案大小30 二進制交叉概率0.9 多項式變異概率0.1 算法重復(fù)次數(shù)5

4.2結(jié)果分析

（1）多目標(biāo)解。表2列出了三種算法獲得的7個不同規(guī)模標(biāo)準(zhǔn)問題的最優(yōu)多目標(biāo)解。其中n表示工件數(shù)量，m表示工序數(shù)量，從表2可以發(fā)現(xiàn)在7個問題中，文章的HGA算法獲得的三個目標(biāo)函數(shù)值都要比RWGA和NSGA-II的更優(yōu)，三種算法中RWGA獲得的目標(biāo)函數(shù)值最差。表2表明HGA算法在解決多目標(biāo)流水車間調(diào)度問題時具有一定的優(yōu)越性。

表2.三種算法的多目標(biāo)解

問題規(guī)模(nxm)參考多目標(biāo)解算法最優(yōu)多目標(biāo)解 110x5{840, 350,5402}RWGA{978,696,6360} NSGA-II{883,467,5499} HGA{877,361,5402} 210x10{1115,230,8082}RWGA{1296,581,9246} NSGA-II{1240,251,8479} HGA{1212,238,8402} 320x5{1360,525,16232}RWGA{1536,1239,18100} NSGA-II{1433,623,17992} HGA{1380,572,17310} 420x10{1820,734,23520}RWGA{2070,1595,27199} NSGA-II{1901,1087,24533} HGA{1852,968,23547} 540x10{3066,23182,74320}RWGA{3230,3023,81556} NSGA-II{3037,2439,74665} HGA{3019,2375,74572} 650x10{3455,2588,105570}RWGA{3990,3670,117610} NSGA-II{3620,2800,107550} HGA{3600,2710,106730} 760x10{4010,2445,142088}RWGA{4440,3860,155550} NSGA-IIHGA{4060,2790,144160} {4075,2335,143552}

（2）計算效率。表3列出了三種算法在解決7個不同規(guī)模問題時CPU時間消耗?？梢钥闯觯?個不同規(guī)模問題中，RWGA耗時最短，HGA耗時稍長于RWGA，而NSGA-II耗時最長。結(jié)合(1)中結(jié)果可知，RWGA耗時雖然最短，但其最優(yōu)解質(zhì)量很差，不利于決策者方案的選取，而HGA算法可以在稍長的耗時內(nèi)獲得更優(yōu)的解。

表3. CPU 時間消耗

問題規(guī)模(nxm)CPU耗時(s) RWGANSGA-IIHGA 110x56.1116.006.23 210x107.7517.558.05 320x59.5528.7610.72 420x1013.6630.5515.00 540x1024.8746.1626.55 650x1018.2335.4421.62 760x1017.3426.8820.53

圖2.三種算法的D1R值比較

結(jié)束語

針對多目標(biāo)流水車間調(diào)度問題，提出一種混合遺傳算法，該算法以灰熵并行關(guān)聯(lián)度作為遺傳算法的多目標(biāo)適應(yīng)度分配機制，以灰熵并行關(guān)聯(lián)度選擇最優(yōu)個體，引導(dǎo)算法向更優(yōu)方向進化，同時引入Pareto外部檔案技術(shù)保持解的質(zhì)量及多樣性。通過仿真實驗表明，所提混合遺傳算法在解質(zhì)量、計算效率及解集收斂等方面都要優(yōu)于RWGA和NSGA-II算法。

[1]Garey M R,Johnson D S,Sethi R.The Complexity of Flow-shop and Jobshop Scheduling[J].Mathematics of Operations Research,1976,(2):117-129.

[2]魏文杲,蔣真真,于翔,馬秀明.基于改進遺傳算法的流水車間調(diào)度研究與仿真[J].裝備制造技術(shù),2011,(2):4-6+9.

[3]Chung Y H,Tong L I.Makespan minimization for mmachine permutation flowshop scheduling problem with learning considerations[J].International Journal of Advanced Manufacturing Technology,2011,(56):355-367.

[4]楊開兵.多目標(biāo)混合遺傳算法求解流水車間調(diào)度問題[J].電腦與信息技術(shù),2008,(2):28-30.

[5]朱光宇,賀利軍.基于灰熵并行分析優(yōu)化算法的多目標(biāo)流水車間調(diào)度[J].計算機工程,2015,(10):165-170.

[6]Suresh R K,Mohanasundaram K M.Pareto archived simulated annealing for permutation flow shop scheduling with multiple objectives[C]//Proceedings of 2004 IEEE Conference on Cybernetics and Intelligent Systems. Singapore:IEEE,2004:712-717.

[7]雷德明.現(xiàn)代制造系統(tǒng)智能調(diào)度技術(shù)及其應(yīng)用[M].北京:中國電力出版社,2011.

[8]Bean J C.Genetic Algorithms and Random Keys for Sequen-cing and Optimization[J].Orsa Journal on Computing,1994, (6):154-160.

[9]衛(wèi)忠,徐曉飛,鄧勝春.多目標(biāo)混合流水車間作業(yè)調(diào)度的演化算法[J].計算機集成制造系統(tǒng),2006,(8):1227-1234.

[10]賀利軍,劉超,朱光宇.基于模糊關(guān)聯(lián)熵的高維多目標(biāo)流水車間調(diào)度優(yōu)化[J].計算機集成制造系統(tǒng),2015,(10):2704- 2710.

[11]朱光宇,馮子超,楊志鋒.灰熵并行分析引導(dǎo) PSO求解多目標(biāo)優(yōu)化問題[J].系統(tǒng)工程與電子技術(shù),2014,(11):2233- 2238.

[12]雷德明,嚴(yán)新平.多目標(biāo)智能優(yōu)化算法及其應(yīng)用[M].北京:科學(xué)出版社,2009.

[13]Konak A,Coit D W,Smith A E.Multi-objective optimiza-tion using genetic algorithms:A tutorial[J].Reliability Engineering & System Safety,2006,(9):992-1007.

[14]Deb K,Pratap A, Agarwal S,et al.A fast and elitist multi-objective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,(2):182-197.

[15]Czyzzak,Piotr,Jaszkiewicz A.Pareto simulated annealinga metaheuristic technique for multiple-objective combinatorial optimization[J].Journal of Multi-criteria Decision Analysis, 1998,(1):34-47.

（責(zé)任編校：宮彥軍）

2017－02－15

湖南科技學(xué)院科學(xué)研究項目（項目編號17XKY066）。

羅哲(1988－)，男，湖南永州人，湖南科技學(xué)院工程師，碩士，主要從事優(yōu)化算法和柴油機的研究。

TP391

A

1673-2219（2017）10-0071-04