基于深度強化學習的柔性作業車間調度方法＊

崔雪艷 萬爛軍 趙昊鑫 李長云

（①湖南工業大學計算機學院，湖南 株洲 412007；②智能信息感知及處理技術湖南省重點實驗室，湖南 株洲 412007）

生產調度在制造系統中起著至關重要的作用，有效的調度方案是提高生產效率和提高資源利用率的重要因素。柔性作業車間調度（flexible job shop scheduling，FJSP）問題[1]中每道工序可在多個機臺上處理，每個機臺可處理多道工序。在FJSP 中，機臺的柔性引入更符合制造系統的實際情況，能夠提高制造系統的生產效率，但擴大了可行解的范圍，進而增加了生產調度的難度和復雜性。

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

這些元啟發式算法雖然可以獲得高質量的調度方案，但當問題規模增大時，求解FJSP 的計算時間迅速增長，導致其難以滿足快速調度的需求。此外，一旦問題結構發生變化，需重新調整算法參數。而深度強化學習結合了深度學習的感知能力和強化學習的決策能力，在求解車間調度問題方面具有很大的潛力。因此，本文提出了一種有效求解FJSP的深度演員評論家強化學習方法，并采用不同規模的基準實例對該方法進行了驗證。

1 基本理論

強化學習通過智能體與環境的交互，學習從環境狀態到行為的映射，從而獲得最大的獎勵。強化學習的模型框架如圖1 所示。在t時刻，從環境中獲取當前的狀態，智能體在動作空間中選出一個動作，執行動作后，狀態更新為下一狀態，同時環境給出獎勵。

圖1 強化學習的模型框架

2 FJSP 轉化

2.1 問題定義

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

為了簡化問題，需滿足以下約束條件：每個機臺一次只能加工一道工序；每個工件都由一個固定的工序序列組成；工序只能在指定的機臺上加工；工序在不同的機臺上加工，加工時間可能不同；一旦在機臺上開始了一個操作，就不能中斷；不考慮機臺之間的運輸時間。

本文的目標是最小化所有工件的最大完工時間，目標函數為

2.2 問題建模

隨著FJSP 規模的增加，單個智能體的集中控制計算復雜度也隨之增加，從而導致在解決大規模FJSP 時適應性較差。為了解決這一問題，將FJSP建模為一個多智能體馬爾科夫決策過程，其中，將機臺視為智能體，并對多智能體馬爾科夫決策過程中的狀態空間、動作空間以及獎勵函數進行設計。

狀態空間描述了機臺智能體在不同時間的生產加工場景信息，具體來說，狀態空間包括狀態矩陣Sm、機臺可加工矩陣Am和工序加工時間矩陣Pm。Sm表示每道工序的調度狀態，“0”表示該工序未被調度，“1”表示該工序已被調度。Am表示機臺的加工能力，“1”表示該機臺可加工該工序，“0”表示該機臺不可加工該工序。Pm表示每道工序在不同機臺上的加工時間。這3 個矩陣代表了狀態的3 個不同通道，作為卷積神經網絡的輸入。

動作空間包含了智能體可選擇的所有動作。由于目標函數是最小化最大完工時間，因此選擇了一些與Ji的總工時以及Oi,j的Pi,j,k相關的調度規則作為動作。表1 展示了動作空間包含的8 個簡單的調度規則。

表1 調度規則表

演員網絡輸出動作at后，機臺智能體會根據at對應的調度規則來確定被調度的工序，隨后FJSP環境會給予一個即時獎勵rt。即時獎勵反映了at對調度方案產生的短期影響。即時獎勵的計算見式（2）。其中：Ct-1表示當前調度t步的上一步求解FJSP 實例所得的最大完工時間。

3 基于深度強化學習求解FJSP

3.1 網絡結構設計

基于深度強化學習求解FJSP 的總體框架如圖2所示，在該方法中，構建一個演員評論家（actor critic flexible job shop scheduling，AC-FJSP）模型。其中：演員網絡的輸入為狀態，輸出為調度規則。智能體根據輸出的調度規則選擇合適的工序，當該工序被調度后，環境給出獎勵，將狀態和獎勵輸入給評論家網絡，評論家網絡去評估該調度規則并反饋給演員網絡以更好地調整調度策略。

圖2 基于深度強化學習求解FJSP 的總體框架

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

表2 AC-FJSP 模型的網絡結構

3.2 模型訓練

用于求解FJSP 的AC-FJSP 模型的訓練過程，具體步驟如下。

步驟1：確定完整調度次數I、用于模型訓練的FJSP 實例、學習率lr。

步驟2：初始化演員網絡和評論家網絡。

步驟3：根據FJSP 實例構建狀態空間中的3 個矩陣Sm、Am和Pm。

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

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

步驟6：獲取當前狀態st，演員網絡通過Softmax 策略輸出動作at。

步驟7：判斷Gset是否為空，若是，則即時獎勵rt取值為零；若否，根據動作at從Gset中選出符合該調度規則的工序Oi,j。

步驟8：獲取每個機臺上當前已被加工的最后一道工序的結束時間并取其中的最大值作為當前的最大完工時間。

步驟9：更新下一狀態st+1，并根據式（2）計算rt。

步驟10：采用Shared-Adam 優化器進行網絡參數的更新。

步驟11：判斷當前FJSP 實例的所有工序是否均被調度，若是，結束此次完整調度；否則，重復執行步驟5 至步驟10。

步驟12：重復執行步驟4 至步驟11，直到完成第I次完整調度為止，從而獲得訓練好的ACFJSP 模型的網絡參數，并保存該模型。

4 實驗

4.1 實驗設置

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

對比方法：本文提出的方法與加工時間最短（shortest processing time，SPT）、剩余加工時間最長（longest remaining processing time，LRPT）、當前工序的加工時間與總工時之比最小（smallest ratio of processing time to total work，SPT/TW）3 條啟發式調度規則，改進遺傳算法（improved genetic algorithm，IGA）[4]和混合離散粒子群算法（hybrid discrete particle swarm optimization，HDPSO）[9]進行比較。

完整調度的迭代次數為300 次，學習率為0.005。神經網絡的優化器為Share-Adam，其中betas參數設置為0.99，eps參數設置為10-8。

實驗平臺的硬件配置如下：一個8 核的Intel Core i7-9700K CPU、2560 核NVIDIA GeForce RTX 2070 SUPER GPU 以及64GB 內存。實驗平臺的軟件配置如下：Python 3.7、Pytorch 1.6。

4.2 比較求解質量

為驗證AC-FJSP 的有效性，與啟發式調度規則、IGA 和HDPSO 比較求解實例的最大完工時間。ACFJSP 相對最優啟發式調度規則的優化率Arate的計算式為

AC-FJSP 相對于IGA 和HDPSO 的優化率Brate的計算式為

式中：ZH表示啟發式調度規則的最優解，ZA表示AC-FJSP 的解，ZY表示IGA 和HDPSO 的最優解。

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

表3 求解FJSP 實例的最大完工時間

4.3 比較求解效率

為進一步驗證AC-FJSP 的有效性，與啟發式調度規則、IGA 和HDPSO 比較求解效率。AC-FJSP相比啟發式調度規則最短計算時間的提升率Crate的計算式為

AC-FJSP 相對于IGA 和HDPSO 的最短計算時間的提升率Drate計算式為

式中：TH為啟發式調度規則的最短計算時間；TA為AC-FJSP 的計算時間；TY為IGA 和HDPSO 的最短計算時間。

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

表4 求解FJSP 實例的計算時間

圖3 求解超大規模FJSP 實例的執行時間

5 結語

本文提出了一種有效求解大規模柔性作業車間調度問題的深度強化學習方法，以最小化最大完工時間為優化目標構建了一個AC-FJSP 模型，機臺智能體根據演員網絡輸出的調度規則選擇合適的工序進行調度。為驗證提出方法的有效性，采用啟發式調度規則、IGA、HDPSO 和提出的方法開展一系列對比實驗。結果表明提出的方法在求解質量方面優于啟發式調度規則，在求解效率方面優于元啟發式算法。

在實際工業生產中可能存在機器故障和緊急插單等動態事件。TD3 算法具有強大的學習能力和穩定性，適合處理連續動作空間的問題。因此，下一步將采用TD3 算法來求解動態柔性作業車間調度問題。