基于改進遺傳算法的柔性流水車間調度研究

徐嘉琦 田 野②

（①長春理工大學計算機學院，吉林 長春 130022；②長春理工大學人工智能學院，吉林 長春 130022）

柔性流水車間調度問題（flexible flow shop scheduling problem，F(xiàn)FSP）也稱混合流水車間調度問題，是在傳統(tǒng)車間調度問題的基礎上加入了并行機的機制，更加符合如今的工廠車間生產(chǎn)的實際情況。隨著智能化自動化的普遍應用與升級，目前柔性流水車間調度問題被廣泛應用于機械[1]、化工、汽車生產(chǎn)、運輸?shù)雀餍懈鳂I(yè)。該問題已被證實為NP-Hard問題，解決此問題目前最常用的辦法就是智能優(yōu)化算法[2]，如粒子群算法、蜂群算法、遺傳算法等[3]。隨著問題規(guī)模的擴大，原始群智能算法出現(xiàn)計算慢、收斂過早、結果不好等問題[4]，因此對原算法的優(yōu)化改進是必然的趨勢。本文研究為經(jīng)典的遺傳算法在該問題上的應用。Bao T 等[5]針對遺傳算法引入了基于有向變異的種群初始化，和基于免疫的物種選擇對算法進行了優(yōu)化。楊森等[6]提出了一種自適應遺傳算法的改進方法，優(yōu)化了交叉概率和變異概率的計算方式，并對該算法進行了驗證。Shao W S等[7]提出了基于多鄰域局部搜索的多目標進化算法求解多目標分布式混合流水車間調度問題。

經(jīng)過眾多的文獻查詢[8]，柔性流水車間問題在實際生產(chǎn)應用中的最優(yōu)化目標有機器閑置時間最少，完工最快。問題的編碼以及解碼方式也是影響結果的重要原因之一。基于此，本文提出了一種改進遺傳算法求解柔性流水車間調度問題，以完工時間最小化為目標，設計了針對該問題的編碼與解碼，算法針對該編碼在復制、遺傳、變異上進行相應優(yōu)化，并引入了多種策略以提高算法的性能，在高收斂速度下，避免陷入局部最優(yōu)無法更新最優(yōu)解，最后通過多種對比試驗驗證算法的有效性。

1 柔性流水車間調度問題

1.1 問題概述

柔性流水車間問題即：工廠生產(chǎn)n個產(chǎn)品，每個產(chǎn)品的工藝路徑是相同的，都需要m道工序，不同產(chǎn)品在同一道工序上加工時間不同，并且存在并行機，即m道工序中有一道或多道工序的機器數(shù)量為兩臺或多臺，這些機器的性能是相同的，如圖1 所示。

圖1 柔性流水車間調度

有關參數(shù)定義如下：j為作業(yè)的索引，j=1,2,···,n；j′為j的上一個作業(yè)；i=1,2,···,m為工序索引；hi表示工序i可操作的機器有h個，hi=1,2,···,ki，其中ki為工序i中可用來加工的機器數(shù)量；Gi表示工序i中可用來加工的機器合集；Cij表示工序i中開工順序為j的作業(yè)完成時間；Pij表示作業(yè)i的第j道工序的需要工作的時間；Mhi表示機器集合Gi里的第h個機器；Z表示工作的完成時間。

有關決策變量的定義如下：

1.2 柔性流水車間問題的數(shù)學模型

式（1）為目標函數(shù)最小完工時間Z的最小值；式（2）在一道工序中任何作業(yè)只可以有一個緊前作業(yè)；式（3）為所有的作業(yè)在同一工序的每個機器上只能成為一個作業(yè)的緊前作業(yè)；式（4）為任意作業(yè)的排產(chǎn)無論是否出現(xiàn)在某機器上，它的緊前、緊后作業(yè)變量一定相等；式（5）是同一個機器的同一個位置上的作業(yè)不存在緊前或緊后的關系；式（6）是對完工時間的約束，兩個作業(yè)在同一臺機器上有緊前關系，該定義才有效，在不同機器上完工時間無規(guī)定，或者同一機器無緊前緊后關系可用此約束，M為一個極大值；式（7）為同一作業(yè)前一道工序完成時間加當前工序的作業(yè)時間不能大于當前工序完成時間；式（8）為各作業(yè)的準備時間為0。

2 改進遺傳算法

2.1 算法流程

針對柔性流水車間的改進遺傳算法，輸入具體的問題，包括作業(yè)數(shù)、工序數(shù)和每個作業(yè)的每道工序所需時間的矩陣，以及每道工序對應的可用機器數(shù)量；輸出為最優(yōu)的工件安排表，包括最小完成時間以及Gantt 圖。算法在遺傳算法基礎上針對柔性流水車間問題進行了改進，由于該問題解的離散性對多處進行了優(yōu)化與添加，流程圖如圖2 所示。

圖2 MGTA 算法流程圖

2.2 編碼與解碼

染色體的編碼是遺傳算法的第一步，后續(xù)的一切操作都圍繞著編碼進行操作。本文采取一維的編碼形式，由于自動選擇機器，而完工時間僅由每道工序的作業(yè)加工順序決定。與傳統(tǒng)一維編碼相比，傳統(tǒng)編碼為從1 到(n×m)的亂序，這里將一個個體的編碼在內部分為m份，則每份的排列為從(n－1)×m+1 到(n×m)，此處n的取值范圍為[1,n]。如有一作業(yè)數(shù)為4、工序數(shù)為3 的初始問題，則個體的編碼如圖3 所示。

圖3 染色體編碼

該編碼在一定程度可以避免種群的重復，也可以減少后期的計算量。解碼為編碼的逆操作，本文使用解碼方式為針對最早結束時間的啟發(fā)式解碼規(guī)則。按順序排產(chǎn)，當前操作數(shù)為a，工序數(shù)為proc,作業(yè)數(shù)為job，當前操作數(shù)的工序為(a-1)與job取商后加1，當前操作數(shù)的作業(yè)數(shù)為(a-1)與job取余后加1，并安排機器。分配前進行機器空閑時間檢查，在可排產(chǎn)的可用機器中再次搜索是否有兩個工作間隔的空閑時間、是否可以塞入當前任務，若沒有再安排到當前工序可用機器里可開工時間最小的機器上，優(yōu)先完成先分配的方案。

2.3 種群初始化

由于隨機生成的初始種群存在不確定性，有可能生成種群聚集，本文采用對立方法進行初始化操作，先隨機生成一半的初始種群。由于該問題屬于離散型，對立方式為將生成的一半種群全部進行逆序排列，即將每道工序全部進行逆序，如一作業(yè)數(shù)為4、工序數(shù)為3 的問題隨機生成的個體和對立后個體如圖4 所示，避免了初始種群聚集，可生成更優(yōu)解提升算法效率。

圖4 對立方法

2.4 交叉操作

傳統(tǒng)遺傳算法多為單點或多點交叉，即交換兩個或多個點生成全新的DNA 個體。由于本文的離散型編碼，單點或多點交叉后會出現(xiàn)缺失或重復，需重新驗證個體完整性，導致計算時間增加，并破壞原有基因格式。為保留原有基因編碼格式的同時交叉產(chǎn)生新個體，這里采用片段交叉，將兩個個體的某一工序整體進行交叉變換，這樣可以在生成新個體的同時更直觀地保留父代的優(yōu)秀基因。如有兩個DNA 個體，則交叉方式如圖5 所示。

圖5 交叉操作

2.5 優(yōu)化變異操作

變異操作是擴大搜索范圍找到更優(yōu)解的關鍵步驟。首先由概率判斷該個體是否需要進行變異，為了變異程度更大跳出局部最優(yōu)，針對該文的編碼方式設計如下變異：個體的每道工序都進行變異，每道工序中隨機選取兩個作業(yè)數(shù)進行交換，如圖6 所示。

圖6 優(yōu)化變異操作

這樣針對n個作業(yè)、m道工序的個體，每經(jīng)過一次變異就有2m處發(fā)生了變異，增大變異的程度并且保證了編碼的格式。

2.6 多目標選擇

選擇操作的目的是使種群向最優(yōu)個體靠攏，并將最優(yōu)個體遺傳到下一代，在一定程度上在最優(yōu)個體附近更新尋找最優(yōu)解。為了降低種群陷入局部最優(yōu)的情況，根據(jù)離散型的問題設計了多目標選擇，即選出b個較優(yōu)個體，使其他個體向這些個體靠攏。按照次序使除較優(yōu)個體分別進行選擇操作，每次選擇操作前都隨機獲取個體的一個片段，使該片段直接被其目標較優(yōu)個體的相同位置的片段替換。再從頭檢查個體去除重復部分，補上缺失部分。在較優(yōu)個體上隨機選取片段如圖7 所示，非較優(yōu)個體靠攏方式如圖8 所示。

圖7 片段選取

圖8 靠攏方式

多目標選擇增大了算法的搜索程度，給出了更多疑似最優(yōu)的選擇，并且未增加時間復雜度的量級，在不影響收斂速度的同時，增大了搜索范圍。

2.7 交叉概率變異概率更替

交叉和變異操作作為遺傳算法中的兩個重要步驟，交叉和變異的概率更加決定了算法的效率。本文設計了兩套交叉概率和變異概率，用來針對不同的情況。初始情況為高交叉概率、低變異概率，并記錄迭代過程中最優(yōu)解更新情況，若g次迭代仍未出現(xiàn)最優(yōu)解的改變則調整為低交叉概率、高變異概率，再次出現(xiàn)最優(yōu)解更新后恢復高交叉概率、低變異概率。這樣使整體算法更加靈活，能更好地跳出陷入局部最優(yōu)解的情況。

3 仿真試驗及結果分析

3.1 參數(shù)設置和對比試驗

MTGA 在求解柔性流水車間調度中的主要參數(shù)包括種群大小（pop）、最大迭代次數(shù)（G）、較優(yōu)個體數(shù)（b）、高交叉概率（c1）、低交叉概率（c2）、低變異概率（m1）、高變異概率（m2）、最優(yōu)解未更新代數(shù)（g）。由于多目標選擇的因素種群大小在較大時可以更好地發(fā)揮意義，因此種群大小設置為200。針對交叉以及變異概率的設置，交叉概率過大會導致種群歸一化，過小則沒有保留優(yōu)秀基因的效果；變異概率過大會導致種群傾向于隨機無規(guī)律搜索，過小則無法跳出局部最優(yōu)解。經(jīng)過多次試驗結果統(tǒng)計，高交叉概率為0.7，低交叉概率為0.3，高變異概率為0.5，低變異概率為0.2，g為pop/4，b為5，最大迭代次數(shù)分別設置為100和200。為驗證本文改進算法（MTGA）的性能，將算法與改進遺傳算法（NSAGA）[9]、改進貪婪遺傳算法（GGA）[10]、混沌自適應粒子群優(yōu)化算法（CAPSO）[11]、基于Lévy 飛行和差分進化的混合鯨魚優(yōu)化算法（WOA-LFDE）[12]進行對比。以上對比算法都是近期發(fā)布的可應用于FFSP 的優(yōu)秀算法。對比算法參數(shù)均按照原論文給出的最優(yōu)參數(shù)進行設置。試驗均采用Matlab R2016a 編寫，在Intel Core i5-10200H、2.40GHz CPU、16GB RAM、Windows 10 環(huán)境下進行測試。

3.2 尋優(yōu)效果測試

首先對幾種算法的尋優(yōu)能力進行測試，算例為中等規(guī)模，10 個作業(yè)均有9 個工序，每道工序配備的機器數(shù)量為[2 3 2 1 2 4 6 2 4]，每個工件的每道工序加工時間通過隨機生成取值范圍為(0,180)，具體見表1，通過暴力搜索算法得出最優(yōu)解為919。5 種算法在迭代次數(shù)為200、求解10 次求得的最優(yōu)解見表2。

表1 工作時間

表2 運算結果

由表2 可知，除WOA-LFDE 算法外，4 種算法在10 次實驗中均成功得出過最優(yōu)解。為了便于對比，在此引入每次實驗的最優(yōu)解與已知最優(yōu)解的平均相對偏離度（average relative percentage deviation，ARPD）[13]，定義如下：

式中：L表示算法的實驗次數(shù)，soli表示算法。

在第i次實驗求得的最優(yōu)解，BKS 為問題已知最優(yōu)解。ARPD 能夠有效地表示算法求的解與最優(yōu)解之間的相對偏離程度以及算法的尋優(yōu)能力。表3為算法10 次求解上述算例后求得的ARPD。

表3 算法的ARPD

由表3 可知，MTGA 算法可以求得在最優(yōu)解附近誤差較小的結果，其ARPD 的值也是最小的；NSAGA 與CAPSO 算法雖然也求出了最優(yōu)解，但是存在某次結果距最優(yōu)解偏離較大，因此導致ARPD較大；WOA-LFDE 算法雖然未求得最優(yōu)解，但其運算結果較為集中，離散程度很小，并且與最優(yōu)解相差不大；GGA 算法雖然表現(xiàn)結果與MTGA 相差不大，但由于其貪婪選擇的原因導致運算量與運算時間也相對較大，因此在尋優(yōu)能力方面MTGA 有著較好的效果。

3.3 大規(guī)模基準算例測試

為進一步驗證MTGA 的各方面性能，本文參考Carlier I 和 Néron E[14]所提的12 種算例進行測試，如10-5-1 表示有10 個作業(yè)，每個作業(yè)有5 道工序，1 是每道工序機器數(shù)的索引。索引對應機器數(shù)見表4。

表4 機器數(shù)量類型匯總

針對每個算例進行20 次測試，種群大小為200，迭代次數(shù)為100，分別記錄20 次實驗中的最優(yōu)解（Cmin）、平均解（Cave）和標準差（Std），結果見表5。針對大型算例的收斂曲線如圖9～圖12 所示，算例10-5-1 的甘特圖如圖13 所示。

表5 大規(guī)模實驗結果

圖9 算例20-10-6 收斂曲線

圖10 算例20-10-5 收斂曲線

圖11 算例20-10-4 收斂曲線

圖12 算例15-10-4 收斂曲線

圖13 算例10-5-1 甘特圖

4 結果分析

由實驗結果可以明顯看出，針對機器數(shù)量瓶頸階段在開頭的實驗（機器索引為2 和5），5 種算法尋優(yōu)能力相差不大，所求的最優(yōu)解相近，在問題規(guī)模不大的情況下離散程度也很好，算法都十分穩(wěn)定。在20-10-5 的實驗中，NSAGA、WOA-LFDE、GGA 標準差較大，算法穩(wěn)定性較差。針對瓶頸階段在中間的實驗（機器索引為1、3、4、6）MTGA算法的尋優(yōu)能力明顯優(yōu)于其對比算法，在小規(guī)模算例中差距不大，但隨著問題規(guī)模的擴大，MTGA 的最優(yōu)解與其他算法差距也變大，并且除20-10-6 算例穩(wěn)定性不輸于其對比試驗。20-10-6 算例標準差明顯變大的原因是MTGA 在實驗中搜索到十分優(yōu)秀的解導致標準差的擴大，也能側面說明其尋優(yōu)能力，以及可以有效跳出局部最優(yōu)解的優(yōu)點。在表5中還可以發(fā)現(xiàn)，GGA 算法在部分大規(guī)模實驗中表現(xiàn)與MTGA 相近，但由于其貪婪搜索的原因導致其運行時間大幅度增加，效果也未超越MTGA，因此驗證了MTGA 算法在尋優(yōu)能力上的有效性和優(yōu)越性。針對收斂曲線，由于小規(guī)模算例各算法差距不大，因此選擇4 個典型的大規(guī)模算例進行收斂曲線對比。由圖9 針對機器數(shù)瓶頸期在開頭的算例中，各種算法的精度和收斂速度相差不大，其中MTGA和GGA 精度相對較高。由圖10～圖12 可知，MTGA算法在機器數(shù)瓶頸期在中間的大規(guī)模算例中精度遠遠高于其他算法，收斂速度在圖11 和圖12 中不低于其他對比算法。圖9 中收斂速度在迭代前期不是最佳，但能夠及時跳出局部最優(yōu)解獲得更優(yōu)秀的解。

5 結語

本文研究了改進的遺傳算法應用于柔性流水車間調度問題，介紹了柔性流水車間問題，設計了針對該問題的編碼與解碼方案，用對立方法生成初始種群，設計了兩套交叉變異概率靈活交替應用，針對編碼方式更新了交叉與變異，采用了多目標選擇，使收斂方向多個最優(yōu)解靠攏，降低陷入局部最優(yōu)的概率。通過實驗對比NSAGA、CAPSO、WOA-LFDE和GGA 這4 種優(yōu)秀的改進算法驗證了MTGA 的精度與穩(wěn)定性，又通過12 個算例，包括機器瓶頸期在開頭和中間的情況，驗證了MTGA 算法在不同規(guī)模，不同類型的算例中收斂性和精度表現(xiàn)得出算法的精度是在對比實驗中最高的，且有較好的收斂性，證明了算法的有效性和優(yōu)越性。未來的工作將從算法的收斂速度入手，為明顯加快算法收斂速度使其明顯優(yōu)于其他算法進行研究。