基于DDQN算法的混流車間作業動態自適應調度的研究

陳曉航 王美林 吳耿楓 梁凱晴

摘 ?要：大規模生產的混流車間制造系統存在資源規模大、約束多等問題，快速找到合適的調度策略是實現高效生產的關鍵。為解決傳統數學規劃算法和啟發式算法存在的策略求解效率低、自適應性差等問題，文章提出一種基于DDQN的智能車間動態自適應調度方法，對車間作業的自適應調度做了研究。通過“一步一推理”的自適用動態調度，可以高效地匹配合適的調度策略動作。

關鍵詞：深度強化學習;DDQN算法;動態自適應調度

中圖分類號：TP18 ? ? ? 文獻標識碼：A文章編號：2096-4706（2021）24-0133-06

Abstract： In view of the large scale of resources and many constraints of the hybrid flow workshop manufacturing system in mass production， how to quickly find a suitable scheduling strategy is the key to achieve efficient production. In order to solve the problems of low strategy solving efficiency and poor adaptive existing in traditional mathematical programming algorithms and heuristic algorithms， this paper proposes a dynamic adaptive scheduling method for intelligent workshop based on DDQN， research on adaptive scheduling of workshop operations. Through the self-adaptive dynamic scheduling of “one step， one reasoning”， the appropriate scheduling policy actions can be efficiently matched.

Keywords： deep reinforcement learning; DDQN algorithm; dynamic adaptive scheduling

0 ?引 ?言

在“中國制造2025”背景下，面向大批量定制生產的混流制造HFS（Hybrid Flow Shop， HFS）是一種主流生產組織模式。而HFS調度已被證明是一個NP-Hard（Non-deterministic Polynomial Hard）的問題，對于稍大規模的調度問題，在車間實際生產中往往會有各種復雜的干擾元素。因此，如何解決這些因素對車間作業調度的干擾問題，保證生產的順利進行，就成為一個非常有意義的研究方向。

針對制造過程的動態自適應調度，在相當多的制造領域已經得到研究。車間現場的動態調度，傳統的做法是采用反應式，預測反應式，前攝式，或滾動式等方式重調度或修補調度。文獻[2]中針對在車間復雜動態環境下的制造企業生產過程執行系統MES，建立了自適應調度模型進行研究。文獻[3]中針對Agent技術構建基于問題的功能模塊，提出一種基于改進-學習算法（WSQ）的自適應調度機制。文獻[4]中Sahman針對分布式作業車間調度問題，將貪婪啟發式方法與DSHO算法相結合進行求解。文獻[7]采用了多優先規則啟發式的調度方式，文獻[10]針對凸輪從動機構的優化設計，采用元啟發式算法進行了研究。文獻[14]采用反應式調度機制解決船舶流水線的模糊調度問題。文獻[15]針對制造車間的信息物理融合系統CPS，提出了一個基于實時數據采集的自適應調度框架機制，但沒有涉及具體問題應用與求解算法。

采用傳統數學規劃算法或啟發式算法，能夠解決車間調度的路徑問題，但是在實際大規模定制生產現場中，其主要存在以下難點：一是面向大規模生產的HFS，系統規模大、資源約束多，會產生“維數災難”導致求解困難;二是面向定制生產的HFS，會因訂單、工藝、設備、人員和物料等各因素動態事件，導致APS（Advanced Planning and Scheduling）調度方案在生產執行中因執行偏差較大而不可行。因此，本論文針對大規模HFS系統的調度問題，采用MPN（Manufacturing Petri Net）對車間調度系統進行壓縮建模，并提出一種基于DDQN算法的車間作業動態調度方法，將傳統算法計算過程數據作為歷史經驗進行學習，得到蘊含調度知識的深度知識DQN。進一步，將深度知識中的Q值匹配車間生產中采集到的實時數據，形成工件流轉的調度策略，調度過程中充分利用了深度知識DQN，從而在實時狀態下能夠高效地指導工業生產。

1 ?模型構建

1.1 ?MPN模型構建

混流制造車間運作過程可以描述為：一共n個待加工的工件經過s道工序進行加工，而每一道工序存在Mi臺設備（Mi>1;i=1，2，…，s），每個工件需要經過每一道工序的加工，同一道工序的不同類型的設備對同一工件的加工時間不同。本文針對混流車間采用一種基于ROPN（Resource Oriented Petri Net）的制造系統MPN建模機制，將等價并行設備建模成為一個資源提供節點Place，將批次工件建模成Petri網中流轉的Token，工序中工件可以建模為通過Transaction觸發進行流轉。這樣的模型既縮小了混流制造車間調度模型規模，又具有良好的數學表達能力。

本論文用一個以某覆銅板廠案例進行說明，如圖1所示，描述了一個基于MPN模型的車間制造系統。在MPN模型中，車間作業過程可以抽象為待加工的所有工件Token在目標函數的指導下全部從p0開始轉運，在Transaction的觸發下進入到合適的Place上完成加工等一系列操作，最終轉運到p15并完成對所有工件加工的過程。各工位容量如圖2所示。

該案例用到的加工時間矩陣為：

1.2 ?MPN數據狀態建模

通過把MPN制造系統采集到的多源異構數據進行鏈接和集成的，對節點的多維數據進行準確表達，可以反映該節點上在制造過程中所蘊含的生產邏輯，從而實現MPN系統狀態的建模。

定義1：工位狀態由A=。維度i可以是節點中包含了“人機物法環”的各種信息，即人工熟練度、設備類型、物料類別、操作標準和生產環境等各維度的信息。

定義2：制造系統狀態S=，是由各個工位狀態構成的向量。

定義3：制造系統的MDP狀態過程M={|Si表示t時刻的狀態，Si+1表示t+1時刻Si的下一個狀態}，是各個制造系統狀態在時間軸上的狀態演變序列。

針對研究的覆銅板廠MPN案例，如果工位只定義一個維度狀態為Token數量，制造系統某個時刻系統的狀態為：<4，1，1，2，2，0，0，0，0，0，0，0，0，0，0，0>，若p4一個工件token被轉運到p5，其下一個時刻的狀態為：<4，1，1，2，1，1，0，0，0，0，0，0，0，0，0，0>，前后狀態有著時序上的演變邏輯。

2 ?算法設計與訓練

為了充分利用制造數據中的價值，本文考慮強化學習中基于價值策略的思路來實現算法，通過模型訓練，實現一個深度Q價值網絡DQN作為深度知識來指導調度策略。進一步，為解決使用相同的value來進行選擇動作和估計動作造成估計的價值過于樂觀的問題，設計了將選擇和評估分開成2個Q價值網絡的Double DQN（DDQN）算法。本文基于DDQN算法，構建一個深度強化學習算法模塊，把預備好的數據輸入到算法模型中訓練，充分利用數據中的生產邏輯蘊含的知識。模型訓練的過程具體包括以下兩個方面。

2.1 ?獲取數據

從歷史數據中隨機獲取最小批量數目的數據，每一條數據都按照的格式，一次選取固定數目的數據作為一個Batch（一批）的樣本，輸入到模型中進行訓練，本文設定一次隨機選取的數目為k條（k=40）。針對本文研究的覆銅板廠案例，S是制造系統的所有工件在每個庫所分布狀態的集合，A和S+1是基于當前的系統狀態所采取的動作以及下一個系統狀態，S是當前的系統制造節點狀態，S+1是下一個系統制造節點狀態，這些連續的S按時間序列串聯成為完整的制造系統的MDP狀態過程;定義A作為一個調度動作策略（其中，TOKENID是某個Token的編號，TRASID是某一個變遷的編號），表示當前某一個編號為TOKENID的工件在調度時觸發了某個變遷TRASID，進而流轉到下個節點執行操作;R是獎勵，是當前的狀態S執行了可選的某一個動作A之后，對這次動作的效果的一個評估值，它反映了系統對當前的狀態去執行該動作的可取程度，可有正值或負值，其數值越大表示該動作越可取;D是一個固定的系統數據狀態，預先設定為一個完整的作業過程的末狀態，也就是一個MDP過程結束的狀態，此時所有的待加工的訂單都已經完成。

2.2 ?訓練模型的過程

DDQN是由負責動作獲取的現實網絡Current_Net和負責動作價值計算的目標網絡Target_Net組成，兩者的網絡結構完全相同。我們把MDP狀態過程的各個系統狀態S作為神經網絡的輸入值;神經網絡的輸出為各動作Q表，Q表的不同維度索引映射不同動作，Q表中某一索引存儲的數值代表某一動作的Q值，Q值越大，動作的價值越大，表示該動作的合理性越高。整個模型的訓練過程的如圖3所示。

2.2.1 ?計算Batch樣本集的Q值

具體步驟為：

（1）將樣本i（i屬于1，k）中的S+1數據分別輸入Current_Net和Target_Net神經網絡中，得到Cur_Q值表和Tar_Q值表;

（2）獲取樣本i（i屬于1，k）Cur_Q值表中Q值最大的索引，即動作，再利用該索引檢索Tar_Q表，得到對應動作的Tar_Q值;

（3）創建可存儲k條樣本Q值數據的列表Q_batch，每條樣本數據根據：

Y=R+c*Qtarget（S_n，arg max′（Qcurrent（S_n，A′）））

分別計算對應的Q值并載入列表中，用于后續損失函數的計算。

2.2.2 ?損失函數的收斂過程

具體過程為：

（1）正向傳播。將k條樣本數據中的S輸入Current_Net神經網絡，得到的當前狀態的現實Q值，同時將k條樣本所得k個現實Q值存入Current_Net_Q列表，用于損失計算。

（2）反向傳播（收斂函數）。將損失函數Lost設定為：

Loss=Y-Qcurrent（S，A）

使用Tensorflow模塊自帶optimizer優化器，按照設定的固定步長e對Loss進行最小化收斂，通過訓練次數的反復迭代得到適配的模型。

2.2.3 ?目標Q網絡更新

本項研究中，設置更新目標網絡的頻率是f，即將Current_Net的參數每訓練f步，就更新一次Target_Net的參數。它決定著DDQN算法訓練的穩定性和快速性。相比DQN算法，引入目標網絡可以增加算法的穩定性，考慮到車間制造的實際，如果車間的動態干擾性較弱，即車間的生產較少有加增訂單或人員流動等情況，車間生產數據有相當的平穩性，那么可以考慮調小f，可以適當增加訓練的算法的快速性;如果車間制造的動態性較強，時常有加增訂單等突發事件，那么可以適當調大f，以使得訓練算法具有更好的穩定性。

在每次車間作業之前，都會基于歷史數據和當前狀態數據訓，按照以上的幾個步驟訓練R次，一般至少訓練上萬次，以確保模型的有效性。訓練完成深度Q價值網絡（DQN）作為自適應調度知識，用來指導調度。

3 ?實驗與分析

3.1 ?實驗條件與過程

為研究驗證本文提出的基于DDQN的車間調度系統在調度動態自適應性方面的有效性。本文采用馬爾可夫Petri網模型進行驗證，實驗平臺采用Pycharm基于Python語言實現，實驗環境為Intel（R） Core（TM） i5-5200U CPU @ 2.20 GHz、內存為12 GB、操作系統為Windows10。

實驗參數：基于Python語言以及Tensorflow等神經網絡算法庫，搭建維度為10的輸入層、9層隱含層、維度為220的輸出層、每層隱含層的神經元個數不同的全連接深度神經網絡，用作評估深度神經網絡與目標深度神經網絡，并初始化各個不同的權重和偏置參數，整個實驗中所涉及的參數如表1所示。

根據圖1的仿真模型驗證DDQN算法，使用TensorFlow 2.1搭載多層感知機模型（Multilayer Perceptron， MLP）。輸入層包含16個神經元，隱藏層層數為2，每層20個神經元，輸出層包含220個神經元。隨機生成220條消息樣本，將每條消息從源節點開始執行某個動作前后狀態轉移情況及所獲獎勵存入經驗池（經驗池存滿后最新獲得的經驗值覆蓋最早經驗值），待經驗值存滿后，隨機抽取40個經驗序列喂入神經網絡進行訓練，當前消息到達目的節點后視為當前軌跡到達終止狀態，所有消息到達終止狀態后完成訓練并保存訓練模型。

3.2 ?DDQN算法的有效性分析

為驗證本文中DDQN算法對車間調度數據利用效率的有效性，優化模型的效果，通過加大訓練次數，并針對不同的激勵公式，根據訓練的效果來分析車間調度的自適應性以及工作的效率。每訓練1 000次就做一次調度時間Time的測試，用來研究訓練次數和模型訓練的效果之間的變化關系。

通過對設計激勵公式的多次嘗試和調參工作，本研究中設計的激勵為：

經訓練后，將得到的調度時間和訓練次數的關系進行如圖4所示。

根據結果可知，第一，損失在訓練10萬次后收斂，滿足實驗要求，證明了實驗結果的有效性。第二，測試調度完工時間在訓練10萬次左右有明顯下降，此后測試結果出現幾次不錯的調度時間結果，多次出現130，振蕩幅度較為合理，模型訓練較為理想。

實驗得到收斂函數的圖像，如圖5所示，從圖像可知，本次研究中學習模型的收斂函數是趨于平緩的，這說明模型訓練的效果的科學性和合理性。

分析實驗結果，由圖4可知，首先，當訓練次數在10萬次以下的時候，經過訓練得到的模型把調度時間穩定在190個時間單位左右;當訓練次數當訓練次數超過10萬次，模型的調度時間明顯降低到155個時間單位左右，并穩定在一定區間。這說明模型訓練次數的增加可以在一定程度上優化模型。其次，經過30萬次的訓練，訓練時長為43 min 56 s，平均訓練一次的時長為0.008 786 67 s。這體現了模型具有良好的學習更新效率，滿足動態自適應調度時效性的需求。最后，從完工時間和響應時間來看，測試出現的最長完工時間為237個時間單位;測試出現的最短完工時間為130個時間單位;訓練30萬次的模型最終測試調度時間為162個時間單位;響應時長為0.082 8 s，一共40步，則平均每步響應時長為0.002 07 s。這充分說明模型在每一步中可以快速做出響應，在極短時間內給出調度指導策略，能夠有效解決車間自適應調度問題。

4 ?結 ?論

本文針對當前物聯網智能制造的車間調度中存在的無法有效利用車間生產的各種數據，以及調度效率低下等問題，提出來一種基于積累獎勵的雙重Q網絡算法，并以某覆銅板廠案例進行驗證。本研究的調度系統可以通過“一步一調度”的策略響應系統的動態性，能夠實時地根據環境的變化來不斷選擇策略。將實時狀態與深度目標Q網絡交互匹配，根據車間實時數據進行推演，每匹配一步則生成一次調度策略，用來指導下個一個作業，能夠快速地響應車間的動態變化，體現了對動態事件的自適應性，這對指導車間生產調度有著重要的意義。

參考文獻：

[1] MEILIN WANG，ZHONG R Y，DAI Q Y，et al. A MPN-based scheduling model for IoT-enabled hybrid flow shop manufacturing [J].Advanced Engineering Informatics，2016，30（4）：728-736.

[2] 賈萬達，彭艷，石寶東.基于MES系統的動態環境自適應調度模型 [J].現代商貿工業，2021，42（2）：159-160.

[3] ABREU L R，TAVARES-NETO R F，NAGANO M S. A new efficient biased random key genetic algorithm for open shop scheduling with routing by capacitated single vehicle and makespan minimization [J/OL].Engineering Applications of Artificial Intelligence，2021，104：[2021-11-02].https：//doi.org/10.1016/j.engappai.2021.104373.

[4] ?AHMAN M A. A discrete spotted hyena optimizer for solving distributed job shop scheduling problems [J/OL].Applied Soft Computing，2021，106：[2021-11.02].https：//doi.org/10.1016/j.asoc.2021.107349.

[5] 肖鵬飛，張超勇，孟磊磊，等.基于深度強化學習的非置換流水車間調度問題 [J].計算機集成制造系統，2021，27（1）：192-205.

[6] 李國梁，李峭，徐亞軍，等.基于DDQN的片上網絡混合關鍵性消息調度方法 [J/OL].北京航空航天大學學報，[2021-11-07].https：//www.cnki.net/KCMS/detail/detail.aspx？dbcode=CAPJ&dbname=CAPJLAST&filename=BJHK20210424001&v=MzEzMjJBUzZqaDRUQXpscTJBMGZMVDdSN3FkWmVac0Z5M2xWcjdCSlY0PUp5ZkRaYkc0SE5ETXE0MUJaT3NPWXdrN3ZC.

[7] 劉東寧，徐哲.基于多優先規則啟發式的分布式多項目隨機調度 [J].系統工程理論與實踐，2021，41（12）：3294-3303.

[8] 秦浩翔，韓玉艷，陳慶達，等.求解阻塞混合流水車間調度的雙層變異迭代貪婪算法 [J/OL].控制與決策，[2021-11-03].https：//www.cnki.net/KCMS/detail/detail.aspx？dbcode=CAPJ&dbname=CAPJLAST&filename=KZYC20210701014&v=MTc2NzNORE1xSTlFWk9vTFl3azd2QkFTNmpoNFRBemxxMkEwZkxUN1I3cWRaZVpzRnkzbFZyN0JKVjQ9TGpmU2JiRzRI.

[9] 秦媛媛.基于SVM與強化學習的啟發式算法[J].長江工程職業技術學院學報，2021，38（2）：10-14.

[10] 李浩，劉志芳，嚴勝利.基于元啟發式算法的凸輪從動機構優化設計研究 [J].機床與液壓，2021，49（14）：105-109.

[11] ANGEL-BELLO F，VALLIKAVUNGAL J，Alvarez A. Fast and efficient algorithms to handle the dynamism in a single machine scheduling problem with sequence-dependent setup times [J/OL].Computers & Industrial Engineering，2021，152：[2021-10-29].https：//doi.org/10.1016/j.cie.2020.106984.

[12] 尹靜，楊阿慧.考慮交貨期約束的塔式起重機服務調度啟發式算法 [J].中國工程機械學報，2021，19（1）：1-6.

[13] PENG K K，PAN Q K，GAO L，et al. An Improved Artificial Bee Colony algorithm for real-world hybrid flowshop rescheduling in Steelmaking-refining-Continuous Casting process [J].Computers & Industrial Engineering，2018，122：235-250.

[14] 蘭宏凱，楊志，柳存根，等.船舶平面分段單流水線反應式模糊調度研究 [J].艦船科學技術，2019，41（15）：7-11.

[15] ROSSIT D A，TOHM? F，Frutos M. A data-driven scheduling approach to smart manufacturing [J].Journal of Industrial Information Integration，2019，15：69–79.

[16] 錢斌，佘明哲，胡蓉，等.超啟發式交叉熵算法求解模糊分布式流水線綠色調度問題 [J].控制與決策，2021，36（6）：1387-1396.

[17] ?王建華，潘宇杰，孫瑞.考慮機床折舊的柔性作業車間綠色調度算法 [J].計算機應用，2020，40（1）：43-49.

[18] LIU C L，CHANG C C，TSENG C J. Actor-Critic Deep Reinforcement Learning for Solving Job Shop Scheduling Problems [J].IEEE Access，2020，8：71752-71762.

[19] HU L，LIU Z Y，HU W F，et al. Petri-net-based dynamic scheduling of flexible manufacturing system via deep reinforcement learning with graph convolutional network [J].Journal of Manufacturing Systems.2020，55：1-14.

[20] HU H，JIA X L，HE Q X，et al. Deep reinforcement learning based AGVs real-time scheduling with mixed rule for flexible shop floor in industry 4.0 [J/OL].Computers & Industrial Engineering，2020， 149：[2021-10-29].106749.https：//doi.org/10.1016/j.cie.2020.106749.

[21] 馬騁乾，謝偉，孫偉杰.強化學習研究綜述 [J].指揮控制與仿真，2018，40（6）：68-72.

[22] 王維祺，葉春明，譚曉軍.基于Q學習算法的作業車間動態調度 [J].計算機系統應用，2020，29（11）：218-226.

[23] YANG S L，XU Z G，WANG J Y. Intelligent Decision-Making of Scheduling for Dynamic Permutation Flowshop via Deep Reinforcement Learning [J/OL].Sensors，2021，21（3）：[2021-10-29].https：//doi.org/10.3390/s21031019.

[24] CLAUDIO A，FABRIZIO M，ANDREA P. Number of bins and maximum lateness minimization in two-dimensional bin packing [J].European Journal of Operational Research，2021，291（1）：101-113.

[25] SHIRVANI M H，TALOUKI REZA R. Bi-objective scheduling algorithm for scientific workflows on cloud computing platform with makespan and monetary cost minimization approach [J/OL].Complex & Intelligent Systems，[2021-10-29].https：//link.springer.com/article/10.1007/s40747-021-00528-1.

[26] PARK J，CHUN J，KIM S H，et al. Learning to schedule job-shop problems： representation and policy learning using graph neural network and reinforcement learning [J].International Journal of Production Research.2021，59（11）：3360-3377.

[27] LUO S. Dynamic scheduling for flexible job shop with new job insertions by deep reinforcement learning [J/OL].Applied Soft Computing，2020，91：[2021-10-29].https：//doi.org/10.1016/j.asoc.2020.106208.

[28] PARK I B，HUH J，KIM J，et al. A Reinforcement Learning Approach to Robust Scheduling of Semiconductor Manufacturing Facilities [J].IEEE Transactions on Automation Science and Engineering，2020，17（3）：1420-1431.

[29] GEORGIADIS G P，ELEKIDIS A P，GEORGIADIS M C. Optimal production planning and scheduling in breweries [J/OL].Food and Bioproducts Processing，2021，125：[2021-10-29].https：//doi.org/10.1016/j.fbp.2020.11.008.

作者簡介：陳曉航（1995—），男，漢族，廣東揭陽人，碩士研究生在讀，研究方向：物聯網車間調度和深度強化學習。王美林（1975-），男，漢族，湖南安化人，副教授，博士，研究方向：物聯網技術、制造執行系統及應用、面向新工科教育的智慧學習工場技術;吳耿楓（1998-），男，漢族，廣東揭陽人，碩士研究生在讀，研究方向：物聯網車間調度和深度強化學習;梁凱晴（1998-），女，漢族，廣東江門人，碩士研究生在讀，研究方向：物聯網車間調度和深度強化學習。