基于改進(jìn)遺傳算法的柔性流水車間調(diào)度研究

徐嘉琦 田 野②

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

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

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

1 柔性流水車間調(diào)度問題

1.1 問題概述

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

圖1 柔性流水車間調(diào)度

有關(guān)參數(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表示工作的完成時間。

有關(guān)決策變量的定義如下：

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

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

2 改進(jìn)遺傳算法

2.1 算法流程

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

圖2 MGTA 算法流程圖

2.2 編碼與解碼

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

圖3 染色體編碼

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

2.3 種群初始化

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

圖4 對立方法

2.4 交叉操作

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

圖5 交叉操作

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

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

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

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

2.6 多目標(biāo)選擇

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

圖7 片段選取

圖8 靠攏方式

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

2.7 交叉概率變異概率更替

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

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

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

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

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

首先對幾種算法的尋優(yōu)能力進(jìn)行測試，算例為中等規(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 運算結(jié)果

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)果分析

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

5 結(jié)語

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