崔雪艷 萬(wàn)爛軍 趙昊鑫 李長(zhǎng)云

（①湖南工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，湖南 株洲 412007；②智能信息感知及處理技術(shù)湖南省重點(diǎn)實(shí)驗(yàn)室，湖南 株洲 412007）

生產(chǎn)調(diào)度在制造系統(tǒng)中起著至關(guān)重要的作用，有效的調(diào)度方案是提高生產(chǎn)效率和提高資源利用率的重要因素。柔性作業(yè)車間調(diào)度（flexible job shop scheduling，F(xiàn)JSP）問(wèn)題[1]中每道工序可在多個(gè)機(jī)臺(tái)上處理，每個(gè)機(jī)臺(tái)可處理多道工序。在FJSP 中，機(jī)臺(tái)的柔性引入更符合制造系統(tǒng)的實(shí)際情況，能夠提高制造系統(tǒng)的生產(chǎn)效率，但擴(kuò)大了可行解的范圍，進(jìn)而增加了生產(chǎn)調(diào)度的難度和復(fù)雜性。

近年來(lái)，眾多學(xué)者已對(duì)FJSP 展開(kāi)了廣泛的研究。啟發(fā)式調(diào)度規(guī)則[2]可對(duì)動(dòng)態(tài)事件做出即時(shí)響應(yīng)，但由于不同調(diào)度環(huán)境會(huì)對(duì)調(diào)度性能產(chǎn)生影響，因此很難保證找到最優(yōu)調(diào)度方案。元啟發(fā)式算法通常通過(guò)進(jìn)化算子或粒子運(yùn)動(dòng)來(lái)迭代地搜索調(diào)度方案[3]，用于求解FJSP 的元啟發(fā)式算法主要包括遺傳算法[4-7]、粒子群優(yōu)化[8-9]、人工蜂群[10-11]、鯨魚(yú)優(yōu)化算法[12-13]以及灰狼算法[14-15]等。Chen N L 等[6]針對(duì)具有不確定加工時(shí)間的FJSP，提出了一種精英遺傳算法。Li Y B 等[11]提出了一種改進(jìn)的人工蜂群算法來(lái)求解FJSP，該算法采用三維編碼/解碼機(jī)制和動(dòng)態(tài)鄰域搜索提升了算法的性能。Liu Z F 等[8]提出了一種可變鄰域的混合遺傳粒子群算法來(lái)求解FJSP，將粒子群作為遺傳算法的變異算子有效地提升了收斂速度。Yang W Q 等[12]提出了一種混合鯨魚(yú)算法來(lái)求解FJSP，其中使用種群多樣性機(jī)制來(lái)確保種群多樣性在迭代過(guò)程中保持穩(wěn)定。為了解決FJSP，李寶帥和葉春明[13]提出了一種混合正余弦鯨魚(yú)優(yōu)化算法。Li X Y 等[14]提出了一種改進(jìn)的灰狼優(yōu)化算法來(lái)求解分布式FJSP，該算法設(shè)計(jì)了4 個(gè)交叉算子來(lái)拓展搜索空間。Lin C R 等[15]提出了一種基于學(xué)習(xí)的灰狼優(yōu)化算法來(lái)求解具有額外資源和機(jī)臺(tái)準(zhǔn)備時(shí)間的隨機(jī)柔性作業(yè)車間調(diào)度問(wèn)題。

這些元啟發(fā)式算法雖然可以獲得高質(zhì)量的調(diào)度方案，但當(dāng)問(wèn)題規(guī)模增大時(shí)，求解FJSP 的計(jì)算時(shí)間迅速增長(zhǎng)，導(dǎo)致其難以滿足快速調(diào)度的需求。此外，一旦問(wèn)題結(jié)構(gòu)發(fā)生變化，需重新調(diào)整算法參數(shù)。而深度強(qiáng)化學(xué)習(xí)結(jié)合了深度學(xué)習(xí)的感知能力和強(qiáng)化學(xué)習(xí)的決策能力，在求解車間調(diào)度問(wèn)題方面具有很大的潛力。因此，本文提出了一種有效求解FJSP的深度演員評(píng)論家強(qiáng)化學(xué)習(xí)方法，并采用不同規(guī)模的基準(zhǔn)實(shí)例對(duì)該方法進(jìn)行了驗(yàn)證。

1 基本理論

強(qiáng)化學(xué)習(xí)通過(guò)智能體與環(huán)境的交互，學(xué)習(xí)從環(huán)境狀態(tài)到行為的映射，從而獲得最大的獎(jiǎng)勵(lì)。強(qiáng)化學(xué)習(xí)的模型框架如圖1 所示。在t時(shí)刻，從環(huán)境中獲取當(dāng)前的狀態(tài)，智能體在動(dòng)作空間中選出一個(gè)動(dòng)作，執(zhí)行動(dòng)作后，狀態(tài)更新為下一狀態(tài)，同時(shí)環(huán)境給出獎(jiǎng)勵(lì)。

圖1 強(qiáng)化學(xué)習(xí)的模型框架

2 FJSP 轉(zhuǎn)化

2.1 問(wèn)題定義

FJSP 描述如下：在m臺(tái)機(jī)臺(tái)M={M1,M2,···,Mm}上可加工n個(gè)工件 J={J1,J2,···,Jn}。每個(gè)工件Ji由p道連續(xù)的工序組成，每道工序Oi,j都可在匹配的機(jī)器Mi,j? M 上進(jìn)行加工，其中Oi,j表示工件Ji的第j道工序，Pi,j,k表示Oi,j在機(jī)臺(tái)Mk上的加工時(shí)間。Si,j和Ei,j為工序Oi,j的開(kāi)始時(shí)間和結(jié)束時(shí)間，Ct為調(diào)度t步后FJSP 實(shí)例的最大完工時(shí)間。

為了簡(jiǎn)化問(wèn)題，需滿足以下約束條件：每個(gè)機(jī)臺(tái)一次只能加工一道工序；每個(gè)工件都由一個(gè)固定的工序序列組成；工序只能在指定的機(jī)臺(tái)上加工；工序在不同的機(jī)臺(tái)上加工，加工時(shí)間可能不同；一旦在機(jī)臺(tái)上開(kāi)始了一個(gè)操作，就不能中斷；不考慮機(jī)臺(tái)之間的運(yùn)輸時(shí)間。

本文的目標(biāo)是最小化所有工件的最大完工時(shí)間，目標(biāo)函數(shù)為

2.2 問(wèn)題建模

隨著FJSP 規(guī)模的增加，單個(gè)智能體的集中控制計(jì)算復(fù)雜度也隨之增加，從而導(dǎo)致在解決大規(guī)模FJSP 時(shí)適應(yīng)性較差。為了解決這一問(wèn)題，將FJSP建模為一個(gè)多智能體馬爾科夫決策過(guò)程，其中，將機(jī)臺(tái)視為智能體，并對(duì)多智能體馬爾科夫決策過(guò)程中的狀態(tài)空間、動(dòng)作空間以及獎(jiǎng)勵(lì)函數(shù)進(jìn)行設(shè)計(jì)。

狀態(tài)空間描述了機(jī)臺(tái)智能體在不同時(shí)間的生產(chǎn)加工場(chǎng)景信息，具體來(lái)說(shuō)，狀態(tài)空間包括狀態(tài)矩陣Sm、機(jī)臺(tái)可加工矩陣Am和工序加工時(shí)間矩陣Pm。Sm表示每道工序的調(diào)度狀態(tài)，“0”表示該工序未被調(diào)度，“1”表示該工序已被調(diào)度。Am表示機(jī)臺(tái)的加工能力，“1”表示該機(jī)臺(tái)可加工該工序，“0”表示該機(jī)臺(tái)不可加工該工序。Pm表示每道工序在不同機(jī)臺(tái)上的加工時(shí)間。這3 個(gè)矩陣代表了狀態(tài)的3 個(gè)不同通道，作為卷積神經(jīng)網(wǎng)絡(luò)的輸入。

動(dòng)作空間包含了智能體可選擇的所有動(dòng)作。由于目標(biāo)函數(shù)是最小化最大完工時(shí)間，因此選擇了一些與Ji的總工時(shí)以及Oi,j的Pi,j,k相關(guān)的調(diào)度規(guī)則作為動(dòng)作。表1 展示了動(dòng)作空間包含的8 個(gè)簡(jiǎn)單的調(diào)度規(guī)則。

表1 調(diào)度規(guī)則表

演員網(wǎng)絡(luò)輸出動(dòng)作at后，機(jī)臺(tái)智能體會(huì)根據(jù)at對(duì)應(yīng)的調(diào)度規(guī)則來(lái)確定被調(diào)度的工序，隨后FJSP環(huán)境會(huì)給予一個(gè)即時(shí)獎(jiǎng)勵(lì)rt。即時(shí)獎(jiǎng)勵(lì)反映了at對(duì)調(diào)度方案產(chǎn)生的短期影響。即時(shí)獎(jiǎng)勵(lì)的計(jì)算見(jiàn)式（2）。其中：Ct-1表示當(dāng)前調(diào)度t步的上一步求解FJSP 實(shí)例所得的最大完工時(shí)間。

3 基于深度強(qiáng)化學(xué)習(xí)求解FJSP

3.1 網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)

基于深度強(qiáng)化學(xué)習(xí)求解FJSP 的總體框架如圖2所示，在該方法中，構(gòu)建一個(gè)演員評(píng)論家（actor critic flexible job shop scheduling，AC-FJSP）模型。其中：演員網(wǎng)絡(luò)的輸入為狀態(tài)，輸出為調(diào)度規(guī)則。智能體根據(jù)輸出的調(diào)度規(guī)則選擇合適的工序，當(dāng)該工序被調(diào)度后，環(huán)境給出獎(jiǎng)勵(lì)，將狀態(tài)和獎(jiǎng)勵(lì)輸入給評(píng)論家網(wǎng)絡(luò)，評(píng)論家網(wǎng)絡(luò)去評(píng)估該調(diào)度規(guī)則并反饋給演員網(wǎng)絡(luò)以更好地調(diào)整調(diào)度策略。

圖2 基于深度強(qiáng)化學(xué)習(xí)求解FJSP 的總體框架

基于深度強(qiáng)化學(xué)習(xí)的AC-FJSP 模型的網(wǎng)絡(luò)結(jié)構(gòu)見(jiàn)表2。該模型由2 個(gè)卷積層、4 個(gè)BN 層、4 個(gè)全連接層組成。Conv1 和Conv2 為演員網(wǎng)絡(luò)與評(píng)論家網(wǎng)絡(luò)共享的卷積層。在Conv1 和Conv2 中，都使用16 個(gè)大小為1×1 的卷積核，padding 設(shè)置為零填充，以保證卷積后的特征圖與輸入數(shù)據(jù)的大小保持一致。在Conv1 和Conv2 后分別采用BN1 和BN2進(jìn)行二維批歸一化處理，可加快網(wǎng)絡(luò)的訓(xùn)練速度并防止過(guò)擬合。FC1、BN3 和FC2 是演員網(wǎng)絡(luò)的層，用于生成調(diào)度策略并輸出動(dòng)作。FC3、BN4 和FC4是評(píng)論家網(wǎng)絡(luò)的層，用于估計(jì)狀態(tài)值函數(shù)并輸出狀態(tài)值。FC1、FC2、FC3 和FC4 中都使用100 個(gè)神經(jīng)元。在FC1 和FC3 后分別采用BN3 和BN4 進(jìn)行一維批歸一化處理。此外，在Conv1、Conv2、FC1和FC3 后使用ReLU 激活函數(shù)，可增強(qiáng)模型的表達(dá)能力。

表2 AC-FJSP 模型的網(wǎng)絡(luò)結(jié)構(gòu)

3.2 模型訓(xùn)練

用于求解FJSP 的AC-FJSP 模型的訓(xùn)練過(guò)程，具體步驟如下。

步驟1：確定完整調(diào)度次數(shù)I、用于模型訓(xùn)練的FJSP 實(shí)例、學(xué)習(xí)率lr。

步驟2：初始化演員網(wǎng)絡(luò)和評(píng)論家網(wǎng)絡(luò)。

步驟3：根據(jù)FJSP 實(shí)例構(gòu)建狀態(tài)空間中的3 個(gè)矩陣Sm、Am和Pm。

步驟4：初始化Sm、Am和Pm。

步驟5：獲取可加工工序集合Gset，其中待選的工序Oi,j需滿足3 個(gè)條件，即Oi,j未被加工、Oi,j的上一道工序Oi,j-1已被加工、Oi,j可被Mk加工。

步驟6：獲取當(dāng)前狀態(tài)st，演員網(wǎng)絡(luò)通過(guò)Softmax 策略輸出動(dòng)作at。

步驟7：判斷Gset是否為空，若是，則即時(shí)獎(jiǎng)勵(lì)rt取值為零；若否，根據(jù)動(dòng)作at從Gset中選出符合該調(diào)度規(guī)則的工序Oi,j。

步驟8：獲取每個(gè)機(jī)臺(tái)上當(dāng)前已被加工的最后一道工序的結(jié)束時(shí)間并取其中的最大值作為當(dāng)前的最大完工時(shí)間。

步驟9：更新下一狀態(tài)st+1，并根據(jù)式（2）計(jì)算rt。

步驟10：采用Shared-Adam 優(yōu)化器進(jìn)行網(wǎng)絡(luò)參數(shù)的更新。

步驟11：判斷當(dāng)前FJSP 實(shí)例的所有工序是否均被調(diào)度，若是，結(jié)束此次完整調(diào)度；否則，重復(fù)執(zhí)行步驟5 至步驟10。

步驟12：重復(fù)執(zhí)行步驟4 至步驟11，直到完成第I次完整調(diào)度為止，從而獲得訓(xùn)練好的ACFJSP 模型的網(wǎng)絡(luò)參數(shù)，并保存該模型。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

為驗(yàn)證本文提出的方法求解柔性作業(yè)車間調(diào)度的有效性，在不同規(guī)模的FJSP 實(shí)例上進(jìn)行測(cè)試。根據(jù)實(shí)例的規(guī)模大小，分為小規(guī)模實(shí)例、中規(guī)模實(shí)例、大規(guī)模實(shí)例以及超大規(guī)模實(shí)例4 大組。其中：小規(guī)模有10×5、15×5、20×5 和10×10；中規(guī)模有10×20、20×10、10×40 和15×15；大規(guī)模有20×40、20×60、50×20 和 50×40；超大規(guī)模有 50×60、100×20、100×40 和100×60。實(shí)例規(guī)模為10×5 表示該實(shí)例中包含10 個(gè)待加工的工件和5 臺(tái)可加工工件的機(jī)臺(tái)。根據(jù)數(shù)據(jù)來(lái)源，分為Hurink J[16]實(shí)例和Behnke D[17]實(shí)例，加粗體表示求解某實(shí)例最佳的最大完工時(shí)間。

對(duì)比方法：本文提出的方法與加工時(shí)間最短（shortest processing time，SPT）、剩余加工時(shí)間最長(zhǎng)（longest remaining processing time，LRPT）、當(dāng)前工序的加工時(shí)間與總工時(shí)之比最?。╯mallest ratio of processing time to total work，SPT/TW）3 條啟發(fā)式調(diào)度規(guī)則，改進(jìn)遺傳算法（improved genetic algorithm，IGA）[4]和混合離散粒子群算法（hybrid discrete particle swarm optimization，HDPSO）[9]進(jìn)行比較。

完整調(diào)度的迭代次數(shù)為300 次，學(xué)習(xí)率為0.005。神經(jīng)網(wǎng)絡(luò)的優(yōu)化器為Share-Adam，其中betas參數(shù)設(shè)置為0.99，eps參數(shù)設(shè)置為10-8。

實(shí)驗(yàn)平臺(tái)的硬件配置如下：一個(gè)8 核的Intel Core i7-9700K CPU、2560 核NVIDIA GeForce RTX 2070 SUPER GPU 以及64GB 內(nèi)存。實(shí)驗(yàn)平臺(tái)的軟件配置如下：Python 3.7、Pytorch 1.6。

4.2 比較求解質(zhì)量

為驗(yàn)證AC-FJSP 的有效性，與啟發(fā)式調(diào)度規(guī)則、IGA 和HDPSO 比較求解實(shí)例的最大完工時(shí)間。ACFJSP 相對(duì)最優(yōu)啟發(fā)式調(diào)度規(guī)則的優(yōu)化率Arate的計(jì)算式為

AC-FJSP 相對(duì)于IGA 和HDPSO 的優(yōu)化率Brate的計(jì)算式為

式中：ZH表示啟發(fā)式調(diào)度規(guī)則的最優(yōu)解，ZA表示AC-FJSP 的解，ZY表示IGA 和HDPSO 的最優(yōu)解。

表3 展示了啟發(fā)式調(diào)度規(guī)則、IGA 和HDPSO求解不同規(guī)模的FJSP 實(shí)例的最大完工時(shí)間。求解10×5、20×5 和10×40 規(guī)模實(shí)例的最佳調(diào)度規(guī)則分別是LRPT、SPT/TW 和SPT。由表3 可知，不同規(guī)模的FJSP 實(shí)例中，啟發(fā)式調(diào)度規(guī)則性能不穩(wěn)定。ACFJSP 求解的結(jié)果與啟發(fā)式調(diào)度規(guī)則相比較，優(yōu)化率最高有63.2%，最低也有12.7%。AC-FJSP 求解的結(jié)果與IGA 和HDPSO 相比較，求解不同規(guī)模FJSP 實(shí)例的最大完工時(shí)間均相近。上述實(shí)驗(yàn)結(jié)果表明AC-FJSP 的求解性能穩(wěn)定且優(yōu)，泛化性較好。原因在于AC-FJSP 的動(dòng)作空間包含了多個(gè)調(diào)度規(guī)則，通過(guò)訓(xùn)練，AC-FJSP 可自適應(yīng)地選擇合適的調(diào)度規(guī)則，而不是使用同一個(gè)調(diào)度規(guī)則求解所有的FJSP實(shí)例。

表3 求解FJSP 實(shí)例的最大完工時(shí)間

4.3 比較求解效率

為進(jìn)一步驗(yàn)證AC-FJSP 的有效性，與啟發(fā)式調(diào)度規(guī)則、IGA 和HDPSO 比較求解效率。AC-FJSP相比啟發(fā)式調(diào)度規(guī)則最短計(jì)算時(shí)間的提升率Crate的計(jì)算式為

AC-FJSP 相對(duì)于IGA 和HDPSO 的最短計(jì)算時(shí)間的提升率Drate計(jì)算式為

式中：TH為啟發(fā)式調(diào)度規(guī)則的最短計(jì)算時(shí)間；TA為AC-FJSP 的計(jì)算時(shí)間；TY為IGA 和HDPSO 的最短計(jì)算時(shí)間。

表4 展示了啟發(fā)式調(diào)度規(guī)則、IGA 和HDPSO求解不同規(guī)模的FJSP 實(shí)例的計(jì)算時(shí)間。啟發(fā)式調(diào)度規(guī)則和AC-FJSP 在求解小規(guī)模和中規(guī)模FJSP 實(shí)例的計(jì)算時(shí)間均在8 s 內(nèi)，求解大規(guī)模實(shí)例的計(jì)算時(shí)間均在110 s 內(nèi)。圖3 所示為求解超大規(guī)模FJSP實(shí)例的執(zhí)行時(shí)間。就算求解超大規(guī)模的實(shí)例，ACFJSP 的計(jì)算時(shí)間也與啟發(fā)式調(diào)度規(guī)則的計(jì)算時(shí)間相接近。與IGA 和HDPSO 相比較，AC-FJSP 的計(jì)算時(shí)間的提升率最高有98.1%，在求解超大規(guī)模實(shí)例時(shí)提升率最低也有60.3%。原因在于演員評(píng)論家算法可進(jìn)行單步更新，提高了學(xué)習(xí)效率。當(dāng)訓(xùn)練完成后，模型已經(jīng)學(xué)習(xí)到最優(yōu)的參數(shù)，可快速地進(jìn)行調(diào)度，從而縮短了計(jì)算時(shí)間。AC-FJSP 利用大規(guī)模實(shí)例進(jìn)行訓(xùn)練，其他實(shí)例可利用該模型在較短的時(shí)間內(nèi)得到一個(gè)較好的調(diào)度方案。

表4 求解FJSP 實(shí)例的計(jì)算時(shí)間

圖3 求解超大規(guī)模FJSP 實(shí)例的執(zhí)行時(shí)間

5 結(jié)語(yǔ)

本文提出了一種有效求解大規(guī)模柔性作業(yè)車間調(diào)度問(wèn)題的深度強(qiáng)化學(xué)習(xí)方法，以最小化最大完工時(shí)間為優(yōu)化目標(biāo)構(gòu)建了一個(gè)AC-FJSP 模型，機(jī)臺(tái)智能體根據(jù)演員網(wǎng)絡(luò)輸出的調(diào)度規(guī)則選擇合適的工序進(jìn)行調(diào)度。為驗(yàn)證提出方法的有效性，采用啟發(fā)式調(diào)度規(guī)則、IGA、HDPSO 和提出的方法開(kāi)展一系列對(duì)比實(shí)驗(yàn)。結(jié)果表明提出的方法在求解質(zhì)量方面優(yōu)于啟發(fā)式調(diào)度規(guī)則，在求解效率方面優(yōu)于元啟發(fā)式算法。

在實(shí)際工業(yè)生產(chǎn)中可能存在機(jī)器故障和緊急插單等動(dòng)態(tài)事件。TD3 算法具有強(qiáng)大的學(xué)習(xí)能力和穩(wěn)定性，適合處理連續(xù)動(dòng)作空間的問(wèn)題。因此，下一步將采用TD3 算法來(lái)求解動(dòng)態(tài)柔性作業(yè)車間調(diào)度問(wèn)題。