蔡國帥，金 淳，華順剛

（1.大連理工大學(xué)機(jī)械工程學(xué)院，遼寧大連 116024；2.大連理工大學(xué)經(jīng)濟(jì)管理學(xué)院，遼寧大連 116024）

0 引言

置換流水車間調(diào)度問題（Permutation Flow-shop Scheduling problem，PFSP）作為典型的生產(chǎn)調(diào)度問題，是許多實(shí)際生產(chǎn)調(diào)度問題的簡化模型，在運(yùn)輸、物流、車間生產(chǎn)等領(lǐng)域有著大量的應(yīng)用[1]，已被證明3臺機(jī)器以上的PFSP問題屬于NP-Hard難題[2]。因此，研究該問題的優(yōu)化算法具有重要的理論意義和工程價值。

求解PFSP的方法主要分為3類，精確算法、啟發(fā)式算法和智能優(yōu)化算法。精確算法主要有分支定界法、整數(shù)規(guī)劃和動態(tài)規(guī)劃等方法，由于其計(jì)算復(fù)雜度大，僅用于求解小規(guī)模問題。啟發(fā)式算法有CDS（Campbell Dudek Smith）算法、Palmer算法以及NEH（Nawaz Enscore Ham）算法，啟發(fā)式算法具有求解速度快的優(yōu)勢，但是其求得的解的質(zhì)量較差。由于精確算法和啟發(fā)式算法存在不足，目前對PFSP的研究多集中于智能優(yōu)化算法。常用的智能優(yōu)化算法有粒子群優(yōu)化算法、遺傳算法、蟻群算法和差分進(jìn)化算法等。盡管許多智能優(yōu)化算法在PFSP上取得了不錯的效果，但是其迭代過程通常比較耗時，因此很多文獻(xiàn)中利用不同的算法生成群智能優(yōu)化算法的初始種群，以提高初始種群的質(zhì)量，提升算法的性能。如Zhang等[3]將NEH算法與遺傳算法結(jié)合，并融合模擬退火算法，以提升算法性能。秦旋等[4]將NEH算法和共生生物搜索算法相結(jié)合，設(shè)計(jì)了一種混合生物共生算法，并獲得了良好的性能。王凌等[5]利用訓(xùn)練好的指針網(wǎng)絡(luò)輸出初始解，設(shè)計(jì)一種帶反饋機(jī)制的迭代貪婪算法。

由此可見，種群初始化是群智能優(yōu)化算法的第一個階段，也是影響算法性能的一個重要因素。而深度強(qiáng)化學(xué)習(xí)技術(shù)求解組合優(yōu)化問題具有求解速度快、泛化能力強(qiáng)的優(yōu)點(diǎn)，并且可以利用訓(xùn)練好的網(wǎng)絡(luò)直接輸出問題的解。因此適合用來對群智能優(yōu)化算法的初始種群進(jìn)行初始化，以提高初始種群質(zhì)量，提升算法性能。近年來，在組合優(yōu)化領(lǐng)域出現(xiàn)了多個深度強(qiáng)化學(xué)習(xí)的新方法[6]，如指針網(wǎng)絡(luò)、圖神經(jīng)網(wǎng)絡(luò)。Vinyals等[7]提出了一種名為指針網(wǎng)絡(luò)的神經(jīng)架構(gòu)來學(xué)習(xí)輸出序列的條件概率，并用于求解旅行商問題。Bello等[8]提出了一個使用神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)來解決組合優(yōu)化問題的框架，在100個城市規(guī)模旅行商問題上接近最優(yōu)解。

因此本文將指針網(wǎng)絡(luò)和遺傳算法相結(jié)合，利用指針網(wǎng)絡(luò)來生成PFSP問題的初始序列，并用于遺傳算法初始種群的構(gòu)造，然后利用結(jié)合重啟機(jī)制和局部搜索技術(shù)的遺傳算法來獲得最終的解。通過仿真實(shí)驗(yàn)測試Reeves標(biāo)準(zhǔn)數(shù)據(jù)集，驗(yàn)證了算法的有效性。

1 置換流水車間調(diào)度問題描述

PFSP問題通常描述為n個工件J={1,…,n}在m臺機(jī)器M={1,…,m}上加工，每個工件在各機(jī)器上加工順序相同而且每臺機(jī)器加工的各工件順序也相同，給定工件i(i∈J)在機(jī)器j(j∈M)上的處理時間pij，目標(biāo)是求得一個工件加工順序使得某個調(diào)度目標(biāo)達(dá)到最優(yōu)，常用的調(diào)度目標(biāo)是最大完工時間Cmax。

PFSP問題的假設(shè)如下：（1）所有工件在零時刻均可加工；（2）工件在不同機(jī)器間的運(yùn)輸時間和設(shè)置時間包含在處理時間中；（3）每臺機(jī)器在同一時刻只能處理一個工件；（4）不允許作業(yè)搶占，即在每臺機(jī)器上工件一旦開始加工則不能中斷；（5）機(jī)器之間的緩沖區(qū)容量無限大。

令π=(π1,…,πn)代表所有工件一個加工序列，其中πi∈J。Cπi,j和pπi,j分別表示工件πi在機(jī)器j上的完成時間和加工時間。最大完工時間Cmax的計(jì)算過程如下：

置換流水車間調(diào)度的目標(biāo)是求得一個最優(yōu)工件加工順序π=(π1,…,πn)，使得Cmax最小。

2 指針網(wǎng)絡(luò)與遺傳算法求解流程

指針網(wǎng)絡(luò)改進(jìn)遺傳算法框架如圖1所示。

圖1 PN-HGA算法框架

2.1 指針網(wǎng)絡(luò)與參數(shù)優(yōu)化

2.1.1 數(shù)據(jù)預(yù)處理

傳統(tǒng)的指針網(wǎng)絡(luò)是用來求解TSP問題，編碼網(wǎng)絡(luò)的輸入為二維向量，而PFSP問題的輸入維度則是機(jī)器的數(shù)量m，因問題不同而不同，這導(dǎo)致指針網(wǎng)絡(luò)不能直接應(yīng)用于PFSP問題。

因此本文對PFSP問題的數(shù)據(jù)進(jìn)行預(yù)處理，考慮到標(biāo)準(zhǔn)算例（Carlier、Reeves、Taillard）的最大機(jī)器數(shù)為20，因此可以在算例數(shù)據(jù)后面增加（20-m）個所有工件加工時間都為0的機(jī)器，其最終的最大完工時間和原算例相同，并不會影響調(diào)度結(jié)果。因此對于一個n個工件，m(m≤20)個機(jī)器的調(diào)度問題，經(jīng)過預(yù)處理操作后轉(zhuǎn)化為一個n個工件，20個機(jī)器的調(diào)度問題。因此對于不同的調(diào)度問題，其機(jī)器維度固定為20，然后可以通過指針網(wǎng)絡(luò)進(jìn)行求解。

2.1.2 編碼與解碼

指針網(wǎng)絡(luò)包括兩個循環(huán)神經(jīng)網(wǎng)絡(luò)（RNN）模塊，編碼網(wǎng)絡(luò)和解碼網(wǎng)絡(luò)，如圖2所示。

圖2 指針網(wǎng)絡(luò)結(jié)構(gòu)

這兩個模塊都由長短期記憶（LSTM）網(wǎng)絡(luò)組成。編碼網(wǎng)絡(luò)讀取實(shí)例是由工件i在每臺機(jī)器上的處理時間組成的向量。每次讀取一個工件，并將其轉(zhuǎn)化為一系列的隱藏狀態(tài)。在第i步時：

式中：Whp、Whh、h0為待訓(xùn)練的網(wǎng)絡(luò)參數(shù)；sigmod()為激活函數(shù)；q()表示c是h1,…,h n線性組合；c為編碼網(wǎng)絡(luò)的最終輸出，是一個存儲了輸入序列信息的語義向量。

解碼網(wǎng)絡(luò)對語義向量c進(jìn)行解碼。在第一步解碼過程中，即t=0時，解碼網(wǎng)絡(luò)讀入語義向量c，輸出當(dāng)前的隱藏狀態(tài)s0，利用Ateention機(jī)制跟據(jù)s0和編碼器得到的各個工件的隱藏狀態(tài)計(jì)算選擇各個工件的概率，此時可選擇概率最大的節(jié)點(diǎn)作為第一步選擇的工件；在接下來的解碼過程中，即t=1,2,…,n時，解碼網(wǎng)絡(luò)讀入上一步的隱藏狀態(tài)和上一步選擇工件的特征向量，輸出當(dāng)前的隱藏狀態(tài)st。根據(jù)st和各個工件的隱藏狀態(tài)計(jì)算選擇各個工件的概率。繼續(xù)選擇具有最大概率值且沒有被選擇過的節(jié)點(diǎn)添加到解當(dāng)中，按照該方式不斷選擇工件，直至構(gòu)造一個完整的解。計(jì)算公式如下：

式中：v T、W1、W2、y0、Why、Whs為待訓(xùn)練的網(wǎng)絡(luò)參數(shù)；s0=c；y t∈o。

2.1.3 策略梯度優(yōu)化參數(shù)

由于采用監(jiān)督式的訓(xùn)練方式往往依賴高質(zhì)量的標(biāo)簽，而對于PFSP問題，獲得高質(zhì)量標(biāo)簽是很困難的。因此采用基于策略的強(qiáng)化學(xué)習(xí)來優(yōu)化指針網(wǎng)絡(luò)的參數(shù)。訓(xùn)練目標(biāo)是預(yù)期的完工時間，在給定實(shí)例o的情況下，該完工時間的期望如下：

假設(shè)實(shí)例o的加工時間服從分布O，則訓(xùn)練的目標(biāo)函數(shù)為：

采用策略梯度法優(yōu)化參數(shù)，上式的梯度是使用眾所周知的REINFORCE算法[9]來計(jì)算的：

式中：b(s)為不依賴于π的基線函數(shù)，并估計(jì)預(yù)期完工時間以減小梯度的方差。

在訓(xùn)練過程中，每次從分布S采樣M個實(shí)例，并對每個實(shí)例oi采樣一個加工序列πi～pθ(.|o i)，上式中的梯度用Monte Carlo采樣近似如下：

然后采用ADAM優(yōu)化器進(jìn)行參數(shù)優(yōu)化參數(shù)：

2.2 改進(jìn)的遺傳算法

現(xiàn)有遺傳算法求解PFSP問題通常使用NEH算法來生成一個解，然后隨機(jī)生成來初始化種群，而且在迭代后期通常由于種群多樣性降低而停滯在局部最優(yōu)值附近。因此本文通過訓(xùn)練的指針網(wǎng)絡(luò)與NEH算法相結(jié)合來初始化種群，以提高初始種群的質(zhì)量，并利用重啟機(jī)制，在算法陷入局部最優(yōu)的時候?qū)ΨN群進(jìn)行調(diào)整，來提高算法性能。

2.2.1 編碼與種群初始化

PFSP最常用的編碼是工件的簡單排列，排列中工件的相對順序表示車間機(jī)器對工件的加工順序。如一個個體為（2，1，3）表示工件2最先加工，然后加工工件1，最后加工工件3。

為了更好地理解本文初始化過程，簡要描述NEH過程[10]，該過程基于這樣的思想，即所有機(jī)器上總加工時間最長的工件應(yīng)該盡可能早地被調(diào)度。這種啟發(fā)式方法可以分為3個簡單的步驟如下。

（1）m臺機(jī)器上作業(yè)的總加工時間計(jì)算如下:

（2）工件按Pi的降序排序。然后，獲取前兩個工件（具有較高Pi的兩個工件），這兩個工件有兩種可能的加工序列，計(jì)算這兩個加工序列的完工時間，選擇完工時間較小的那個序列。

（3）繼續(xù)選擇第i個工件（Pi排第i的工件），并通過將其放置在已調(diào)度工件序列中所有可能的i位置來找到最佳調(diào)度序列。假如i=3，分別將其插入步驟（2）中選擇序列的頭部、中間和尾部生成3個序列，將選擇3個中的最佳序列用于下一次迭代。

初始化過程基于這個NEH算法和這個算法的修改，初始化種群采用兩種方法：第一種在步驟（2）中對工件進(jìn)行排序后，只需從有序列表中選擇兩個隨機(jī)工件，并用它們來交換前兩個工件，然后繼續(xù)步驟2和3的剩余部分來生成部分個體；第二種則在在步驟（2）中工件的序列為訓(xùn)練好的指針網(wǎng)絡(luò)生成的序列，之后和第一種方法一樣生成部分個體。

2.2.2 選擇與種群迭代方案

常用的選擇方案為輪盤賭選擇和錦標(biāo)賽選擇。本文選擇錦標(biāo)賽選擇，在整個種群中隨機(jī)抽取n個個體，選擇其中的最優(yōu)的個體作為父代個體。

種群迭代方案有子代取代種群中最差個體和子代直接取代父代的兩種方法。本文采用子代取代種群中最差個體的方法，即子代個體適應(yīng)度大于種群中最差個體的適應(yīng)度，并且子代并不存在與種群中的時候子代取代種群中最差個體。

2.2.3 交叉

遺傳交叉算子通過組合父代來產(chǎn)生新的子代。目標(biāo)是產(chǎn)生“更好的”子代，即在與父母雜交后創(chuàng)造更好的序列。常用的交叉算子有單點(diǎn)順序交叉（OP）、兩點(diǎn)順序交叉（TP）、部分匹配交叉（PMX）等。本文采取一種相似塊序兩點(diǎn)交叉（SBOX）的算子，該算子首先考慮至少兩個連續(xù)相同作業(yè)的塊，只有那些在父代中占據(jù)相同位置的相同塊才被直接復(fù)制到子代，然后再保留相同塊的基礎(chǔ)上采用單點(diǎn)順序交叉的方法對父代進(jìn)行交叉，具體過程如圖3所示。

圖3 SBOX算子

2.2.4 變異

遺傳算法中的變異算子主要是為了避免收斂到局部最優(yōu)，并在種群中重新引入丟失的基因。變異算子主要有互換突變、位置突變和移碼突變。本文采用移碼突變，即隨機(jī)選擇一個工件插入到另一個隨機(jī)的位置上去，具體過程如圖4所示。

圖4 移碼突變

2.2.5 重啟機(jī)制

在遺傳算法中，種群經(jīng)過多次迭代之后，種群的多樣性降低，使其停滯在局部最優(yōu)值附近。因此在遺傳算法中加入重啟機(jī)制：在每次迭代，存儲種群的最小完工時間mak i；如果mak i=maki-1則count mark+=1，否則countmark=0；如果countmar k＞Gr，則重新調(diào)整種群：首先將種群按照Cmax升序排序，將最小的20%加入新得種群，然后通過對最佳20%個體進(jìn)行移碼突變產(chǎn)生新的20%的個體加入新得種群，之后通過初始化種群的兩種方法分別生成20%的個體加入新得種群，剩余20%個體則隨機(jī)產(chǎn)生。

利用重啟機(jī)制，每當(dāng)種群中最小的最大完工時間超過Gr代不變時，重啟機(jī)制將替換種群中除20%以外的所有最佳個體，希望重新引入種群多樣性并脫離局部最優(yōu)。

2.2.6 局部搜索

局部搜索從個體中隨機(jī)提取所有工件，并將其重新插入所有可能的位置，當(dāng)找到更好的個體時，它將被保留，并且該過程將繼續(xù)，直到檢查完所有工件。對每一代中的所有個體應(yīng)用局部搜索會消耗很多時間，因此通常設(shè)置一個局部搜索概率Penh來控制個體是否進(jìn)行局部搜索。本文在變異之后以Penh的概率對子代進(jìn)行局部搜索，并且在每一代之后對種群中的最優(yōu)個體以2Penh的概率進(jìn)行局部搜索，以提高個體質(zhì)量。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)設(shè)計(jì)和參數(shù)設(shè)置

指針網(wǎng)絡(luò)訓(xùn)練階段相關(guān)參數(shù)設(shè)置如下：指針網(wǎng)絡(luò)每次采樣數(shù)（Batchsize）設(shè)為512，RNN采用長短時記憶網(wǎng)絡(luò)（LSTM），網(wǎng)絡(luò)隱藏層維數(shù)設(shè)為128，參數(shù)優(yōu)化采用Adam算法，學(xué)習(xí)率設(shè)為1×10-4，學(xué)習(xí)率衰減速率每5 000步0.96。網(wǎng)絡(luò)初始參數(shù)為[-0.08，0.08]之間均勻分布的隨機(jī)數(shù)。訓(xùn)練數(shù)據(jù)隨機(jī)生成1 024 000個數(shù)據(jù)，其中規(guī)模n_m=（30_5，30_10，30_15，30_20）的訓(xùn)練數(shù)據(jù)各占1/4，工件在各個機(jī)器上的加工時間為[0，1]均勻分布的隨機(jī)數(shù)，經(jīng)過預(yù)處理操作后進(jìn)行訓(xùn)練。

在遺傳算法迭代搜索環(huán)節(jié)相關(guān)參數(shù)設(shè)置如下：迭代次數(shù)為4 000，重啟參數(shù)Gr=25，種群規(guī)模Psize=20。遺傳算法中3個關(guān)鍵參數(shù)交叉概率Pc、變異概率Pm、局部搜索概率Penh的取值會影響算法的性能，因此采用Rec19算例進(jìn)行正交試驗(yàn)，每個參數(shù)設(shè)置4個水平值，數(shù)值如表1所示。

表1 參數(shù)水平

利用正交表L16進(jìn)行實(shí)驗(yàn)，在每組參數(shù)組合下獨(dú)立運(yùn)行算法10次，采用10次所得的完工時間平均值（AVG）作為響應(yīng)值，結(jié)果如表2所示。

表2 實(shí)驗(yàn)方案與實(shí)驗(yàn)結(jié)果

各參數(shù)響應(yīng)值如表3所示。由表3可知，Penh對算法性能的影響最大，Pc其次，Pm對性能的影響最小。根據(jù)試驗(yàn)結(jié)果的對比，最佳參數(shù)組合為：Pc=0.4，Pm=0.015，Penh=0.075。

表3 各參數(shù)響應(yīng)值

算法性能評價標(biāo)準(zhǔn)采用最優(yōu)相對誤差（Best Relative Error，BRE）和平均相對誤差（Average Relative Error，ARE），計(jì)算公式如下：

式中：Cmax為運(yùn)行10次中的最優(yōu)值；為運(yùn)行10次的平均值；C*為當(dāng)前算例的最優(yōu)解。

本文使用Python 3.7編程，進(jìn)行測試的平臺的參數(shù)如下：CPU為Intel（R）Core（TM）i5-8300H CPU@2.30 GHz，內(nèi)存16 GB，操作系統(tǒng)為Windows 10。

3.2 指針網(wǎng)絡(luò)效果檢驗(yàn)

為了驗(yàn)證指針網(wǎng)絡(luò)生成初始解的有效性，將指針網(wǎng)絡(luò)生成的解與NEH算法生成的解進(jìn)行比較。選擇PFSP問題常用的Rec測試算例，指針網(wǎng)絡(luò)獨(dú)立運(yùn)行10次，取最優(yōu)相對誤差進(jìn)行比較。比較結(jié)果如表4所示。從表中可以看出，指針網(wǎng)絡(luò)生成的解有13算例結(jié)果優(yōu)于NEH算法，因此采用指針網(wǎng)絡(luò)與NEH算法結(jié)合來初始化遺傳算法能夠提高初始種群的質(zhì)量。雖然21個算例的平均值指針網(wǎng)絡(luò)結(jié)果比NEH算法差，主要是由于訓(xùn)練網(wǎng)絡(luò)的數(shù)據(jù)最大為30個工件，而最后3個算例（Rec37、Rec39、Rec41）的工件數(shù)達(dá)到75個，因此在這幾個算例上指針網(wǎng)絡(luò)表現(xiàn)很差，拉高了指針網(wǎng)絡(luò)的最優(yōu)相對誤差的平均值。

表4 指針網(wǎng)絡(luò)與NEH算法結(jié)果

3.3 PT-HGA算法結(jié)果

為了驗(yàn)證PN-HGA算法求解PFSP問題的性能，選擇PFSP問題常用的Rec測試算例，并將PN-HGA與求解PFSP的混合遺傳算法（HGA）[3]、變參數(shù)量子進(jìn)化算法（VP-QEA）[11]、混合差分進(jìn)化算法（L-HDE）[12]、混合共生生物搜索算法（HSOS）[4]的求解結(jié)果進(jìn)行比較，比較結(jié)果如表5所示。從表5可以看出，PN-HGA算法求解的21個算例有19個算例的最優(yōu)相對誤差和15個算例的平均相對誤差等于或優(yōu)于所比較的幾種算法。而從整體上來看，PN-HGA的最優(yōu)相對誤差的平均值為0.375，平均相對誤差的平均值為0.630，均優(yōu)于其他4種算法，證明了PN-HGA算法的有效性。

表5 測試結(jié)果比較

4 結(jié)束語

本文提出了求解置換流水車間調(diào)度問題的一種指針網(wǎng)絡(luò)與遺傳算法結(jié)合的框架，創(chuàng)新之處：首先，根據(jù)PFSP問題與指針網(wǎng)絡(luò)的特點(diǎn)對算例進(jìn)行預(yù)處理，使得訓(xùn)練的指針網(wǎng)絡(luò)可以適用于不同規(guī)模的算例，通過與NEH算法比較，驗(yàn)證了指針網(wǎng)絡(luò)的性能；其次，將指針網(wǎng)絡(luò)生成的解并結(jié)合NEH算法用來初始化遺傳算法的初始種群，以提高種群質(zhì)量，提升算法性能，并利用重啟機(jī)制來提高算法的全局搜索能力。通過對Reeves標(biāo)準(zhǔn)測試集進(jìn)行仿真測試，并與4種智能優(yōu)化算法相比較，驗(yàn)證了本文算法的有效性。未來的研究著重于優(yōu)化模型的訓(xùn)練，以提供更高質(zhì)量的解，提升算法的性能，并將算法應(yīng)用于其他類型的調(diào)度問題。