王 宇 張聞強(qiáng)(河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院 河南 鄭州 450001)

0 引 言

調(diào)度問題研究是將具有相關(guān)具有約束條件的有限資源，按照問題實(shí)際需求合理配給一個或者多個目標(biāo)對象。流水車間調(diào)度問題FSP(Flow shop scheduling problem)是一類經(jīng)典的多目標(biāo)調(diào)度問題，按照實(shí)際工業(yè)生產(chǎn)需求約束后的數(shù)學(xué)建模，屬于NP-hard問題，在工業(yè)自動化領(lǐng)域廣泛存在。其中以最短拖期與總完工時(shí)間為雙目標(biāo)的調(diào)度問題意在合理地排列出機(jī)器、工件、時(shí)間等資源分配，有效率地滿足自動化生產(chǎn)過程中經(jīng)濟(jì)或性能[1]。在1954年，F(xiàn)SP由Johnson等[2]提出，在此之后大量的論文提出了不同的方法，試圖確定更好的工作序列。平衡找到高品質(zhì)的解決方案，而且消耗合理的計(jì)算時(shí)間。

近年來在工業(yè)自動化領(lǐng)域，眾多學(xué)者針對不同目標(biāo)的FSP問題進(jìn)行了廣泛的探討。研究單臺機(jī)器混合型車間調(diào)度問題提出分支綁定算法，強(qiáng)調(diào)特殊情況下的啟發(fā)式或最優(yōu)解，盡量減少制造時(shí)間[3]。流程車間調(diào)度問題是典型的組合優(yōu)化問題、解集復(fù)雜、數(shù)據(jù)量大、結(jié)果中通常不存在最優(yōu)解，學(xué)者針對問題對最新的智能計(jì)算算法：混合遺傳算法、粒子群優(yōu)化和貓群優(yōu)化算法的四個元學(xué)說的實(shí)驗(yàn)比較研究[4]。Gao等[5]提出兩種建構(gòu)性啟發(fā)式方法，嵌入局部搜索和修改迭代算子，改進(jìn)了混合啟發(fā)式算法，在約束條件下最大可能地降低調(diào)度的總流程時(shí)間。然而，單目標(biāo)的研究已不能滿足當(dāng)下制造自動化的生產(chǎn)環(huán)境，多重約束下的有限資源分配成為主流。為了彌補(bǔ)單一智能算法的弊端，結(jié)合不同算法的優(yōu)勢。在犧牲一定程度時(shí)間復(fù)雜度的情況下，學(xué)者對經(jīng)典的演化算法進(jìn)行組合?；旌喜煌乃惴ㄊ蛊渚哂邢嚓P(guān)父代算法的優(yōu)勢特性，針對實(shí)際環(huán)境優(yōu)化后應(yīng)用前景更加廣泛。楊開兵等[6]根據(jù)成組工件的FSP問題，在保持種群的多樣性與收斂性能上分別引入適應(yīng)度計(jì)算策略和進(jìn)行局部搜索。何啟巍基于粒子群優(yōu)化算法的特點(diǎn)，加入一種變鄰域搜索策略，極大地提高了解的分布性，混合算法用于對調(diào)度問題進(jìn)行求解，提高了解集的范圍[7]。陳可嘉等[8]通過對經(jīng)典的NSGA-Ⅱ算法進(jìn)行改進(jìn)，仿真生物食物鏈策略，算法收斂性能有所提高。

差分進(jìn)化算法DE(Differential Evolution)用于解決實(shí)數(shù)優(yōu)化問題，在1997年由Storn等[9]提出，是一種先變異，后交叉的啟發(fā)式全局搜索算法，由于采用浮點(diǎn)數(shù)編碼，算法解析容易實(shí)現(xiàn)，對連續(xù)空間具有高效的全局搜索能力。標(biāo)準(zhǔn)差分算法文檔中使用錦標(biāo)賽選擇，便于實(shí)現(xiàn)，遺傳方式與眾多智能算法相同。差分算法的主要策略在于變異操作方式，帶有方向目標(biāo)性，區(qū)別種群中優(yōu)勢的個體，使得其他個體根據(jù)決策者的需要以優(yōu)勢個體為前提進(jìn)行一定的擾動，實(shí)現(xiàn)個體變異，得到下一代。差分策略根據(jù)種群分布的特點(diǎn)，讓優(yōu)秀的個體成為“榜樣”，避免傳統(tǒng)遺傳算法隨機(jī)“盲目”式的變異方式，提高算法的搜索能力。現(xiàn)在，基于差分進(jìn)化算法被廣泛應(yīng)用到數(shù)據(jù)挖掘、自動化、機(jī)械工程等各個領(lǐng)域。同時(shí)，也延伸于多目標(biāo)優(yōu)化與調(diào)度問題。針對最小化最大完成時(shí)間問題，提出自適應(yīng)鄰域搜索差分演化(NS-SGDE)基于概率模型的指導(dǎo)代理，以指導(dǎo)DE的探索階段來產(chǎn)生后代[10]。差分算法過快的收斂速度容易陷入局部最優(yōu)。通過設(shè)定自適應(yīng)縮放因子，建立分布模型，對種群進(jìn)化過程中的優(yōu)勢個體進(jìn)行統(tǒng)計(jì)，自適性的改變選擇方式，有效地防止子代陷入局部最優(yōu)[11]?？勺冟徲?DEVNS)搜索在收斂性方面具有很強(qiáng)的優(yōu)勢，結(jié)合可變鄰域的差分演化算法來解決流水車間調(diào)度問題具有很高的競爭力[12]。張曉霞等運(yùn)用基于概率模型的分布估計(jì)算法，避免算法陷入局部最優(yōu)，求解混合零空閑置換流水車間問題[13]。

向量評估算法VEGA(Vector evaluated genetic algorithm)[14]利用并行方式解決多目標(biāo)優(yōu)化問題，根據(jù)多目標(biāo)子函數(shù)設(shè)立不同后代、分層成比例的選擇機(jī)制，獨(dú)立種群按照決策者需要可以進(jìn)行獨(dú)立遺傳操作或者融合進(jìn)化。不同的后代群體朝著不同的方向進(jìn)化，這種特性表現(xiàn)出很強(qiáng)的朝著Pareto前沿面的邊緣區(qū)域收斂的能力，同時(shí)分布性不好。一種基于Pareto支配與被支配關(guān)系的適應(yīng)度函數(shù)PDDR-FF(Pareto dominating and dominated relationship-based fitness function)[15]用來判斷個體之間的區(qū)別。PDDR-FF函數(shù)針對個體的支配信息對其優(yōu)劣程度與位置進(jìn)行區(qū)別劃分，根據(jù)個體支配數(shù)與被支配數(shù)賦予不同的數(shù)值。個體在Pareto前沿面分為中心區(qū)域與邊緣區(qū)域，其中中心區(qū)域的可支配面積比邊緣區(qū)域要大。PDDR-FF的特點(diǎn)促使個體朝著具有更大支配數(shù)的優(yōu)勢方向前進(jìn),也就是表現(xiàn)為朝著具有更大支配面積的中心區(qū)域進(jìn)化?；旌喜蓸訖C(jī)制不僅具有良好的收斂性能，同時(shí)保護(hù)了種群的分布性?；诨旌喜蓸硬呗缘亩嗄繕?biāo)進(jìn)化算法HSS-MOEA(Multi-objective hybrid evolutionary algorithm)與NSGA-Ⅱ和SPEA2相比，混合采樣后的算法在收斂和分布性能上要好，在時(shí)間消耗、運(yùn)算效率上，也優(yōu)于傳統(tǒng)遺傳算法[16]。

混合采樣策略不僅具有VEGA偏好邊緣區(qū)域的優(yōu)勢，同時(shí)具有朝Pareto前沿的邊緣區(qū)域收斂的能力，而DE對精英解進(jìn)一步優(yōu)化。本文在HSS-MOEA的基礎(chǔ)上引入差分策略，設(shè)計(jì)混合算法框架及變異操作中備選個體的選擇策略。以此提出多目標(biāo)混合差分進(jìn)化算法(HMODE)來解決復(fù)合FSP問題。混合算法保留了收斂速度和分布性能，以及DE提高HSS-MOEA應(yīng)用后的效率性。

1 問題描述

流程車間調(diào)度可以描述如下：在集合J={J1，J2，…，Jn}里有n個工件。在不同的m個機(jī)器{M1，M2，…，Mm}進(jìn)行處理。模擬機(jī)器工件在機(jī)器上的操作順序進(jìn)行處理，則Oji被定義為作業(yè)Ji的第i個操作，并且機(jī)器Mi上的Oji的處理時(shí)間是Pji。目標(biāo)是找到一套相對最優(yōu)的解決方案，最大限度地減少加工時(shí)間和最大延遲。

令π=(π(1)，π(2)，…，π(1))是作業(yè)的某一組操作順序，πa是排列π的運(yùn)動作業(yè)，n是作業(yè)數(shù)。U表示所有可能的過程組合，π∈U。Ci(j)表示機(jī)器Mi上作業(yè)πj的總完成時(shí)間，tji是機(jī)器Mi上的操作完成時(shí)間。如果在機(jī)器Mi上處理操作Oji，則xji=1，否則，xji=0;如果在Okh之前操作Oji，則yjikh=1，否則yjikh=0。FSP的數(shù)學(xué)公式可以描述如下：

(1)

j=2,3,…,ni=2,3,…,m

以最大完工時(shí)間為目的的FSP是從解集U找到一組序列π*:

(2)

所有約束條件如下：

(3)

解決最小化最大拖期與最小化總完工時(shí)間的多目標(biāo)流水車間調(diào)度問題要保證在同一時(shí)間里一個工件只能在一臺機(jī)器上加工，約束條件要保證一臺機(jī)器在某一個工作時(shí)間內(nèi)只能加工一個工件，所有工件加工順序相同。約束條件式(3)中前四個公式表示所有機(jī)器的作業(yè)加工訂單，分別確保加工排列的可行性，作業(yè)的唯一性和機(jī)器的獨(dú)特性。其余方程定義約束條件為非負(fù)。

求解最小化最大拖期是FSP中最常見的問題。假設(shè)Tmax(π)是序列π的最大拖期時(shí)間，Tπ(j)和Dπ(j)分別表示作業(yè)π(j)的拖期和項(xiàng)目時(shí)間。項(xiàng)目時(shí)間由“廠商”確定。類似地，F(xiàn)SP的最大拖期數(shù)學(xué)描述標(biāo)準(zhǔn)如下：

(4)

最大拖期與最大完工時(shí)間雙優(yōu)化目標(biāo)流水車間調(diào)度問題可以形式化為：

min{Cmax(π),Tmax(π)}π∈U

(5)

2 混合多目標(biāo)進(jìn)化算法與差分演化策略結(jié)合

2.1 算法框架

本研究基于多目標(biāo)混合采樣進(jìn)化算法，算法在同時(shí)保證收斂性能和分布性能的前提下，時(shí)間復(fù)雜度盡量降低。在此基礎(chǔ)上，混合DE算法對精英種群進(jìn)行處理，謀求進(jìn)一步提高最優(yōu)解集的收斂性和分布性，提高算法的性能?；旌纤惴朔渭僁E算法對于問題的局部搜索能力弱、搜索效率低的弊端，并重新設(shè)計(jì)問題編碼方式、遺傳操作中對備選個體的選擇策略以及參數(shù)設(shè)置。促使混合后的算法在Pareto前沿面的各個方向，盡可能地向著真實(shí)Pareto前沿面收斂并且均勻分布，以彌補(bǔ)單一算法的不足，提升算法的效力和效率。

算法大致框架如圖1所示，以t代HMODE的演進(jìn)過程為例。A(t)表示精英解集，作為第t代的精英保留策略，P(t)代表第t代種群。初始化參數(shù)，設(shè)置結(jié)束條件。一代的解決過程包括5個階段。

圖1 算法流程圖

1) 第一階段：VEGA采樣策略 在這個階段，利用VEGA采樣策略選擇優(yōu)秀個體，利用對Pareto前沿面邊界地區(qū)的強(qiáng)收斂能力依據(jù)目標(biāo)函數(shù)把P(t)分割成子代種群Sub1-P(t)與Sub2-P(t)。子代種群只考慮單一目標(biāo)演化，是單目標(biāo)最優(yōu)解集，按照降序排列。VEGA特性選擇出來的優(yōu)秀個體處于Pareto前沿面邊界處。

2) 第二階段：融合交配池(混合采樣) VEGA對Pareto前沿面邊緣區(qū)域處的搜索能力很好，多個子種群同時(shí)搜索導(dǎo)致單個個體的多樣性欠佳，原因就在于它的選擇偏好。在研究中，采樣得到的單個目標(biāo)子種群與精英種群A(t)的組合，形成一個交配池Mating Pool。在交配池中，以一個目標(biāo)存儲好優(yōu)秀個體子種群Sub1-P(t)，子種群Sub2-P(t)為另一個目標(biāo)擁有優(yōu)秀個體，而精英種群基于PDDR-FF適應(yīng)度函數(shù)選擇后具有多目標(biāo)最優(yōu)解，位于Pareto前沿面中心區(qū)域。因此，在交配池中，三分之一的個體服務(wù)于一個目標(biāo)，三分之一是另一個目標(biāo)，最后三分之一是兩個目標(biāo)，如圖2所示。

圖2 混合采樣

3) 第三階段：重構(gòu) 交叉操作是遺傳算法的主要操作。只有通過連續(xù)交叉，才能生產(chǎn)新的個體，獲得好的解集，突變算子是保持解的多樣性。在傳統(tǒng)解決FSP問題方式上，基于問題特性通常采用染色體編碼。本文引入差分進(jìn)化策略，對問題編碼進(jìn)行實(shí)數(shù)化。從二進(jìn)制編碼的思想出發(fā)，使用模擬二進(jìn)制交叉SBX(simulated binary crossover)與(polynomial mutation)多項(xiàng)式變異。

SBX交叉模擬二進(jìn)制串單點(diǎn)交叉共享重心的屬性特點(diǎn)，交叉生成的子代個體與父代的重心對稱。SBX交叉對于實(shí)數(shù)編碼具有很高的穩(wěn)定性。βi是隨機(jī)數(shù)。

(6)

ci與pi分別表示第i個基因位的子代與父代個體。SBX模擬二進(jìn)制碼單點(diǎn)交叉的共享重心特性，對于子代個體與父代個體每一個變量盡可能地使βi=1，保證了后代與雙親的重心對稱。

變異操作使用基于多項(xiàng)式分布的多項(xiàng)式變異方法。不均勻的方式改變個體，服從兩個原則：突變體應(yīng)隨機(jī)抽樣；隨著算法的演化過程，突變的程度將會減少。

使用均勻分布U～(0，1)生成多項(xiàng)式分布數(shù)ξ。

(7)

第i個變量變異方式如下：

(8)

ξj是由式(7)生成的多項(xiàng)式分布隨機(jī)數(shù)。Δmax是xj的最大允許攝動。

4) 第四階段：精英保留策略 精英保留思想要把優(yōu)秀的個體作為“榜樣”傳遞到下一代，直到替換。A(t)作為優(yōu)秀種群在一定程度上代表著當(dāng)代最好的那一批個體，算法最后輸出也是這個集合。精英種群和P(t+1)混合成臨時(shí)種群temp-A(t)后按照PDDR-FF值適應(yīng)度值排序。根據(jù)PDDR-FF性質(zhì)，函數(shù)值越小越好，支配的面積大，其適應(yīng)度值不超過1。同時(shí)，被支配個體的適應(yīng)度值將超過1。此外，即使對于所有非支配個體，它們也具有不同的PDDR-FF值。非支配的個體根據(jù)位置分為邊緣區(qū)域(接近1)和中心區(qū)域(接近0)。

計(jì)算PDDR-FF適應(yīng)度值排序后，按照種群設(shè)置大小，選擇出|A(t)|個體作為temp-A(t+1)。temp-A(t)中的個體被復(fù)制形成temp-A(t+1)。這種個體保留機(jī)制類似于精英抽樣策略，基于PDDR-FF函數(shù)特點(diǎn)保證解集合處于Pareto中心區(qū)域。

5) 第五階段：差分優(yōu)化策略 更新解集以獲取臨時(shí)種群temp-A(t+1)后，應(yīng)用差分進(jìn)化策略對temp-A(t+1)進(jìn)行優(yōu)化。經(jīng)過DE的突變和交叉運(yùn)算后創(chuàng)建臨時(shí)種群temp-A′(t+1)。此時(shí)的臨時(shí)種群不僅有著上一代優(yōu)秀的個體，同時(shí)包含根據(jù)“榜樣”個體引導(dǎo)獲得的下一代。融合后按照決策者對問題的需要選擇下一代真實(shí)精英種群A(t+1)。與傳統(tǒng)DE不同，應(yīng)用與HSS-MOEA相同的優(yōu)秀個體保持機(jī)制，對種群進(jìn)行區(qū)域劃分，依據(jù)PDDR-FF值更新解集。

2.2 混合差分策略

DE不僅加強(qiáng)算法在Pareto前沿面中心區(qū)域和邊界區(qū)域的搜索能力，而且有助于彌補(bǔ)在過于強(qiáng)調(diào)中心和邊界區(qū)域的搜索帶來的剩余區(qū)域搜索能力不足的缺陷。但是需要根據(jù)問題背景的特殊性和復(fù)雜性來設(shè)計(jì)差分策略進(jìn)入的時(shí)機(jī)。此時(shí)機(jī)需要克服單純DE算法基于問題的局部搜索能力弱、搜索效率低的弊端。Pareto前沿面上個體代表著當(dāng)代優(yōu)秀的種群，作為目標(biāo)向量，向著真實(shí)的Pareto前沿面搜索有利于提升算法的收斂性能；或者沿著當(dāng)前Pareto前沿面搜索將有利于提升算法的均勻分布性能。

變異操作中備選個體的選擇策略?；贒E算法，需要根據(jù)當(dāng)前個體、備選個體個數(shù)和方向以確定搜索起點(diǎn)、步長和方向。這些個體的選擇策略直接決定了新生成個體的收斂和分布性能。擬采用的變異操作根據(jù)當(dāng)前個體的適應(yīng)度評價(jià)函數(shù)值為DE/rand/1，仿真結(jié)果采取的設(shè)置如下：

Ui=X3+F(X1-X2)

(9)

依據(jù)支配關(guān)系把Pareto前沿面可劃分邊界區(qū)域與中心區(qū)域。對于初始精英解集temp-A(t+1)獲得差分演化算子，隨機(jī)選擇三個不同的個體。根據(jù)PDDR-FF值，保證選擇的個體eval(X1)

圖3 收斂性

圖4 分布性

模式一：X1與X2位于帕累托前沿面相同的區(qū)域時(shí)，不考慮X3個體位置，進(jìn)化方向有助于提高解集的收斂性能。

模式二：X1與X2位于帕累托前沿面不同的區(qū)域時(shí)，個體進(jìn)化有助于提高解集的均勻分布性能。

被選最差個體位于中心區(qū)域，最優(yōu)個體分布邊界區(qū)域時(shí)，個體朝兩邊進(jìn)化。

只表示單個目標(biāo)的優(yōu)勢個體集中在邊界處，具有多目標(biāo)的最優(yōu)個體位于中心區(qū)域，個體朝中心處移動。

混合算法框架如圖3所示，改進(jìn)了遺傳算法，根據(jù)問題的特征采用實(shí)數(shù)編碼引入了DE策略對精英個體進(jìn)行優(yōu)化處理，使得算法的收斂性有了較大的改進(jìn)。加入自適應(yīng)密度評價(jià)函數(shù)PDDR-FF，對前沿面分塊化，彌補(bǔ)了遺傳算法容易陷入局部最優(yōu)解的缺點(diǎn)，加強(qiáng)了全局搜索的能力，使得算法能夠向多個方向演變，并在算法中根據(jù)問題相關(guān)的偏好信息設(shè)計(jì)DE策略執(zhí)行時(shí)期，提高算法的搜索速度。算法偽代碼如下所示。

算法1

HMODA?DEforMOPsStep0 Initialization：Sett=0，P(t)和A(t)Step1 Reprodution：1．1PartitionP(t)intoSub?P1(t)andSub?P2(t)byVEGA1．2TheSub?P1(t)，Sub?P2(t)andA(t)mixedintoMatingpool1．3P(t+1)wereobtainedfromthematingbycrossoverandmutationStep2 Differentialevolution：2．1TheA(t)andP(t+1)generatetemp?A(t+1)byelitistretentionstrategy2．2X1，X2andX3selectedfromtemp?A(t+1)．Accordingto?thepropertiesofPDDR?FFfunction，temp?A′(t+1)wereobtainedbydifferentialevolution．Step3 Selection：SelectA(t+1)fromtemp?A(t+1)Utemp?A′(t+1)Step4 StoppingCondition：Ifthestoppingconditionismet，stop；otherwise，sett=t+1andgotoStep1．

3 實(shí)驗(yàn)與結(jié)論

為驗(yàn)證算法可靠性，實(shí)驗(yàn)數(shù)據(jù)來源于Taillard[17]提出的其中10個隨機(jī)生成的調(diào)度問題，數(shù)據(jù)規(guī)模對應(yīng)于工業(yè)問題的實(shí)際尺寸。分別為20×5、20×10、20×20，對應(yīng)為20個工件。有5臺、10臺以及20臺機(jī)器。目的是最小化完工時(shí)間與最小化最大拖期的雙目標(biāo)。所有的仿真都在Core i5處理器(3.3 GHz)上執(zhí)行，內(nèi)存為8 GB。程序?yàn)镴AVA語言編寫。HMODE和HSS-MOEA使用相同的編碼和遺傳操作，具體參數(shù)值如下：種群大小=100;最大代數(shù)=500;檔案大小=50;交叉概率=0.90;突變概率=1/變量數(shù)，編碼方法是實(shí)數(shù)編碼。有20個變量。DE交叉概率=0.5，F(xiàn)=0.5。運(yùn)行30次HMODE和HSS-MOEA以比較結(jié)果。在這項(xiàng)研究中，驗(yàn)證收斂性通過比較解集中的個體與參考點(diǎn)在目標(biāo)空間中所圍成的超立方體的體積HV(Hypervolume)指標(biāo)，比較父代與子代之間的距離的GD(generational distance)指標(biāo)。分布性通過多元化度量DM(Diversification Metric)和SP(Spacing)，比較當(dāng)前點(diǎn)的每個成員與其最近的鄰居的范圍(距離)的差異，DM通過個體與其他個體的最大歐式距離來評價(jià)，有效地評測解集的分布性。

實(shí)驗(yàn)數(shù)據(jù)Box箱線圖如圖5與圖6所示。表1與表2分別表示SP、DM和HV、GD指標(biāo)的平均值和方差。表中顯示，HMODE的分布優(yōu)于HSS-MOEA，表明DE促進(jìn)了進(jìn)一步演變。與HSS-MOEA相比，HMODE在收斂方面具有優(yōu)勢。由于使用差分策略，編碼方案使用實(shí)數(shù)編碼。HSS-MOEA和HMODE的時(shí)間復(fù)雜度高于順序編碼。同時(shí)，HMODE在計(jì)算上有不止一個步驟，消耗更多的時(shí)間資源。

圖5 收斂性評測：HV與GD指標(biāo)

圖6 分布性評測：DM和SP指標(biāo)

表1 DM 和 SP指標(biāo)的均值與標(biāo)準(zhǔn)差

表2 HV和GD指標(biāo)的均值與標(biāo)準(zhǔn)差

對于算法的效率，與傳統(tǒng)遺傳算法相比較可以從兩方面來討論。1) 距離計(jì)算方面，NSGA-Ⅱ時(shí)間復(fù)雜度為O(mNlogN)；SPEA2計(jì)算復(fù)雜度為O(mN2logN)；由于沒有距離計(jì)算機(jī)制，因此HSS-MOEA與HMODE的時(shí)間復(fù)雜度為O(0)。2) 在適應(yīng)度計(jì)算方面，HSS-MOEA與HMODE采用基于支配關(guān)系的混合采樣，需要進(jìn)行PDDR-FF值的計(jì)算。對于種群中m個目標(biāo)，N個個體的PDDR-FF值的計(jì)算，總的比較次數(shù)可以按照下式計(jì)算：

m(N-1)+m(N-2)+…+m×2+m×1=mN(N-1)/2

(10)

因此，需要進(jìn)行mN(N-1)/2次比較來計(jì)算PDDR-FF的值，HSS-MOEA的時(shí)間復(fù)雜度為O(mN2)；NSGA-Ⅱ與SPEA2時(shí)間復(fù)雜度同樣為O(mN2)。由于HMODE引入DE計(jì)算，對每代精英種群進(jìn)行優(yōu)化處理，假設(shè)精英種群大小也為N，染色體長度為C。首先進(jìn)行PDDR-FF排序，時(shí)間復(fù)雜度為O(mN2)。更新精英解集的最差時(shí)間復(fù)雜度為O(NC)。則HSS-MOEA的時(shí)間按復(fù)雜度為O(mN2)+O(mN2)+O(NC)。綜上所述，HSS-MOEA的運(yùn)算速度要比NSGA-Ⅱ與SPEA2快，HMODE比HSS-MOEA要慢，隨著實(shí)際問題規(guī)模的增大，染色體長度C越大。與傳統(tǒng)遺傳算法相比時(shí)間復(fù)雜度上優(yōu)勢不明顯，但收斂性與分布性上則進(jìn)一步提高。以FSP01(20×5)為例，HSS-MOEA時(shí)間消耗的均值有標(biāo)準(zhǔn)差為：1.49e+011.6e+01，HMODE則為4.89e+021.9e+01。

4 結(jié) 語

在本文中，為解決最大完工時(shí)間和最小化最大拖期雙目標(biāo)流水車間調(diào)度問題，一種結(jié)合差分進(jìn)化策略與混合采樣策略的多目標(biāo)優(yōu)化算法HMODE被提出?；旌喜蓸硬呗詫σ罁?jù)種群個體的函數(shù)值與支配關(guān)系在Pareto前沿面進(jìn)行排序與區(qū)域劃分，融合差分進(jìn)化思想，引導(dǎo)每一代的進(jìn)化方向。此外，DE操作對精英解集的處理，使得解在收斂到真正的Pareto前沿面的能力更大。數(shù)值比較表明，HMODE在收斂性和分布性上優(yōu)于HSS-MOEA。

[1] 王萬良. 生產(chǎn)調(diào)度智能算法及其應(yīng)用[M]. 科學(xué)出版社, 2007.

[2] Johnson S M.Optimal two- and three-stage production schedules with setup times included[J].Naval Research Logistics Quarterly,1954,1(1):61- 68.

[3] Wang S, Liu M, Chu C. A branch-and-sbound algorithm for two-stage no-wait hybrid flow-shop scheduling[J]. International Journal of Production Research, 2015, 53(4):1143- 1167.

[4] Bouzidi A, Riffi M E, Barkatou M. A comparative study of four metaheuristics applied for solving the flow-shop scheduling problem[C]// World Congress on Information and Communication Technologies. IEEE, 2015:140- 145.

[5] Gao K, Pan Q, Suganthan P N, et al. Effective heuristics for the no-wait flow shop scheduling problem with total flow time minimization[J]. International Journal of Advanced Manufacturing Technology, 2013, 66(9- 12):1563- 1572.

[6] 楊開兵, 劉曉冰. 無成組技術(shù)條件下流水車間調(diào)度的多目標(biāo)優(yōu)化[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2009, 15(2):348- 355.

[7] 何啟巍, 張國軍, 朱海平,等. 一種多目標(biāo)置換流水車間調(diào)度問題的優(yōu)化算法[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用, 2013, 22(9):111- 118.

[8] 陳可嘉, 周曉敏. 多目標(biāo)置換流水車間調(diào)度的改進(jìn)食物鏈算法[J]. 中國機(jī)械工程, 2015, 26(3): 348- 353,360.

[9] Storn R,Price K.Differential Evolution—A Simple and Efficient Heuristic for global Optimization over Continuous Spaces[J].Journal of Global Optimization, 1997, 11(4):341- 359.

[10] Shao W,Pi D.A self-guided differential evolution with neighborhood search for permutation flow shop scheduling[J]. Expert Systems with Applications, 2016, 51:161- 176.

[11] 劉紅平,黎福海. 面向多目標(biāo)優(yōu)化問題的自適應(yīng)差分進(jìn)化算法[J]. 計(jì)算機(jī)應(yīng)用與軟件,2015,32(12):249- 252,269.

[12] Yi W,Gao L,Zhou Y,et al.Differential evolution algorithm with variable neighborhood search for hybrid flow shop scheduling problem[C]// IEEE,International Conference on Computer Supported Cooperative Work in Design.IEEE, 2016:233- 238.

[13] 張曉霞, 呂云虹. 一種求解混合零空閑置換流水車間調(diào)度禁忌分布估計(jì)算法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2017, 34(1):270- 274.

[14] Schaffer J D. Multiple Objective Optimization with Vector Evaluated Genetic Algorithms[C]// International Conference on Genetic Algorithms. L. Erlbaum Associates Inc. 1985:93- 100.

[15] Zhang W,Gen M,Jo J.Hybrid sampling strategy-based multiobjective evolutionary algorithm for process planning and scheduling problem[J]. Journal of Intelligent Manufacturing, 2014, 25(5):881- 897.

[16] 張聞強(qiáng), 盧佳明, 張紅梅. 流水車間調(diào)度問題的快速多目標(biāo)混合進(jìn)化算法[J]. 計(jì)算機(jī)應(yīng)用, 2016, 36(4):1015- 1021.

[17] Taillard E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research, 1993, 64(2):278- 285.