陳永燦 劉 宇 周艷平

（青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院，山東 青島 266061）

車間調(diào)度問題是典型的NP-Hard 問題，調(diào)度問題解決的好壞影響著企業(yè)對市場的反應(yīng)能力和競爭力。柔性作業(yè)車間調(diào)度問題[1]（flexible job-shop scheduling problem，F(xiàn)JSP）是對傳統(tǒng)作業(yè)車間調(diào)度問題更深入的研究，是比JSP 更復(fù)雜的NP-hard 問題。傳統(tǒng)的FJSP 研究主要集中在單目標(biāo)調(diào)度上，但多目標(biāo)FJSP 更貼近人們實(shí)際生產(chǎn)需求[2]。目前，求解多目標(biāo)優(yōu)化問題[3]（multi-objective optimization problem，MOP）的方法分為兩類：根據(jù)每個(gè)目標(biāo)函數(shù)的權(quán)重將MOP 轉(zhuǎn)換為單目標(biāo)問題；運(yùn)用Pareto 優(yōu)化策略[4]。

差分進(jìn)化算法[5]（differential evolution，DE）是Stom R 和Price K 提出的一種隨機(jī)的并行直接搜索算法，因其具有結(jié)構(gòu)簡單、易于實(shí)現(xiàn)、收斂速度快、魯棒性強(qiáng)等特點(diǎn)被學(xué)者們廣泛使用。郭麗[6]提出了一種自適應(yīng)DE 算法，通過對參數(shù)的改進(jìn)來解決MOP；侍倩[7]將混合選擇機(jī)制和Archive 群體更新應(yīng)用到DE 算法中，提高了DE 算法在解決MOP時(shí)搜索Pareto 最優(yōu)解的質(zhì)量與速度；張敬敏等[8]將混沌優(yōu)化策略與DE 算法相結(jié)合來解決算法早熟的問題，并在多目標(biāo)FJSP 中解決了收斂性能與早熟之間的矛盾；Wisittipanich W 等[9]為提高最優(yōu)解的質(zhì)量，用5 種具有不用搜索行為的變異策略解決MOP 問題；Qian B 等[10]將一種最小階值規(guī)則解決MOP 問題。在以上的研究中可以發(fā)現(xiàn)，學(xué)者們都是將DE 算法的參數(shù)進(jìn)行各種自適應(yīng)改進(jìn)或?qū)E算法與其他算法相融合，從而提高DE 算法性能。

本文介紹了多目標(biāo)柔性作業(yè)車間調(diào)度模型，提出了一種結(jié)合Pareto 支配關(guān)系的精英選擇策略和模擬退火（simulated annealing，SA）算法[11]的混合自適應(yīng)差分進(jìn)化（hybrid adaptive differential evolution，HADE）算法，通過測試函數(shù)證明了HADE 算法的優(yōu)良性能，并通過仿真實(shí)驗(yàn)證明了HADE 算法是解決多目標(biāo)FJSP 的有效方法。

1 多目標(biāo)FJSP 模型

1.1 多目標(biāo)FJSP 描述

FJSP 是研究如何在m臺(tái)機(jī)器上加工n個(gè)工件的問題。每個(gè)工件包含多道工序，工件的工序數(shù)量不一定相等；同一工件的工序之間有確定的加工順序；每道工序可在多臺(tái)機(jī)器上加工[12]。在確定工序的加工機(jī)器及工件加工順序的基礎(chǔ)上，實(shí)現(xiàn)對最大加工時(shí)間、最大機(jī)器負(fù)荷和總機(jī)器負(fù)荷等調(diào)度目標(biāo)的優(yōu)化。

為了便于描述模型，本文涉及的參數(shù)見表1。

表1 模型參數(shù)表

1.2 目標(biāo)函數(shù)及約束條件

本文模型共有3 個(gè)目標(biāo)函數(shù)。

（1）最小化最大加工時(shí)間：

（2）最小化機(jī)器最大負(fù)荷：

（3）最小化總機(jī)器負(fù)荷：

約束條件說明：

（1）一臺(tái)機(jī)器在某一時(shí)刻只能加工一道工序。

（2）任何工序在同一時(shí)刻只能被一臺(tái)機(jī)器加工。

（3）任何開始加工的工序不能被中斷。

（4）在零時(shí)刻，所有工件都可以加工，即所有工件具有相同優(yōu)先級(jí)。

（5）同一工件的工序之間有先后約束。

2 HADE 算法

2.1 編碼與初始化

HADE 算法采用一種整數(shù)編碼MSOS，由機(jī)器選擇（machine selection，MS）部分和工件排序（operations sequencing，OS）部分組成[13]。MS 部分中每個(gè)基因位用整數(shù)表示，依次按照工件和工件的工序順序進(jìn)行排列，每個(gè)整數(shù)表示當(dāng)前工序選擇的加工機(jī)器在可選機(jī)器集中的順序編號(hào)。OS 部分用工件號(hào)直接編碼，工件號(hào)的出現(xiàn)順序表示該工件工序的先后加工順序。與傳統(tǒng)的集成編碼、二進(jìn)制編碼等編碼方式相比，MSOS 編碼使染色體更易于表現(xiàn)，同時(shí)在進(jìn)行變異、交叉等行為時(shí)具有更強(qiáng)的操作性。

如圖1 所示，第一道工序可以選擇5 臺(tái)機(jī)器進(jìn)行加工，但其對應(yīng)的MS 部分的整數(shù)為3，則代表該工序所選擇的加工機(jī)器為其可選擇的5 臺(tái)機(jī)器中的第3 臺(tái)機(jī)器；OS 部分染色體為[1,2,3,1,1,3]，則表示的加工順序?yàn)镺11→O21→O31→O12→O13→O32。

圖1 MSOS 編碼

DE 算法采用隨機(jī)分布法產(chǎn)生初始種群，導(dǎo)致種群內(nèi)個(gè)體多樣性差，最優(yōu)解質(zhì)量與收斂速度并不理想。HADE 算法采用全局選擇（global selection，GS）、局部選擇（local selection，LS）和隨機(jī)選擇（random selection，RS）相結(jié)合的方式生成初始種群。GS 和LS 主要是為平衡被選擇的各臺(tái)機(jī)器的工作負(fù)荷，提高機(jī)器的利用率；RS 使初始種群分散于整個(gè)解空間。經(jīng)測試，將GS∶LS∶RS 以4∶4∶2的比例生成初始種群。

2.2 變異操作

變異操作通常是通過改變?nèi)旧w的某些基因，對染色體進(jìn)行較小的改動(dòng)來生成一個(gè)新個(gè)體，在增加種群的多樣性的同時(shí)也在一定程度上影響著算法的搜索能力。因HADE 算法采用MSOS 編碼方式，所以變異分為MS 部分變異和OS 部分變異。

MS 部分變異：在MS 部分中隨機(jī)選擇x個(gè)位置，依次將這些位置所選擇的機(jī)器設(shè)置為當(dāng)前工序可選加工機(jī)器中加工該工序用時(shí)最少的機(jī)器。

OS 部分變異：采用部分隨機(jī)變異。在OS 部分中隨機(jī)選擇一段基因，然后將這段基因重新排序后放回染色體中，如圖2 所示。

圖2 OS 部分變異

同時(shí)，變異算子F的取值大小對種群的進(jìn)化也有十分重要的影響。F過大時(shí)，個(gè)體變化較大，算法不容易收斂；F過小時(shí)，種群多樣性會(huì)降低，容易陷入局部最優(yōu)解。為提高算法的收斂速度，保證種群的多樣性，HADE 算法根據(jù)沈孝龍等[14]提出的一種自適應(yīng)差分進(jìn)化（adaptive differential evolution，ADE）算法進(jìn)行了一定的改進(jìn)，使F能夠隨著迭代的進(jìn)行由大變小。ADE 算法中F的取值范圍為[0.4,0.55]，與F的一般取值范圍[0,2]相比范圍較小，為進(jìn)一步提升進(jìn)化前期種群的多樣性，將F的取值范圍擴(kuò)大為(0.55,1]，提高了種群前期的變異能力，如圖3 所示。F具體公式如下：

圖3 自適應(yīng)變異算子對比圖

其中：Fmax=0.55；Fmin=0.4；，G為總迭代次數(shù)，m為當(dāng)前迭代次數(shù)。

2.3 交叉操作

DE 算法將變異后種群中的個(gè)體與原始種群中的個(gè)體進(jìn)行交叉操作，好的交叉操作在提高種群的多樣性的同時(shí)還能提高算法的收斂速度。HADE 算法的交叉操作分為MS 部分交叉和OS 部分交叉。

（1）MS 部分交叉

該部分交叉采用改進(jìn)的均勻交叉的方式，具體步驟如下：

①隨機(jī)生成一個(gè)大于1 并且小于所有工件的工序總數(shù)的整數(shù)l。

②按照隨機(jī)數(shù)l再隨機(jī)生成l個(gè)不相等的整數(shù)。

③根據(jù)步驟②中產(chǎn)生的l個(gè)整數(shù)，依次將原始種群染色體中對應(yīng)l個(gè)整數(shù)位置的基因覆蓋變異后種群染色體中對應(yīng)位置的基因。

（2）OS 部分交叉

采用改進(jìn)的POX 交叉方法，在每個(gè)染色體中對多個(gè)工件進(jìn)行操作，能夠較好地繼承父代個(gè)體的優(yōu)良特征，具體操作如下：

①在工件集{J1,J2,J3,···,Jm}隨機(jī)選取任意數(shù)量的工件構(gòu)成子工件集Jobset1。

②將原始個(gè)體中包含在工件集Jobset1 中的工件復(fù)制到新個(gè)體中，并保持它們的位置和順序。

③將變異后個(gè)體中不包含在工件集Jobset1 中的工件復(fù)制到新個(gè)體中，并保持它們的順序。

OS 部分交叉如圖4 所示。

圖4 改進(jìn)POX 交叉

2.4 結(jié)合Pareto 支配關(guān)系的精英選擇策略

為加速算法收斂，保證種群最優(yōu)解不會(huì)因變異操作和交叉操作的影響而消失，本文對迭代過程中的原始種群與交叉后的種群進(jìn)行結(jié)合，采用基于Pareto 支配關(guān)系的非劣解快速排序方法對種群中的個(gè)體進(jìn)行分類，將種群分為具有支配關(guān)系但互不相交的子種群，最后通過擁擠距離的計(jì)算得到新種群。傳統(tǒng)的精英選擇策略在處理MOP 時(shí)選擇的最優(yōu)個(gè)體很難滿足多個(gè)目標(biāo)函數(shù)；基于聚合的精英選擇策略按照權(quán)重比將MOP 轉(zhuǎn)換成了單目標(biāo)問題，但該方法難以確定合適的權(quán)重比；基于準(zhǔn)則的精英選擇策略只能求出每個(gè)目標(biāo)函數(shù)的最優(yōu)個(gè)體，難以確定滿足所有目標(biāo)函數(shù)的個(gè)體。結(jié)合Pareto 支配關(guān)系的精英選擇策略通過Pareto 支配關(guān)系的非劣解快速排序方法和擁擠距離計(jì)算，可以得到滿足各目標(biāo)函數(shù)的多個(gè)最優(yōu)個(gè)體，該策略既可以保留算法在進(jìn)化過程中的多個(gè)最優(yōu)個(gè)體，還保護(hù)了種群的多樣性，同時(shí)對算法的收斂速度有一定的提升。

結(jié)合Pareto 支配關(guān)系的精英選擇策略的具體步驟如下。

（1）將原始種群與交叉后的種群合并為一個(gè)臨時(shí)種群。

（2）根據(jù)整體規(guī)則和個(gè)體規(guī)則將臨時(shí)種群生成新的種群。

①整體規(guī)則：按照從低到高的順序排列用快速排序方法生成的Pareto 等級(jí)，根據(jù)Pareto 等級(jí)將種群中的個(gè)體按層劃分，依次將每層種群中的個(gè)體放入新種群中，直到父代種群達(dá)到種群規(guī)模；

②個(gè)體規(guī)則：按照擁擠距離從大到小的順序排列該層個(gè)體，依次放入父代種群中，直到父代種群填滿。

2.5 融合SA 算法的選擇操作

傳統(tǒng)DE 算法的選擇操作是將交叉后的個(gè)體與原始個(gè)體逐一對比，按照適應(yīng)度值擇優(yōu)選擇。這個(gè)方法的弊端是容易陷入局部最優(yōu)解，為解決這一弊端，HADE 算法在選擇操作中結(jié)合了SA 算法，對適應(yīng)度值比原始個(gè)體差的交叉后的個(gè)體進(jìn)行操作，嘗試選出更好的個(gè)體替代原始個(gè)體，從而跳出局部最優(yōu)解，具體步驟如下：

（1）將交叉后的個(gè)體與原始個(gè)體按照0.6∶0.3∶0.1 的權(quán)重比對最大加工時(shí)間、最大機(jī)器負(fù)荷、總機(jī)器負(fù)荷進(jìn)行適應(yīng)度值計(jì)算。

（2）判斷適應(yīng)度值大小。若交叉后的個(gè)體適應(yīng)度值更低，將交叉后的個(gè)體替代原始個(gè)體；否則，對交叉后個(gè)體進(jìn)行SA 處理。

（3）設(shè)置初始溫度T0，T=T0。

（4）令T=λT，λ表示退火速率，λ∈(0,1)。

（5）對當(dāng)前個(gè)體的OS 部分進(jìn)行隨機(jī)擾動(dòng)，使其產(chǎn)生一個(gè)新個(gè)體，計(jì)算出原始個(gè)體與新個(gè)體的差值，若差值小于0，則接受該個(gè)體替換原始個(gè)體，結(jié)束循環(huán)。

（6）判斷是否達(dá)到終止溫度，若是，則結(jié)束循環(huán)，否則轉(zhuǎn)到步驟（4）。

2.6 HADE 算法流程

HADE 算法流程如圖5 所示。

圖5 HADE 算法流程圖

利用HADE 算法求解多目標(biāo)FJSP 主要步驟如下：

（1）設(shè)置HADE 算法中種群規(guī)模、最大迭代次數(shù)、Fmax、Fmin、T等參數(shù)。

（2）根據(jù)調(diào)度問題將GS、LS 與RS 結(jié)合使用生成初始種群。

（3）對種群進(jìn)行改進(jìn)自適應(yīng)變異操作和改進(jìn)交叉操作。

（4）求交叉后種群與原始種群合并后的Pareto最優(yōu)解，根據(jù)計(jì)算出的擁擠度距離擇優(yōu)保留。

（5）將新種群與原始種群根據(jù)權(quán)重比得到的適應(yīng)度值進(jìn)行選擇操作，若新個(gè)體優(yōu)于原始個(gè)體，則更新原個(gè)體；否則，進(jìn)行SA 操作。

（6）判斷是否達(dá)到最大迭代次數(shù)。若滿足，循環(huán)結(jié)束；否則，轉(zhuǎn)到步驟（3）。

（7）將輸出的最優(yōu)個(gè)體解碼并轉(zhuǎn)換成對應(yīng)的調(diào)度序列，算法結(jié)束。

2.7 函數(shù)優(yōu)化測試

根據(jù)劉昊等[15]對標(biāo)準(zhǔn)測試函數(shù)的描述，選取表2 中的兩個(gè)函數(shù)作為本文的測試函數(shù)，驗(yàn)證HADE 算法相較于ADE 算法與DE 算法的優(yōu)越性。對3 種算法設(shè)置相同的操作參數(shù)及相同的初始種群。圖5 和圖6 所示為DE、ADE 和HADE 三種算法在最大迭代次數(shù)為30、種群規(guī)模為100 時(shí)得到的最優(yōu)解與迭代次數(shù)的變化曲線。

圖6 3 種算法在測試函數(shù)1 中的性能比較

表2 測試函數(shù)

由圖6 和圖7 可知，HADE 算法比ADE 算法和DE 算法到達(dá)全局最優(yōu)解0 需要更少的迭代次數(shù)；在迭代次數(shù)相同時(shí)，HADE 算法所獲得的最優(yōu)解要比ADE 算法和DE 算法更好。實(shí)驗(yàn)結(jié)果表明，HADE 算法的收斂速度和平均適應(yīng)度都有一定的提高。

圖7 3 種算法在測試函數(shù)2 中的性能比較

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

本文使用Brandimarte P[16]所提出的Mk02（10個(gè)工件6 臺(tái)機(jī)器）、Mk04（15 個(gè)工件8 臺(tái)機(jī)器）、Mk08（20 個(gè)工件10 臺(tái)機(jī)器）三種數(shù)據(jù)集，使用Python 編程，將Windows 10 運(yùn)行平臺(tái)下的Pycharm軟件作為仿真環(huán)境。設(shè)置初始種群規(guī)模為40，迭代次數(shù)為80，T0為5，λ為0.8，將HADE 算法與混合差分進(jìn)化（hybrid differential evolution，HDE）算法[7]、ADE 算法和DE 算法進(jìn)行比較，為防止實(shí)驗(yàn)的偶然性，每種算法各運(yùn)行10 次。選取最大完工時(shí)間最小的3 組解進(jìn)行對比，實(shí)驗(yàn)結(jié)果見表3，其中(67,67,390)代表最大加工時(shí)間為67、最大機(jī)器負(fù)荷為67、總機(jī)器負(fù)荷為390。

表3 實(shí)驗(yàn)結(jié)果比較

由表3 的Mk02、Mk04 結(jié)果可以看出，HADE算法對最大加工時(shí)間和最大機(jī)器負(fù)荷兩個(gè)目標(biāo)函數(shù)的優(yōu)化明顯優(yōu)于其他三種算法，其中，DE 算法的優(yōu)化效果是最差的。單看總機(jī)器負(fù)荷這一目標(biāo)函數(shù)在Mk04 中的優(yōu)化結(jié)果，四種算法的總機(jī)器負(fù)荷平均值為383.7、388.7、400、396，說明HADE 算法對這一目標(biāo)函數(shù)的優(yōu)化也是最好的，但相差不大。在處理較大規(guī)模數(shù)據(jù)集Mk08 時(shí)，HADE 算法雖比其他3 種算法更優(yōu)，但無太大差距?？傮w來說，HADE 算法相較于HDE 算法、ADE 算法和DE 算法的優(yōu)化效果更優(yōu)，是一種適用于求解多目標(biāo)FJSP的算法。

圖8 所示為權(quán)重占比最高的最大加工時(shí)間在Mk04 數(shù)據(jù)集中四種算法的迭代過程曲線。當(dāng)?shù)螖?shù)相同時(shí)，HADE 算法的最大加工時(shí)間最小；當(dāng)最大加工時(shí)間相同時(shí)，HADE 算法的迭代次數(shù)更少。綜上所述，HADE 算法具有更好的尋優(yōu)能力，在求解多目標(biāo)FJSP 問題時(shí)具有一定優(yōu)勢。

圖8 最大加工時(shí)間在Mk04 中4 種算法的進(jìn)化曲線

圖9 所示為對比4 種算法在Mk04 中得到的Pareto 解集，可以看出HADE 算法的尋優(yōu)能力更強(qiáng)，能得到更好的解。

圖9 去重Pareto 解集對比

圖10 所示為使用HADE 算法對Mk04 數(shù)據(jù)集優(yōu)化時(shí)得到的最大加工時(shí)間為67、最大機(jī)器負(fù)荷為66、總機(jī)器負(fù)荷為376 的調(diào)度結(jié)果甘特圖。

圖10 調(diào)度優(yōu)化結(jié)果甘特圖

4 結(jié)語

本文提出了HADE 算法對多目標(biāo)FJSP 進(jìn)行求解，針對最小化最大加工時(shí)間、最小化機(jī)器最大負(fù)荷、最小化總機(jī)器負(fù)荷等目標(biāo)函數(shù)進(jìn)行優(yōu)化，在Mk02、Mk04 和Mk08 這3 種數(shù)據(jù)集中與HDE 算法、ADE 算法、DE 算法進(jìn)行仿真對比，最終表明本文算法收斂性更好，尋優(yōu)能力更強(qiáng)，在求解FJSP 時(shí)效果更優(yōu)。但在處理Mk08 等較大規(guī)模數(shù)據(jù)集時(shí)收斂速度相對較慢，后續(xù)工作將針對處理大規(guī)模問題時(shí)進(jìn)一步提升算法的尋優(yōu)能力和收斂速度。