改進差分進化算法求解混合流水車間調度問題

張 源 陶翼飛 王加冕

昆明理工大學機電工程學院,昆明,650500

0 引言

混合流水車間調度問題[1](hybrid flow-shop scheduling problem，HFSP)是指在一定的時間內對加工工件的排序和設備的指派進行合理分配，使某些性能指標達到最優，已廣泛應用于煙草加工、中草藥生產、冶金等行業。HFSP結合了流水車間和并行機調度的特點，使其復雜程度更高、求解難度更大，且已被證明是一類經典的NP難題[2]。有效解決該類調度問題可以提高企業的生產效率和競爭力，因此研究HFSP具有重要的應用價值和意義。

目前，求解HFSP的算法主要包括遍歷式算法[3]、構造型算法[4]和智能優化算法[5]，其中遍歷式算法可以求解出該類問題的精確解，但計算速度較慢；構造型算法在求解該類問題時運算速度較快，但算法結構復雜且通常無法求解出全局最優解；智能優化算法具有嚴密的理論依據，能夠在較短時間內求解出問題的最優解或理想解，已普遍應用于求解各種生產調度問題。差分進化(differential evolutionary，DE)算法[6]是在遺傳算法進化思想的基礎上所提出的一種智能優化算法，通過父代向量間的差分運算進行種群的迭代更新，主要用于求解多維空間整體最優解。目前已有許多研究采用DE算法求解生產調度問題。GODFREY等[7]針對流水車間調度問題，分別以最大完工時間、流水時間和最小化拖期為目標，采用DE算法進行求解并與采用遺傳算法的結果進行比較，驗證了DE算法具有較好的求解質量。PAN等[8]提出了一種求解作業車間最大完工時間的混合離散DE算法，該算法基于工件的排列順序對個體進行編碼，并應用基于工件排列的變異和交叉操作來生成新的候選解，通過已知基準實例的計算仿真和比較，證明了所提算法的優越性。LIU等[9]提出了一種混合DE算法并用來求解置換流水車間調度問題，該算法將DE算法與個體改進方案(individual improving scheme，IIS)和基于貪心的局部搜索相結合，通過仿真與實驗結果的對比分析，證明了該算法可以有效解決車間調度問題。ZHOU等[10]針對可重入混合流水車間調度問題，以總加權完工時間為優化目標提出一種基于分布估計的混合DE算法進行求解，通過對不同問題規模進行仿真實驗，驗證了該算法能在較短的時間內獲得滿意的解。WU等[11]研究了分布式裝配柔性作業車間調度問題，提出了一種基于DE的混合模擬退火算法，該算法采用貪心思想和非優勢排序相結合的方法來選擇子代，實驗結果表明，該算法能有效地解決分布式裝配柔性作業車間調度問題。

已有研究結果表明，DE算法主要通過與經典算法相融合進而對HFSP進行求解，目前缺乏有關DE算法的改進研究，并且標準DE算法存在全局搜索能力差、收斂速度慢、易陷入局部極值等缺點。針對上述問題，本文以HFSP為研究對象建立仿真模型，提出一種基于反向學習策略、自適應差分因子和Metropolis準則的改進差分進化(improved differential evolutionary，IDE)算法對不同規模的HFSP進行仿真優化實驗，將最大完工時間[12]作為性能指標，并將IDE算法與經典智能優化算法進行對比，驗證了IDE算法的有效性和優越性。

1 問題描述及數學模型

1.1 問題描述

混合流水車間也稱柔性流水車間[13]，是指在流水加工車間的某些工序中存在并行設備的情況，其調度問題可以描述為：I個待加工工件在工序數為J的流水線上依次加工，其中至少有一道工序存在一臺以上的不相關并行機設備，并且相鄰工序間存在無限暫存緩沖區；工件在每道工序中只能選擇該工序的一臺設備進行加工；同一工件在相同工序的不同設備上的加工時間不完全相同[13]。圖1為混合流水車間調度問題(HFSP)模型示意圖，已知各工件在所有設備上的加工時間，該模型的目標為搜索混合流水車間加工工件的最優序列和工件在各工序設備上的指派情況，使得混合流水車間加工I個工件的完工時間最短。

圖1 混合流水車間調度問題模型示意圖Fig.1 Schematic diagram of HFSP model

1.2 數學模型

HFSP數學模型定義參數如下:I表示待加工工件數；m表示加工設備數量；J表示工序數；Ci表示工件i的加工完工時間；i表示工件編號，取值為i=1,2,…,I；j表示工序編號，取值為j=1,2,…,J；mj表示第j道工序的設備總數；k表示每道工序的設備編號，取值為k=1,2,…,mj；Wi,j,k表示工件i在工序j的設備k上的加工所用時間；Pi,j表示工件i在工序j上的加工時間；Fi,j,k表示工件i在工序j的設備k上的加工完成時間；Si,j,k表示工件i在工序j的設備k上的開始加工時間；Xi,j,k表示工件i在工序j的分配情況，分配到設備k上加工時取值為1，否則為0。問題優化目標是最小化最大完工時間，即I個工件完工時間的最小值，具體數學模型如下：

minCmax=min max{C1，C2,…,CI}

(1)

HFSP數學模型的約束條件如下：

Fi,j,k≤Si,j+1,k

(2)

Fi,j,k=Wi,j,k+Si,j,k

(3)

Ci=Fi,J,k

(4)

(5)

(6)

式(1)為最小化最大完工時間的計算表達式及目標函數；式(2)表示各工件在前道工序完工后方可開始后道工序的加工；式(3)表示工件在各工序中的完工時間；式(4)表示各工件的完工時間等于該工件在最后一道工序的完工時間；式(5)表示工件在每道工序中只能選擇該工序的一臺設備進行加工；式(6)表示各工件在每道工序中的加工時間。

2 改進差分進化算法設計及求解

差分進化(DE)算法利用父代向量間差分的原理進行種群個體的迭代更新，以得到所求問題的最優解。但是標準DE算法由于在初始種群的生成、貪婪選擇機制、交叉變異概率方面的局限性，使算法易陷入局部最優解，因此為提高DE算法的全局搜索能力，本文結合反向學習策略[14]、自適應差分因子、Metropolis準則[15]對標準DE算法的各步驟進行了改進。

2.1 編碼和解碼

本文采用基于ROV規則的隨機鍵編碼方式[16]，即種群個體向量中的元素值在[0,1]中隨機生成，向量維度表示待加工工件的個數，工件的加工順序基于向量元素值的大小進行升序排列，如個體向量(0.5,0.1,0.8,0.2)對應的工件加工順序為(3,1,4,2)。解碼的目的是確定加工工件的初始序列和各工序設備的指派情況，其中個體向量中的元素序列代表工件進入混合流水車間首道工序的加工順序，后續階段的工件加工序列按前道工序完工時間的先后順序依次進行加工，工件在各工序并行設備的分配根據最短作業時間(shortest processing time，SPT)法則[17]進行安排，即并行機有單機空閑且暫存區有多工件時，選擇在該機器加工時間最短的工件進入；當并行機有多機空閑且暫存區有單工件時，選擇加工該工件所用時間最短的空閑機器進入；當暫存區隊列有等候工件且某并行機出現空閑時，選擇在該機器加工時間最短的工件進入。

2.2 適應度函數

本文優化的目標是最小化最大完工時間，在DE算法迭代過程中保留的是適應度值最大的個體，依據相關文獻采用目標函數的倒數作為適應度函數，但由于完工時間以秒為單位計算，目標函數計算結果較大，因此為方便觀察比較，在目標函數倒數的基礎上再放大100倍，即第g代的第n條染色體的適應度函數為

fg,n=100/Cg,n

(7)

式中，Cg,n為第g代種群的第n(n=1,2,…,N)個個體的完工時間；N為每代種群的個體數。

2.3 反向學習策略生成初始種群

在標準DE算法中,種群初始化都會采用純隨機策略，即已知個體向量元素的取值范圍，根據該范圍的上下限進行隨機取值，但是隨機策略生成的初始種群在最優解質量和迭代收斂速度等方面的結果并不理想。為提高最優解的質量和種群個體的多樣性，本文結合反向學習策略[14]生成初始種群。首先需依據最初個體得到反向個體，其計算表達式如下：

Ri=Ai+Bi-ri

(8)

式中，A、B分別為個體向量元素取值范圍的上下限；r為最初個體；R為反向個體；i為個體向量的維度。

生成初始種群的基本步驟如下：①采用隨機策略生成最初種群，并根據式(8)生成最初種群的反向種群；②分別計算最初種群和反向種群的個體適應度值；③將最初種群和反向種群中所對應個體的適應度值進行對比，選擇適應度值更高的個體進入最終初始種群。

2.4 改進自適應差分因子設計

DE算法中固定的變異縮放因子和交叉概率使該算法在求解不同規模問題時很難達到其最佳值，從而導致尋優能力降低。為此，本文采用基于進化代數自適應變化的變異縮放因子和交叉概率進行問題的求解。計算表達式如下：

(9)

(10)

式中，F為變異縮放因子；C為交叉概率；G為總迭代次數；g為當前迭代次數；Fu、Fl分別為變異縮放因子的上下邊界限；Cu、Cl分別為交叉概率的上下邊界限。

由式(9)和式(10)可得，隨著迭代次數的增加，變異縮放因子F逐步減小，交叉概率C的值逐步增大，從而使算法在迭代初期，通過提高交叉概率來維持種群的求解空間，從而提高搜索能力；在迭代后期，通過減小變異縮放因子來延續優良個體的基因結構，從而提高收斂速度[17]。

2.5 基于Metropolis準則的個體選擇機制

標準DE算法的選擇機制是將交叉后的個體和對應的初始個體進行對比，保留適應度值更高的個體進入下次迭代進化的種群。雖然該方法可以保證父代最優的個體進入子代，但極易使算法陷入局部最優，因此本文在DE算法的選擇機制中引入模擬退火算法的Metropolis準則，通過一定概率來接收比當前解差的解，從而避免算法陷入局部極值。具體操作如下：若變異個體適應度值優于初始個體適應度值，則接受變異個體進入子代；若初始個體適應度值優于變異個體適應度值，則以概率P接收變異個體。概率P的計算表達式如下：

(11)

Ty+1=WTy

(12)

式中,fin、fcn分別為第n個初始個體與其變異個體的適應度值；T為退溫函數；Ty為第y次退溫的溫度，當y=0時，T0為初始溫度；W為溫度衰減系數。

由式(11)和式(12)可得，當初始個體適應度值優于變異個體適應度值時，以概率P(P∈[0,1])接收該變異新個體。隨著迭代次數的增加，退溫溫度逐漸降低，從而使算法在迭代初期及高溫下，可接收與初始個體適應度差較大的變異新個體，進而維持種群的多樣性；在迭代后期及低溫下，可接收與初始個體適應度差較小的變異新個體，進而延續種群中的優良個體基因序列[15]。

2.6 改進差分進化算法步驟及流程圖

本文結合上述方法對標準DE算法進行改進，最終改進差分進化(IDE)算法的總流程如圖2所示，具體步驟如下。

圖2 改進差分進化算法流程圖Fig.2 Flow chart of IDE algorithm

(1)設置算法的初始化參數、種群規模及最大迭代終止次數Gmax。

(2)結合反向學習策略生成指定規模數量的種群作為IDE算法的最終初始種群。

(3)分別計算種群中個體的適應度值。

(4)基于改進自適應差分因子對種群個體向量進行更新。

(5)基于Metropolis準則對個體向量進行選擇操作。

(6)判斷是否滿足終止條件，若滿足則輸出尋優結果,若不滿足則轉至步驟(3)。

3 仿真實驗

本文選擇文獻[18-19]中的3個較小規模實例和文獻[20]中10個較大規模的Liao算例進行仿真實驗。其中小規模實例為：實例1[18]表示某鋼鐵廠生產企業需加工12個工件，加工過程由煉鋼、精煉、連鋼、軋制4道工序組成，4道工序的并行機數量分別為3、3、2、2；實例2[18]表示某汽車發動機企業需加工12個工件，所有工件都需經過車、刨、磨3道工序，3道工序的并行機數量分別為3、2、4；實例3[19]表示某工廠需加工6個工件，加工過程由銑、車、磨3道工序組成，3道工序的并行機數量分別為3、2、3。為進一步證明算法的性能，選擇10個大規模Liao算例[20](j30c5e1～ j30c5e10)作為實驗數據，該類型數據由30個工件、5道工序組成，其中j、c分別表示工件和工序數，e表示各工序中設備數量分配的10種不同情況。

上述實例的仿真模型及算法程序均在Plant Simulation軟件中建立和編寫，不同規模實例在工序和設備的數量上存在差異，但仿真模型的組成模塊和功能基本一致，所以本文以小規模實例1為例進行說明。如圖3所示，混合流水車間仿真模型由控制參數、程序仿真和數據統計3個模塊組成，其中程序仿真模塊中用Simtalk語言編寫DE算法和模型調度分配程序，數據統計模塊用來記錄工件在各機器上的加工時間、算法求解結果等數據，控制參數模塊包含仿真運行過程中需要調用的參數，如當前種群的進化代數、工件的最大完工時間等。測試模型在硬件為AMD A10-5750M APU 2.50 GHz的計算機上運行，設置IDE算法求解所有算例的最大迭代次數Gmax為200，每代種群個體數量N為50。

圖3 混合流水車間仿真模型Fig.3 Simulation model of hybrid flow-shop

4 結果分析

4.1 改進差分進化算法參數分析

采用L9(34)正交試驗分析變異縮放因子、交叉概率、初始溫度和溫度衰減系數對IDE算法尋優能力的影響，每個因素考察3個水平，最大迭代次數為200，每種組合獨立運行10次，得到最大完工時間的平均值。

通過查閱大量DE算法和模擬退火算法相關文獻，從中選擇常用的參數值進行正交試驗，如文獻[18]中DE算法的變異縮放因子取值范圍為[0.1,0.7]，交叉概率取值范圍為[0.1,0.6]；文獻[15]中模擬退火算法的初始溫度θ0(θ0=T0-273 K)為1000 ℃，溫度衰減系數W為0.9。在正交試驗中[Fl,Fu]取值[0.1,0.7]、[0.1,0.9]、[0.2,0.8]；[Cl,Cu]取值[0.1,0.6]、[0.1,0.5]、[0.15,0.5]；θ0取值1000 ℃、1300 ℃、1500 ℃；W取值0.9、0.95、0.98。表1所示為小規模實例1的統計結果。

表1 實例1正交試驗結果
Tab.1 Orthogonal experimental results of instance 1

組合[Fl,Fu][Cl,Cu]θ0(℃)W平均值(s)1[0.1,0.7][0.1,0.6]10000.90297.302[0.1,0.7][0.1,0.5]13000.95297.203[0.1,0.7][0.15,0.5]15000.98297.304[0.1,0.9][0.1,0.6]13000.98297.355[0.1,0.9][0.1,0.5]15000.90297.106[0.1,0.9][0.15,0.5]10000.95297.207[0.2,0.8][0.1,0.6]15000.95297.158[0.2,0.8][0.1,0.5]10000.98297.359[0.2,0.8][0.15,0.5]13000.90297.20

由表1可知，參數組合5的最大完工時間平均值最小，整體尋優結果最優，所以實例1采用該參數組合，即Fl=0.1、Fu=0.9、Cl=0.1、Cu=0.5、θ0=1500 ℃、W=0.9。剩余小規模實例2和實例3以及大規模算例均采用同樣的正交試驗進行分析，得到其最佳參數組合，如表2所示。

表2 正交試驗結果
Tab.2 Orthogonal test results

規模[Fl,Fu][Cl,Cu]θ0(℃)W平均值(s)實例2[0.1,0.9][0.1,0.6]13000.9824.1實例3[0.2,0.8][0.15,0.5]13000.9013.5j30c5e1[0.1,0.9][0.1,0.5]15000.90477.8j30c5e2[0.1,0.7][0.1,0.5]13000.95618.1j30c5e3[0.2,0.8][0.1,0.6]15000.95605.2j30c5e4[0.1,0.9][0.15,0.5]10000.95578.7j30c5e5[0.2,0.8][0.15,0.5]13000.90607.2j30c5e6[0.1,0.9][0.1,0.5]15000.90615.3j30c5e7[0.1,0.7][0.1,0.6]10000.90634.1j30c5e8[0.2,0.8][0.1,0.6]15000.95687.5j30c5e9[0.1,0.9][0.1,0.6]13000.98655.0j30c5e10[0.1,0.9][0.1,0.5]15000.90597.3

4.2 小規模已知算例結果分析

將本文提出的IDE算法基于上述3個小規模實例分別求解10次，并與遺傳算法(genetic algorithm，GA)算法[18-19]、DE算法[18]、改進果蠅優化算法(improved fruit-fly optimization algorithm，IFOA)[19]、種群增量學習(population-based incremental learning，PBIL)算法[19]、改進分布估計算法(improved estimation of distribution algorithm，IEDA)[19]的尋優結果進行了對比，表3所示為小規模實例下各算法的對比結果。

如表3所示，針對實例1，IFOA和IDE算法可以求得理論最優解297 s，均優于DE算法，并且IDE算法的尋優率80%高于IFOA算法的尋優率60%。圖4為IDE算法的迭代曲線圖，圖5為最優解甘特圖，圖中方框內的數據為工件序號，IDE算法在80代以內就收斂到最優解297 s，而IFOA算法在18 000次迭代搜索中才能求得最優解297 s[19]。針對實例2，IDE算法可以求解出比GA[18]和DE算法更優的解，且IDE算法的尋優率為90%。針對實例3，IFOA和IDE算法能夠以100%的尋優率求得理論最優解13.5 s，均優于其他算法且IFOA算法的迭代終止條件為迭代3000次[19]，而本文提出的IDE算法僅為200次。

表3 小規模實例結果對比Tab.3 Results comparison of small-scale instances s

圖4 實例1迭代曲線圖Fig.40 Instance 1 iteration curve

圖5 實例1最優解甘特圖Fig.5 Optimal solution Gantt diagram for instance 1

綜上所述，IDE算法具有更優的尋優率和全局搜索能力，并且在尋優結果相同的情況下IDE算法的收斂速度更快，從而驗證了所提IDE算法的有效性和優越性。

4.3 大規模算例結果分析

針對10個較大規模的混合流水車間Liao算例[20]，采用GA算法[21]、生物地理學優化(biogeography-based optimization，BBO)算法[21]、DE算法、改進BBO(IBBO)算法[21]以及本文提出的IDE算法分別獨立運行10次進行對比，表4所示為大規模算例下各算法的對比結果。

如表4所示，DE算法與GA算法和BBO算法的尋優結果較接近，未能體現出其明顯優越性，而經過改進后的IDE算法提高了搜索能力，使其求解的最小值和平均值均優于上述算法。與IBBO算法的尋優結果對比可得，IDE算法的平均值更優，并且在10個大規模算例中只有1個算例的最小值大于IBBO算法對應的最小值。

表4 大規模算例結果對比Tab.4 Results comparison of large-scale examples s

綜上，結合各算法的尋優對比結果可得，在求解較大規模問題時，IDE算法的搜索能力更強、最優解質量更優，從而再次驗證了所提IDE算法的有效性和優越性。

5 結語

本文以最小化最大完工時間為優化目標建立混合流水車間仿真模型，并在標準差分進化算法的基礎上引入反向學習策略、自適應交叉變異因子和Metropolis準則，提出了一種改進差分進化算法進行求解。通過對不同規模調度算例進行仿真實驗對比，證明了所提改進差分進化算法的優越性和有效性，為差分進化算法的改進研究提供了一定的參考價值。