徐嘉琦 田 野②

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

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

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

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

1.1 問題概述

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

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

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

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

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

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

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

2.1 算法流程

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

圖2 MGTA 算法流程圖

2.2 編碼與解碼

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

圖3 染色體編碼

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

2.3 種群初始化

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

圖4 對(duì)立方法

2.4 交叉操作

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

圖5 交叉操作

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

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

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

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

2.6 多目標(biāo)選擇

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

圖7 片段選取

圖8 靠攏方式

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

2.7 交叉概率變異概率更替

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

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

3.1 參數(shù)設(shè)置和對(duì)比試驗(yàn)

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

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

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

表1 工作時(shí)間

表2 運(yùn)算結(jié)果

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

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

在第i次實(shí)驗(yàn)求得的最優(yōu)解，BKS 為問題已知最優(yōu)解。ARPD 能夠有效地表示算法求的解與最優(yōu)解之間的相對(duì)偏離程度以及算法的尋優(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)解，但其運(yùn)算結(jié)果較為集中，離散程度很小，并且與最優(yōu)解相差不大；GGA 算法雖然表現(xiàn)結(jié)果與MTGA 相差不大，但由于其貪婪選擇的原因?qū)е逻\(yùn)算量與運(yùn)算時(shí)間也相對(duì)較大，因此在尋優(yōu)能力方面MTGA 有著較好的效果。

3.3 大規(guī)?；鶞?zhǔn)算例測試

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

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

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

表5 大規(guī)模實(shí)驗(yàn)結(jié)果

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

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

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

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

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

4 結(jié)果分析

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

5 結(jié)語

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