基于灰熵并行分析優(yōu)化算法的多目標流水車間調(diào)度

朱光宇，賀利軍

（福州大學機械工程及自動化學院，福州 350108）

基于灰熵并行分析優(yōu)化算法的多目標流水車間調(diào)度

朱光宇，賀利軍

（福州大學機械工程及自動化學院，福州 350108）

在供應(yīng)鏈環(huán)境下構(gòu)建一個多目標Flow Shop調(diào)度優(yōu)化模型，采用灰熵并行分析（GEPA）法優(yōu)化該多目標模型。在表征序列間相似程度的灰關(guān)聯(lián)分析法基礎(chǔ)上引入信息熵理論建立GEPA法，推導(dǎo)出的灰熵并行關(guān)聯(lián)度衡量多目標Pareto解與理想解的相似程度，并將其作為適應(yīng)度值引導(dǎo)算法進化，避免多目標優(yōu)化問題中直接對目標權(quán)重賦值。在此基礎(chǔ)上建立基于灰熵并行分析的遺傳算法。實驗結(jié)果表明，該算法可有效解決供應(yīng)鏈環(huán)境下高維多目標Flow Shop調(diào)度問題，在多目標最優(yōu)解、性能評價指標等方面均優(yōu)于基于隨機權(quán)重的遺傳算法。

供應(yīng)鏈；多目標Flow Shop；灰熵并行分析法；灰熵并行關(guān)聯(lián)度；多目標優(yōu)化；遺傳算法

DO I：10.3969/j.issn.1000-3428.2015.10.031

1 概述

供應(yīng)鏈環(huán)境下的企業(yè)生產(chǎn)比單個企業(yè)內(nèi)部生產(chǎn)更加復(fù)雜，不但要考慮自身企業(yè)內(nèi)部的生產(chǎn)調(diào)度問題，還要考慮到供應(yīng)鏈上其他節(jié)點企業(yè)的因素，如原料采購、交貨期、庫存、運輸?shù)取鴥?nèi)外對供應(yīng)鏈生產(chǎn)調(diào)度這一熱點問題已取得一定的研究成果，如文獻［1］提出供應(yīng)鏈調(diào)度的概念；文獻［2］研究了供應(yīng)鏈環(huán)境下等待約束的流水線調(diào)度問題；文獻［3］構(gòu)造了遺傳粒子群混合算法，運用混合算法對供應(yīng)鏈優(yōu)

化調(diào)度問題進行求解。

供應(yīng)鏈環(huán)境下的生產(chǎn)調(diào)度涉及的絕大部分為多目標問題［4］，其目標維數(shù)一般要比單個企業(yè)生產(chǎn)調(diào)度問題目標維數(shù)大。目前求解供應(yīng)鏈環(huán)境下企業(yè)生產(chǎn)調(diào)度問題的方法主要有多目標規(guī)劃法和多目標智能算法，其中遺傳算法（Genetic Algorithm，GA）、PSO等多目標智能算法應(yīng)用越來越頻繁，且2種方法研究的多為 3個目標以下的低維問題，如文獻［5-6］應(yīng)用多目標規(guī)劃法根據(jù)固定的目標權(quán)重進行線性加權(quán)求和，優(yōu)化雙目標供應(yīng)鏈問題；文獻［7］設(shè)計了一種混合遺傳算法求解單目標敏捷供應(yīng)鏈調(diào)度優(yōu)化問題；文獻［8］提出利用廣義遺傳粒子群算法求解單目標供應(yīng)鏈問題。

多目標規(guī)劃法適用于求解規(guī)模較小的問題，權(quán)重選取主觀因素太大，各目標間數(shù)量級和量綱也難以統(tǒng)一，求解規(guī)模較大的供應(yīng)鏈問題收效甚微；多目標智能算法由于各目標相互制約，優(yōu)化解在解質(zhì)量、收斂性等指標上難以讓人滿意，其主要難點在于適應(yīng)度分配策略的選取。現(xiàn)有適應(yīng)度分配策略主要有Pareto優(yōu)先排序關(guān)系［9］和隨機權(quán)重［10］2種。2種適應(yīng)度分配策略的缺點在于：單純的Pareto優(yōu)先排序關(guān)系方法不能很好地解決高維多目標問題，目標維數(shù)越高搜索的盲目性越大；隨機權(quán)重法求解高維多目標問題時雖然優(yōu)于基于Pareto優(yōu)先排序方法，但忽略了Pareto解改善時可能提供的趨向性指示信息，處理高維問題時效率低［11］。 當問題規(guī)模較大、目標維數(shù)較高時，現(xiàn)有多目標規(guī)劃法和多目標智能算法適應(yīng)度分配策略的缺點更突出。

鑒于以上問題，本文建立五目標供應(yīng)鏈優(yōu)化模型，采用灰熵并行分析法與智能算法結(jié)合優(yōu)化該模型。灰熵并行分析法是灰關(guān)聯(lián)分析與信息熵結(jié)合的一種方法，其推導(dǎo)出的灰熵并行關(guān)聯(lián)度是不確定序列間相似程度的度量。將灰熵并行分析法與通用性強的GA結(jié)合，建立基于灰熵并行分析的GA，以灰熵并行關(guān)聯(lián)度衡量Pareto解與理想解的相似程度，并將其作為適應(yīng)度引導(dǎo)算法進化。

2 基于灰熵并行分析的多目標優(yōu)化

灰熵并行分析法是在表征序列間相似程度的灰關(guān)聯(lián)分析法基礎(chǔ)上引入信息熵理論發(fā)展而來的一種方法，其特點在于利用灰色關(guān)聯(lián)分析和信息熵并行地對序列數(shù)據(jù)進行相似性分析。已有文獻將灰關(guān)聯(lián)分析法和信息熵理論分別應(yīng)用于多目標優(yōu)化中，如文獻［12］利用灰關(guān)聯(lián)分析法導(dǎo)出的灰關(guān)聯(lián)度衡量Pareto解的好壞，但該方法容易導(dǎo)致信息丟失和陷入局部關(guān)聯(lián)傾向；文獻［13］將信息熵理論應(yīng)用于多目標優(yōu)化，以保持解的分布均勻性和多樣性，其缺點在于沒有有效利用各目標間關(guān)聯(lián)信息。灰關(guān)聯(lián)分析法和信息熵理論結(jié)合成的灰熵并行分析法能夠克服2種方法的弱點，可以更好更全面地分析不確定序列間的相似接近程度。灰熵并行分析法應(yīng)用于多目標優(yōu)化時主要問題在于構(gòu)造理想解序列與Pareto解比較序列、序列間的灰關(guān)聯(lián)分析和序列間的灰熵并行分析。

2.1 理想解序列與Pareto解比較序列構(gòu)造

灰熵并行分析法應(yīng)用到多目標優(yōu)化時，首先需要找到理想解序列與Pareto解比較序列，然后計算2個序列的灰熵并行關(guān)聯(lián)度值，該值越大，則Pareto解比較序列與理想解序列越相似。

（1）理想解序列構(gòu)造

對多目標優(yōu)化的每個子目標實現(xiàn) k次單目標優(yōu)化，各子目標的單目標優(yōu)化解的平均值構(gòu)成理想解序列Y0=｛f1（0），f2（0），…，fM（0）｝，其中，M為目標個數(shù)；fM（0）為第 M個子目標的單目標優(yōu)化解。

（2）Pareto解比較序列構(gòu)造

多目標優(yōu)化中生成的Pareto解，構(gòu)成Pareto解比較序列Yi=｛f1（i），f2（i），…，fM（i）｝，i=1，2，…，N，fM（i）為Pareto解的第M個子目標值。

2.2 灰關(guān)聯(lián)分析

灰關(guān)聯(lián)分析的基本思想是根據(jù)序列曲線幾何形狀的相似程度來判斷其聯(lián)系是否緊密。曲線越接近，相應(yīng)序列之間灰關(guān)聯(lián)度就越大，反之就越小［14］。因此，可以將灰關(guān)聯(lián)分析法應(yīng)用于多目標優(yōu)化來分析理想解序列與Pareto解比較序列的相似程度。灰關(guān)聯(lián)分析法對理想解序列與Pareto解比較序列進行關(guān)聯(lián)分析的過程如下：

（1）均值化

通過均值化算子對理想解序列與Pareto解比較序列的各子目標均值化處理，以消除目標間數(shù)量級和量綱的影響，均值化算子公式如下：

其中，k=1，2，…，M；i=0，1，…，N。

（2）求兩級最大差和最小差：

其中，k=1，2，…，M；i=1，2，…，N。

（3）求灰關(guān)聯(lián)系數(shù)：

其中，ρ∈（0，1）為分辨系數(shù)；k=1，2，…，M；i=1， 2，…，N。

2.3 灰熵并行分析

式（5）導(dǎo)出的灰關(guān)聯(lián)度r（Y0，Yi）表征的是理想解序列與Pareto解比較序列的相似程度，該值越大，相似程度越大。但灰關(guān)聯(lián)度值計算的是灰關(guān)聯(lián)系數(shù)的平均值，這容易導(dǎo)致信息丟失；同時灰關(guān)聯(lián)度值具有局部關(guān)聯(lián)傾向，傾向于灰關(guān)聯(lián)系數(shù)大的目標。針對這2個弱點，引入信息熵內(nèi)容，計算多目標解各子目標的熵值權(quán)重，與灰關(guān)聯(lián)分析法結(jié)合成灰熵并行分析法，以期克服灰關(guān)聯(lián)分析的弱點。

（1）計算式（1）中Pareto解序列均值化后各子目標所占比重，即：

（4）求灰關(guān)聯(lián)度值：

其中，k=1，2，…，M；i=1，2，…，N。

（2）計算Pareto解序列各子目標的信息熵：

其中，k=1，2，…，M；i=1，2，…，N。

（3）計算Pareto解序列各子目標的熵值權(quán)重：其中，k=1，2，…，M；i=1，2，…，N。

（4）熵值權(quán)重和灰關(guān)聯(lián)系數(shù)結(jié)合，計算灰熵并行關(guān)聯(lián)度R（Y0，Yi）：

其中，k=1，2，…，M；i=1，2，…，N。

灰熵并行分析法是動態(tài)灰過程發(fā)展態(tài)勢整體接近性分析與信息熵結(jié)合的方法，是一種全局方法。灰熵并行分析法對于分析對象的數(shù)據(jù)序列不需要其服從某一特定分布，其主要以目標數(shù)據(jù)為基礎(chǔ)，對于所研究目標數(shù)據(jù)離散或數(shù)據(jù)不充分問題均適用，因此可以應(yīng)用于供應(yīng)鏈環(huán)境下多目標Flow Shop調(diào)度優(yōu)化問題中。以灰熵并行關(guān)聯(lián)度作為適應(yīng)度引導(dǎo)智能算法進化，灰熵并行關(guān)聯(lián)度值越大表明優(yōu)化解越相似于理想解。

3 問題描述及多目標模型

3.1 問題描述

本文構(gòu)建了一個線性供應(yīng)鏈問題，涉及到供應(yīng)鏈上原料供應(yīng)商、制造商和銷售商3個企業(yè)，涉及到原料采購、生產(chǎn)、運輸?shù)裙?yīng)鏈活動。具體問題描述如下：

制造商從銷售商接到一訂單，需要加工一批數(shù)量為n的工件，完工后運輸?shù)戒N售商。制造商工廠為典型Flow Shop生產(chǎn)類型，即n個工件由m臺機器加工，每個工件具有一定數(shù)量的工序，每個工件以相同順序訪問所有機器，工件在機器上的加工時間固定［15］。整個供應(yīng)鏈活動由以下部分組成：

（1）制造商加工工件前從原料供應(yīng)商處采購加工原料，原料采購成本和原料運輸成本都為固定值。受到銷售商交貨期和自身庫存影響，制造商必須在合理時間完成工件。超過交貨期完工的工件將受到拖期懲罰，產(chǎn)生拖期成本，提前完工的工件將產(chǎn)生庫存成本。拖期成本和庫存成本都與時間成正比。

（2）工件完工后將批量性運輸?shù)戒N售商，運輸工具最大運載數(shù)量固定。假設(shè)制造商完工工件達到運輸工具最大運載數(shù)量時即開始運輸，每次起運時刻為每批最后一個工件完工時間，若最后一批工件數(shù)不足最大運載數(shù)量則按一批運輸。

本文問題是確定工件加工順序，使工件最大完工時間、最大拖期時間、總流程時間、總庫存成本和總拖期成本5個目標最小。

3.2 多目標模型

本文建立的多目標模型為F=m in（f1，f2，f3，f4，f5），其中：

其中，f1為工件最大完工時間；f2為最大拖期時間；f3為總流程時間；f4為總庫存成本；f5為總拖期成本。Ci，Di，Li分別為工件i最后完工時間、交貨期和起運時刻，處于同一批次工件起運時刻一致；Tik為工件i的第k道工序所需加工時間；Cik表示工件i的第k道工序完工時間；g，h分別表示原料和完工工件運輸工具單次最大運輸數(shù)量；V（i），S（j）分別表示原料和工件運輸工具單次實際運輸數(shù)量；a，b分別表示原料和工件批量運輸次數(shù)；βi，γi分別表示單位時間庫存和拖期成本。

4 多目標Flow Shop調(diào)度問題

遺傳算法（GA）已經(jīng)被應(yīng)用于眾多領(lǐng)域，本文將灰熵并行分析法與GA結(jié)合，同時優(yōu)化供應(yīng)鏈模型的5個目標。考慮到Flow Shop調(diào)度生產(chǎn)工件加工路線和工序相同的特點，GA編碼采用基于工件順序的編碼方案［16］。基于灰熵并行關(guān)聯(lián)分析的GA求解供應(yīng)鏈環(huán)境下多目標Flow Shop調(diào)度問題的具體步驟如下：

步驟1 利用GA對問題的各目標單目標優(yōu)化，單目標優(yōu)化解構(gòu)成理想解序列 Y0。產(chǎn)生初始種群，生成NP個個體為種群當代代數(shù)。利用式（10）～式（14）計算個體的多目標函數(shù)值，各目標值構(gòu)成Pareto解序列

步驟2 利用式（9）計算理想解序列 Y0與 Pareto解序列的灰熵并行關(guān)聯(lián)度，并將其作為GA適應(yīng)度值引導(dǎo)算法進化。

步驟3 選擇操作。采用二元錦標賽［17］方法進行選擇。

步驟4 交叉操作。采用部分映射交叉（PMX）［17］方法交叉，交叉概率Pc一般取0.40～0.99。

步驟5 變異操作。采用互換變異（SAWP）［17］方法變異。變異操作可以維持群體多樣性，Pm一般取0.001～0.1。

步驟6 外部檔案維護和更新。通過非劣排序以及擁擠距離［16］對每代產(chǎn)生的非劣解進行計算，將每次迭代產(chǎn)生的解與外部檔案Pareto解進行優(yōu)劣比較，進行相應(yīng)的刪除、添加操作更新Pareto解，即對外部檔案進行更新，通過精英保留策略使得種群的多樣性得到提升。

步驟7 判斷是否滿足終止條件。群體適應(yīng)度值連續(xù)一定次數(shù)不發(fā)生變化或者進化次數(shù)達到要求的最大代數(shù)maχgen時迭代終止；否則，gen=gen+1轉(zhuǎn)步驟2。

上述算法實現(xiàn)過程中，主要是步驟1、步驟2和步驟6會對GA復(fù)雜度造成影響。其中，步驟1的時間復(fù)雜度為O（n×m×M×maχgen×NP2）；步驟2時間復(fù)雜度為O（maχgen×NP）；步驟6時間復(fù)雜度為O（maχgen×Wmax×log Wmax）；標準多目標GA時間復(fù)雜度為O（n×m×M×maχgen×NP2），其中，n為問題工件數(shù)；m為工序數(shù)；M為目標數(shù)；maχgen為迭代代數(shù)；NP為種群規(guī)模。由此可知時間復(fù)雜度量級最大的步驟1與標準多目標 GA時間復(fù)雜度相同，并沒有增加 GA時間復(fù)雜度。算法空間復(fù)雜度方面，由于本文算法程序所需存儲空間都很小，計算機設(shè)備完全能滿足其存儲空間要求，本文算法也不會對GA空間復(fù)雜度造成明顯影響。

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

為驗證灰熵并行分析法的有效性，本文參考文獻［17］方法對供應(yīng)鏈環(huán)境下的制造商工廠產(chǎn)生16個不同規(guī)模的調(diào)度問題實例。從多目標最優(yōu)解、各性能指標等方面，將基于灰熵并行分析的遺傳算法（Grey Entropy Parallel Analysis Method Genetic Algorithm，GEPA-GA）與基于隨機權(quán)重的遺傳算法［18］（Random Weighting Genetic Algorithm，RW-GA）進行比較，因為基于隨機權(quán)重的非Pareto優(yōu)先排序方法被證實在處理高維問題時表現(xiàn)較好［11，19］。 通過分析比較說明該方法的有效性，展示算法GEPA-GA在求解供應(yīng)鏈環(huán)境下多目標Flow Shop調(diào)度問題的優(yōu)越性。

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

算法的種群規(guī)模 NP=20，外部檔案個體數(shù)Wmax=50，最大迭代次數(shù)maχgen=100。GA交叉概率Pc=0.75，變異概率Pm=0.1。單目標優(yōu)化次數(shù)k=10。單位庫存成本βi=1.5，單位拖期成本γi= 2。原料每批運輸最大數(shù)量g=10，完工工件每批最大運輸量h=5。灰關(guān)聯(lián)分析分辨系數(shù)ρ=0.5。

5.2 評價指標

本文采用當代距離（Generational Distance，GD）、間隔距離（Spacing，SP）和相對于理想解平均百分比偏差（ARPD）3個參數(shù)作為算法性能評價指標。

（1）當代距離［20］（GD），表征算法所得非劣解集與理想解間的接近程度，評價算法的收斂特性。計算公式為為外部檔案個體數(shù)，di為第i個非劣解與理想解間的歐氏距離，GD值越小表示與理想解越接近。

（2）間隔距離［21］（SP），表征算法所得非劣解集的解分布情況。SP計算公式為：

（3）相對于理想解的平均百分比偏差［22］（Average Percentage Deviation，ARPD），表示算法所得解的平均質(zhì)量，偏差越小，解的質(zhì)量越高。子目標M的ARPD（M）計算公式為：

其中，Wmax為外部檔案個體數(shù)；FHM（j）為外部檔案個體j的第M個目標的值；fM（0）為理想解的第M個目標的值。

5.3 結(jié)果分析

表1為2種算法的仿真實驗結(jié)果，在實例1、2、6、9、10、13、14中，算法GEPA-GA所得多目標最優(yōu)解有4個目標要好于算法RW-GA；實例3，4，5，7，8，11，12，15，16中，算法GEPA-GA在5個目標上都要好于算法RW-GA。這說明在解決該類問題上，GEPA-GA在整體上都要優(yōu)于RW-GA。16個實例的灰熵并行關(guān)聯(lián)度（GEPRD）均在0.8以上，表明GEPA-GA所得多目標最優(yōu)解與理想解的相似程度都比較高。

表1 16個問題實例的仿真結(jié)果

表2為2種算法性能評價指標結(jié)果，在當代距離（GD）指標上，除實例1，9，10，16外，其余12個實例上算法GEPA-GA的GD值都要小于算法RW-GA，表明算法GEPA-GA的收斂性整體上要好于算法RW-GA。在間隔距離（SP）上，除實例7，9，11，15，16外，其余11個實例上算法GEPA-GA的SP值都要小于算法RW-GA，表明算法GEPA-GA的解集整體上比算法RW-GA的解集分布更均勻。在相對于理想解的平均百分比偏差（ARPD）指標上，除實例1的第4個目標（f4）外，算法GEPA-GA在各實例上各目標的ARPD值都要小于算法RW-GA，說明算法GEPA-GA的多目標優(yōu)化解的質(zhì)量要高于算法RW-GA的多目標優(yōu)化解；算法GEPA-GA在一些實例中的ARPD值出現(xiàn)負數(shù)情況，表明算法GEPA-GA的多目標優(yōu)化解的某些目標的質(zhì)量甚至要高于理想解。ARPD值出現(xiàn)負數(shù)情況可能是以下兩方面原因?qū)е碌模菏紫龋珿A是一種隨機搜索算法，每次搜索到的最優(yōu)解之間可能存在微小偏差，且本文理想解構(gòu)造方式為單目標優(yōu)化解的平均值，其大小會比真實最優(yōu)解稍大；其次，本文算法迭代終止條件都為達到指定代數(shù)時終止，算法迭代次數(shù)達到指定代數(shù)時可能尚未完全收斂，導(dǎo)致其最優(yōu)解與真實最優(yōu)解之間存在誤差。仿真實驗結(jié)果表明，本文所采用灰熵并行分析法可以有

效解決多目標優(yōu)化問題，基于灰熵并行分析的遺傳算法在求解供應(yīng)鏈環(huán)境下多目標Flow Shop調(diào)度問題時，其多目標最優(yōu)解、算法性能評價指標都要優(yōu)于基于隨機權(quán)重的遺傳算法。

表2 2種算法的性能評價指標結(jié)果

6 結(jié)束語

本文提出采用灰熵并行分析法進行多目標優(yōu)化。建立基于灰熵并行分析的遺傳算法，以灰熵并行關(guān)聯(lián)度作為適應(yīng)度引導(dǎo)算法進化，優(yōu)化供應(yīng)鏈環(huán)境下多目標Flow Shop調(diào)度問題。仿真實驗結(jié)果表明，灰熵并行分析法與遺傳算法可有效結(jié)合，基于灰熵并行分析的遺傳算法可以有效解決供應(yīng)鏈環(huán)境下多目標Flow Shop調(diào)度問題，顯示出了灰熵并行分析法在解決高維多目標優(yōu)化問題的優(yōu)越性。

［1］ Hall N G.Supply Chain Scheduling：Batching and Delivery［J］.Operations Research，2003，51（4）：566-584.

［2］ Chauhan S S，Gordon V，Proth J M.Scheduling in Supply Chain Environment［J］.European Journal of Operational Research，2007，183（3）：961-970.

［3］ 劉小華.基于遺傳粒子群混合的可重入生產(chǎn)調(diào)度優(yōu)化［J］.同濟大學學報：自然科學版，2011，39（5）：726-731.

［4］ 黃明達，劉 林.供應(yīng)鏈下Flow Shop調(diào)度問題的多目標混合算法研究［J］.合肥工業(yè)大學學報：自然科學版，2011，34（10）：1564-1569.

［5］ 楊 懿.產(chǎn)供銷一體化的供應(yīng)鏈生產(chǎn)多目標規(guī)劃模型［J］.西華大學學報，2006，25（6）：93-95.

［6］ 周金宏，汪定偉.考慮多運輸方式的供應(yīng)鏈生產(chǎn)計劃多目標模型［J］.系統(tǒng)工程學報，2000，15（4）：362-366.

［7］ 王建華.求解敏捷供應(yīng)鏈調(diào)度優(yōu)化問題的混合遺傳算法［J］.計算機工程與應(yīng)用，2011，47（17）：224-228.

［8］ 胡桂武.基于廣義遺傳粒子群優(yōu)化算法的供應(yīng)鏈優(yōu)化求解［J］.計算機應(yīng)用，2008，28（11）：2840-2843.

［9］ Elaoud S，Loukil T，Teghem J.The Pareto Fitness Genetic Algorithm：Test Function Study［J］.European Journal of Operational Research，2007，177（3）.

［10］ 王 凌.車間調(diào)度及其遺傳算法［M］.北京：清華大學出版社，2003.

［11］ 衛(wèi) 忠.多目標混合流水車間作業(yè)調(diào)度的演化算法［J］.計算機集成制造系統(tǒng)，2006，12（8）：1227-1234.

［12］ 李俊峰，戴文戰(zhàn).基于遺傳算法和灰色關(guān)聯(lián)度的多目標問題求解方法研究［C］//第25屆中國控制會議論文集.北京：航空航天大學出版社，2006：557-560.

［13］ 王 娜.基于混沌多目標粒子群優(yōu)化算法的云服務(wù)選擇［J］.計算機工程，2014，40（3）：23-27，38.

［14］ 劉思峰，謝乃明.灰色系統(tǒng)理論及其應(yīng)用［M］.北京：科學出版社，2008.

［15］ 雷德明.現(xiàn)代制造系統(tǒng)智能調(diào)度技術(shù)及其應(yīng)用［M］.北京：中國電力出版社，2010.

［16］ 雷德明，嚴新平.多目標智能優(yōu)化算法及其應(yīng)用［M］.北京：科學出版社，2009.

［17］ Ishibuchi H.Balance Between Genetic Search and Local Search in Memetic Algorithms for Multi-objective Permutation Flow Shop Schedul-ing［J］.IEEE Transactions on Evolutionary Computa-tion，2003，7（2）：204-223.

［18］ Konak A.Multi-objective Optimization Using Genetic Algorithm s：A Tutorial［J］.Reliability Engineering and System Safety 2006，91（1）：992-1007.

［19］ Hughes E J.Evolutionary M any-objective Optimization：Many Once or One Many［C］//Proceedings of IEEE Congress on Evolutionary Computation.Edinburgh，UK：IEEE Service Center，2005：222-227.

［20］ Abraham A，Jain L.Evolutionary Multi-objective Optimization［M］.［S.1］：Springer，2006：18-20.

［21］ Gong Maoguo.Multi-objective Immune Algorithm with Nondominated Neighbor-based Selection［J］.Evolutionary Computa-tion，2008，16（2）：225-255.

［22］ 齊學梅，羅永龍.求解流水車間調(diào)度問題的混合粒子群算法［J］.計算機工程與應(yīng)用，2012，48（9）：33-39.

編輯 索書志

Multi-objective Flow Shop Schedule Based on Grey Entropy Parallel Analysis Optimization Algorithm

ZHU Guangyu，HE Lijun
（College of Mechanical Engineering&Automation，F(xiàn)uzhou University，F(xiàn)uzhou 350108，China）

This paper establishes a multi-objective Flow Shop schedule optimization model under the environment of supply chain and optimized with the Grey Entropy Parallel Analysis（GEPA）method.Based on the grey relational analysis method，which expresses the similar degree between sequences，the information entropy theory is adopted to establish grey entropy parallel analysis method.The Grey Entropy Parallel Relational Degree（GEPRD）deduced by this method is used to measure the similar degree between multi-objective Pareto solutions and ideal solution and is used as the fitness to guide the evolution of the algorithm.By this way，the shortcoming that assignment the target weight directly in multi-objective optimization problem is overcome.The Genetic Algorithm based on Grey Entropy Parallel Analysis（GEPA-GA）is established.Experimental results show that GEPA-GA can solve high-dimensional multi-objective Flow Shop schedule problem under the environment of supply chain effectively.The multi-objective optimal solution and performance evaluation index of GEPA-GA are all superior to Genetic Algorithm based on Random Weighting（RWGA）.

supply chain；multi-objective Flow Shop；Grey Entropy Parallel Analysis（GEPA）method；Grey Entropy Parallel Relational Degree（GEPRD）；multi-objective optimization；Genetic Algorithm（GA）

朱光宇，賀利軍.基于灰熵并行分析優(yōu)化算法的多目標流水車間調(diào)度［J］.計算機工程，2015，41（10）：165-170.

英文引用格式：Zhu Guangyu，He Lijun.Multi-objective Flow Shop Schedule Based on Grey Entropy Parallel Analysis Optimization Algorithm［J］.Computer Engineering，2015，41（10）：165-170.

1000-3428（2015）10-0165-06

A

TP18

福州市科技計劃基金資助項目（2012-G-131）；福建省教育廳科技計劃基金資助項目（JK 2013006）；福建省自然科學基金資助項目（2014J01183）。

朱光宇（1970-），男，教授、博士，主研方向：多目標優(yōu)化；賀利軍，碩士研究生。

2014-09-22

2014-11-15E-m ail：zhugy@fzu.edu.cn