朱光宇，賀利軍

（福州大學(xué)機(jī)械工程及自動(dòng)化學(xué)院，福州 350108）

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

朱光宇，賀利軍

（福州大學(xué)機(jī)械工程及自動(dòng)化學(xué)院，福州 350108）

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

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

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

1 概述

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

化調(diào)度問(wèn)題進(jìn)行求解。

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）均值化

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

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

（2）求兩級(jí)最大差和最小差：

其中，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)度值計(jì)算的是灰關(guān)聯(lián)系數(shù)的平均值，這容易導(dǎo)致信息丟失；同時(shí)灰關(guān)聯(lián)度值具有局部關(guān)聯(lián)傾向，傾向于灰關(guān)聯(lián)系數(shù)大的目標(biāo)。針對(duì)這2個(gè)弱點(diǎn)，引入信息熵內(nèi)容，計(jì)算多目標(biāo)解各子目標(biāo)的熵值權(quán)重，與灰關(guān)聯(lián)分析法結(jié)合成灰熵并行分析法，以期克服灰關(guān)聯(lián)分析的弱點(diǎn)。

（1）計(jì)算式（1）中Pareto解序列均值化后各子目標(biāo)所占比重，即：

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

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

（2）計(jì)算Pareto解序列各子目標(biāo)的信息熵：

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

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

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

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

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

3 問(wèn)題描述及多目標(biāo)模型

3.1 問(wèn)題描述

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

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

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

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

本文問(wèn)題是確定工件加工順序，使工件最大完工時(shí)間、最大拖期時(shí)間、總流程時(shí)間、總庫(kù)存成本和總拖期成本5個(gè)目標(biāo)最小。

3.2 多目標(biāo)模型

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

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

4 多目標(biāo)Flow Shop調(diào)度問(wèn)題

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

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

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

步驟3 選擇操作。采用二元錦標(biāo)賽［17］方法進(jìn)行選擇。

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

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

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

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

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

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

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

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

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

5.2 評(píng)價(jià)指標(biāo)

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

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

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

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

其中，Wmax為外部檔案?jìng)€(gè)體數(shù)；FHM（j）為外部檔案?jìng)€(gè)體j的第M個(gè)目標(biāo)的值；fM（0）為理想解的第M個(gè)目標(biāo)的值。

5.3 結(jié)果分析

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

表1 16個(gè)問(wèn)題實(shí)例的仿真結(jié)果

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

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

表2 2種算法的性能評(píng)價(jià)指標(biāo)結(jié)果

6 結(jié)束語(yǔ)

本文提出采用灰熵并行分析法進(jìn)行多目標(biāo)優(yōu)化。建立基于灰熵并行分析的遺傳算法，以灰熵并行關(guān)聯(lián)度作為適應(yīng)度引導(dǎo)算法進(jìn)化，優(yōu)化供應(yīng)鏈環(huán)境下多目標(biāo)Flow Shop調(diào)度問(wèn)題。仿真實(shí)驗(yàn)結(jié)果表明，灰熵并行分析法與遺傳算法可有效結(jié)合，基于灰熵并行分析的遺傳算法可以有效解決供應(yīng)鏈環(huán)境下多目標(biāo)Flow Shop調(diào)度問(wèn)題，顯示出了灰熵并行分析法在解決高維多目標(biāo)優(yōu)化問(wèn)題的優(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］.同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，39（5）：726-731.

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

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

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

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

［8］ 胡桂武.基于廣義遺傳粒子群優(yōu)化算法的供應(yīng)鏈優(yōu)化求解［J］.計(jì)算機(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］.北京：清華大學(xué)出版社，2003.

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

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

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

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

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

［16］ 雷德明，嚴(yán)新平.多目標(biāo)智能優(yōu)化算法及其應(yīng)用［M］.北京：科學(xué)出版社，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］ 齊學(xué)梅，羅永龍.求解流水車間調(diào)度問(wèn)題的混合粒子群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48（9）：33-39.

編輯 索書(shū)志

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)化算法的多目標(biāo)流水車間調(diào)度［J］.計(jì)算機(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

福州市科技計(jì)劃基金資助項(xiàng)目（2012-G-131）；福建省教育廳科技計(jì)劃基金資助項(xiàng)目（JK 2013006）；福建省自然科學(xué)基金資助項(xiàng)目（2014J01183）。

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

2014-09-22

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