求解多目標柔性作業(yè)車間調(diào)度問題的混合自適應差分進化算法

陳永燦 劉 宇 周艷平

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

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

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

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

1 多目標FJSP 模型

1.1 多目標FJSP 描述

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

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

表1 模型參數(shù)表

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

本文模型共有3 個目標函數(shù)。

（1）最小化最大加工時間：

（2）最小化機器最大負荷：

（3）最小化總機器負荷：

約束條件說明：

（1）一臺機器在某一時刻只能加工一道工序。

（2）任何工序在同一時刻只能被一臺機器加工。

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

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

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

2 HADE 算法

2.1 編碼與初始化

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

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

圖1 MSOS 編碼

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

2.2 變異操作

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

MS 部分變異：在MS 部分中隨機選擇x個位置，依次將這些位置所選擇的機器設置為當前工序可選加工機器中加工該工序用時最少的機器。

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

圖2 OS 部分變異

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

圖3 自適應變異算子對比圖

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

2.3 交叉操作

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

（1）MS 部分交叉

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

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

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

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

（2）OS 部分交叉

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

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

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

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

OS 部分交叉如圖4 所示。

圖4 改進POX 交叉

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

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

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

（1）將原始種群與交叉后的種群合并為一個臨時種群。

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

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

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

2.5 融合SA 算法的選擇操作

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

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

（2）判斷適應度值大小。若交叉后的個體適應度值更低，將交叉后的個體替代原始個體；否則，對交叉后個體進行SA 處理。

（3）設置初始溫度T0，T=T0。

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

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

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

2.6 HADE 算法流程

HADE 算法流程如圖5 所示。

圖5 HADE 算法流程圖

利用HADE 算法求解多目標FJSP 主要步驟如下：

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

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

（3）對種群進行改進自適應變異操作和改進交叉操作。

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

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

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

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

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

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

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

表2 測試函數(shù)

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

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

3 仿真實驗及結(jié)果分析

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

表3 實驗結(jié)果比較

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

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

圖8 最大加工時間在Mk04 中4 種算法的進化曲線

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

圖9 去重Pareto 解集對比

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

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

4 結(jié)語

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