基于強化學習的智能車間調度策略研究綜述

收稿日期：2021-12-08；修回日期：2022-02-07" 基金項目：浙江理工大學基本科研業務費專項資金資助項目（2021Q026）

作者簡介：王無雙（1997-），女，浙江紹興人，碩士研究生，主要研究方向為強化學習、車間調度（wangwushuang_zstu@163.com）；駱淑云（1986-），女，浙江金華人，講師，碩導，博士，主要研究方向為工業互聯網.

摘 要：智能制造是我國制造業發展的必然趨勢，而智能車間調度是制造業升級和深化“兩化融合”的關鍵技術。主要研究強化學習算法在車間調度問題中的應用，為后續的研究奠定基礎。其中車間調度主要包括靜態調度和動態調度；強化學習算法主要包括基于值函數和AC（Actor-Critic）網絡。首先，從總體上闡述了強化學習方法在作業車間調度和流水車間調度這兩大問題上的研究現狀；其次，對車間調度問題的數學模型以及強化學習算法中最關鍵的馬爾可夫模型建立規則進行分類討論；最后，根據研究現狀和當前工業數字化轉型需求，對智能車間調度技術的未來研究方向進行了展望。

關鍵詞：強化學習；動態調度；靜態調度；作業車間調度；流水車間調度

中圖分類號：TP181"" 文獻標志碼：A

文章編號：1001-3695（2022）06-002-1608-07

doi：10.19734/j.issn.1001-3695.2021.12.0637

Research on intelligent shop scheduling strategies based on reinforcement learning

Wang Wushuang，Luo Shuyun

（School of Information Science amp; Technology，Zhejiang Sci-Tech University，Hangzhou 310000，China）

Abstract：Intelligent manufacturing is an inevitable trend in the development of our country’s manufacturing industry，and intelligent shop scheduling is a key technology for the integration of manufacturing upgrades and deepening.This paper mainly studied the application of reinforcement learning algorithms in shop scheduling problems，which layed the foundation for subsequent research.Shop scheduling mainly included static scheduling and dynamic scheduling，reinforcement learning algorithms mainly included value-based functions and Actor-Critic （AC） networks.First of all，this article described the research status of reinforcement learning methods on the two major issues of Job-Shop scheduling and Flow-Shop scheduling in general.Secondly，it classified the establishment rules of mathematical model of the shop scheduling problem and the most critical Markov model in reinforcement learning algorithms.Finally，according to the research status and the current needs of industrial digital transformation，it prospected the future research direction of intelligent workshop scheduling technology.

Key words：reinforcement learning；dynamic scheduling；static scheduling；Job-Shop scheduling；Flow-Shop scheduling

0 引言

車間調度問題是指如何在機器等資源有限的情況下，合理調度生產資源來安排車間生產任務，以滿足一至多個優化目標的過程［1］。社會在不斷發展，人民的消費水平也隨之不斷提高，各大企業在消費市場的競爭也愈演愈烈。有效的車間調度不僅可以提高生產量，還可以減少企業生產成本，提高客戶滿意度以及減少環境污染等。根據不同的生產特點，車間調度問題可以分為作業車間調度問題、流水車間調度問題以及開放車間調度問題。由于實際生產環境極為復雜，需要考慮各方面因素，所以出現了許多種基于以上調度問題的延伸問題，如柔性作業車間調度問題、混合流水車間調度問題等，它們往往更為復雜。車間調度問題還可以分為靜態調度和動態調度兩大類。靜態調度即在開始生產前，已經獲得了所有關于生產任務的信息且生產環境穩定。而動態調度是指在生產環境不確定的情況下進行調度，更符合實際生產情況［2］。在實際生產過程中，往往會有諸如機器故障、緊急插單等突發狀況。因此，動態車間調度比靜態車間調度更為復雜，面向動態車間調度的研究也相對不成熟。

目前已有大量算法被應用于車間調度問題的研究中，較為常見的有數學規劃方法、智能算法以及圖與網絡算法等［3］。其中，智能算法的應用最為成熟，如人工蜂群算法、蛙跳算法等［4，5］。近幾年，強化學習應用于研究車間調度問題的優勢引起了大量研究者的注意。強化學習以試錯的方式進行學習，通過與環境交互獲得獎勵來指導動作，目標是獲得最大的累積獎勵。此外，強化學習還能夠應對環境的不確定性，具有很強的適應性［6］。因此，無論是應用強化學習解決靜態車間調度問題還是動態車間調度問題，都已經取得了令人欣喜的成果。由于作業車間以及流水車間的應用背景極為廣泛，已經涵蓋了大部分企業生產車間的特點，且目前應用強化學習解決開放車間調度問題的研究尚處于起步階段。所以，本文系統地闡述了應用強化學習解決作業車間調度問題以及流水車間問題的研究現狀，暫時未將開放車間調度問題考慮在內。

作業車間調度問題被定義為：一個加工系統有M臺機器，要求加工N個工件，其中，每個工件完工都需要經過一定的工序加工。各工序的加工時間已確定，并且每個工件必須按照工序的先后順序加工，工件所有工序只有唯一的加工機器。調度任務是安排所有作業的加工順序，在滿足約束條件的同時，使性能指標得到優化［7］。而如果工序加工所需要的資源是具備柔性的，即一道工序有多臺機器可供選擇，那么作業車間調度問題就拓展為柔性作業車間調度問題［8］。很顯然，柔性作業車間調度問題更符合實際生產場景。

流水車間調度問題被定義為：N個工件要在M臺機器上加工，每個工件需要經過M道工序，N個工件在M臺機器上的加工順序相同。給定工件在機器上的加工時間，要求確定每個工件在每臺機器上的最優加工順序［9］。而如果工序加工所需要的資源具備柔性特征，那么流水車間調度問題就擴展為柔性流水車間調度問題，也稱為混合流水車間調度問題［10］。如果規定N個工件的加工順序對所有M臺機器均相同，則稱其為置換流水車間調度問題；如果允許在不同機器上改變工件的加工順序，則稱其為非置換流水車間調度問題。若每臺機器加工任意兩相鄰工件時沒有空閑時間，那么流水車間調度問題就擴展為無等待流水車間調度問題［11］。此外，若產品的生產主要包括加工階段和裝配階段兩個階段，在每個階段都要經過多臺機器加工，該問題即為兩階段流水車間調度問題［12］。

根據迭代方式的不同可將強化學習算法分為基于值函數的強化學習算法、基于策略的強化學習算法以及基于AC（Actor-Critic）的強化學習算法三種。由于基于策略的強化學習算法適用于求解具有連續動作空間的問題，而車間調度問題為組合優化問題，所以目前并沒有研究者采用基于策略的強化學習算法解決車間調度問題。

本文將涉及在內的兩種車間調度問題分為靜態調度和動態調度，并對現有的研究成果按強化學習算法分類進行系統闡述并總結狀態、動作以及獎勵的設置方法。最后結合車間調度問題的發展趨勢，分析并展望了該問題的未來研究方向。

1 作業車間調度

本章主要從靜態調度和動態調度兩個方面來闡述作業車間調度問題的研究現狀，并根據強化學習算法的不同類別進行詳細介紹。圖1為本文所涉及到的作業車間問題分類框架圖。

針對解決靜態作業車間調度問題的研究成果，目前基于值函數的強化學習算法占主體研究導向，因此在該類方法下，本章首先介紹單獨使用強化學習解決該問題的研究成果，包括單智能和多智能兩類。其次介紹強化學習和其他算法相結合的混合算法如何解決該問題，包括其他算法賦能強化學習算法和強化學習算法賦能其他算法兩種方式。表1為采用基于值函數的強化學習算法解決靜態作業車間調度問題的研究成果匯總。最后，本章對采用基于AC的強化學習算法來解決靜態作業車間調度問題的研究成果進行了分析說明。

針對動態作業車間調度問題的研究，動態環境的研究模型都有所差異，其中重點研究了工件隨機到達、新作業插入等動態因素。本文主要按不同動態因素來分類闡述基于值函數的強化學習算法解決動態作業車間調度問題的研究成果，同時也對采用基于AC的強化學習算法來解決動態作業車間調度問題的成果進行了分析。表2為采用基于值函數的強化學習算法解決動態作業車間調度問題的研究成果匯總。

1.1 靜態調度

1.1.1 基于值函數的強化學習算法

目前，有部分研究團隊單純采用基于值函數的強化學習算法來解決靜態作業車間調度問題。Bouazza等人［13］首先將部分柔性作業車間調度問題分解成機器分配子問題和機器上作業分配子問題，其次使用Q學習算法，其中智能體的動作為選擇機器分配規則和選擇機器上工件的調度規則。針對該問題，王維祺等人［15］在利用Q學習算法時將策略選擇的優先級作為學習對象，并分別設定五個基本動作對應五種不同的狀態，策略為動作和狀態的組合。為了更符合實際應用場景，Martins等人［14］考慮了雙資源約束的柔性作業車間調度問題，即同時考慮分配機器和工人資源，并最小化最大完工時間。為增強算法的魯棒性，減少機器和工件數量規模對算法性能的影響，Samsonov等人［16］提出了一種新的動作空間設計方法，其能夠使動作空間的規模不受作業和作業工序數量的影響，同時不受連續空間和離散空間的限制。該動作空間設置方法能夠將解決問題的方法從基于離散動作空間的DQN（deep Q-network）算法進一步拓展到策略梯度（policy gradient，PG）、深度確定性策略梯度（deep deterministic policy gradient，DDPG）等基于連續動作空間的強化學習算法。

強化學習除了單智能體學習，還有多智能體學習，雖然其有諸如性能不穩定、維度爆炸等缺陷，但更適用于實際工廠生產調度場景。文獻［17］提出了一種多智能體深度強化學習算法解決具有并行不相關機器的作業車間調度問題，以最小化拖期時間和最大完工時間為優化目標。實驗結果表明，其在大規模問題上的性能要比混合整數線性規劃算法更有優勢。Méndez-hernández等人［19］也采用類似方法解決同樣的問題。在該兩階段優化方法中，智能體在第一階段作為獨立單元優化各自代表的目標，在第二階段協作尋找折中的解決方案。Lang等人［18］將柔性作業車間調度問題分為兩個子問題，并訓練了兩個DQN智能體，其中一個負責工序順序的選擇，另一個負責將工件分配給機器。

由于作業車間調度問題具有高度復雜性，且強化學習自身存在收斂速度慢、易陷入局部最優等缺陷，很多研究者嘗試結合其他算法來解決以上問題。為使調度具有實時性，Moon等人［20］提出了一種基于協同邊緣計算框架的智能制造工廠生態系統架構，并使用DQN算法來解決其作業車間調度問題。該框架還引用了遷移學習，通過將歷史任務上所學知識遷移到新任務中來加快算法在新環境中的學習速度。實驗結果表明，該方法在不同參數規模下都比傳統方法具有更好的收斂效果。Han等人［21］提出了一種基于析取圖調度的深度強化學習框架，并進一步提出了帶優先經驗重放的雙深度Q學習（dueling double DQN，D3QN）算法，其主要基于競爭網絡結構，并通過將狀態表示為多通道圖像的方式來更好地提取狀態特征。實驗證明，針對小規模問題，該算法能夠獲得最優解；對于大規模問題，其性能優于任何單一的啟發式規則，且與遺傳算法相當。該研究團隊又提出了一種結合編碼器網絡的調度方法［22］，并采用策略梯度算法來優化其參數。實驗表明，訓練模型的效果比啟發式算法更好。Lara-Crdenas等人［23］結合K均值聚類和Q學習算法來解決作業車間調度問題。實驗結果表明，該算法的性能優于一些基于最短加工時間規則和最大作業剩余時間規則的啟發式算法。

由于強化學習能夠通過與環境交互，在試錯中學習正確行為，研究學者將其應用于解決智能優化算法中的參數調節和種群多樣性控制等難題。Chen等人［24］結合Q學習算法和Sarsa算法去改進遺傳算法來解決柔性作業車間調度問題，其根據種群的當前狀態（種群的平均適應度值、種群多樣性和最好個體的適應度值），利用Q學習和Sarsa算法自適應調整交叉和變異的概率。針對柔性作業車間調度問題，非支配排序遺傳算法存在易陷入局部的硬傷，尹愛軍等人［25］融合多個多樣性指標，利用強化學習動態優化種群迭代過程中的拆分比例參數以保持種群多樣性。

1.1.2 基于Actor-Critic的強化學習算法

目前，應用基于AC的強化學習算法來解決靜態作業車間調度問題的研究尚處于起步階段，僅有三個研究團隊分別采用AC、近端策略優化（proximal policy optimization，PPO）以及多智能體PPO算法來解決該問題。Liu等人［35］提出了包括卷積層和全連接層的AC網絡去解決該問題。為加快收斂速度，還提出了一種結合異步更新和DDPG算法的并行訓練算法。實驗結果表明，針對靜態調度環境，該方法比傳統啟發式算法性能更好，同時也能推廣到動態調度環境中應用。Park等人［36］結合圖神經網絡和PPO算法來解決該問題，采用圖神經網絡來學習嵌入表示為圖的作業車間調度問題空間結構的節點特征，并生成將嵌入節點特征映射到最佳調度動作的調度策略。實驗表明，該框架在訓練得到模型后，無須進一步訓練即可應用于新的作業車間調度問題中，大大節省了重新訓練所需的時間。由于作業延誤和過早完工都會帶來不可忽略的生產成本，Roesch等人［37］在綜合考慮生產成本與能源成本的前提下，利用多智能體PPO算法來解決該問題，其中每個智能體都代表一臺機器且必須處理一定數量的作業。

1.2 動態調度

1.2.1 基于值函數的強化學習算法

針對機器故障的動態作業車間調度問題，Zhao等人［26］提出了一種改進的Q學習算法。當機器發生故障時，Q學習智能體能夠同時選擇該處理的工序以及可替代的機器。機器發生故障前的初始調度方案由遺傳算法獲得。實驗結果表明，與單一調度規則相比，所提方案能夠減少頻繁動態環境中的作業延遲時間。Br等人［27］使用了多智能體DQN算法來解決動態柔性作業車間調度問題，將每個產品設置為智能體并共用一個經驗回放池。這些智能體能夠在訓練中學會合作，考慮其他智能體的需求以實現優化目標。

針對作業隨機到達的動態作業車間調度問題，Luo等人［28］提出了一個具有探索循環和利用循環的雙循環DQN算法。該算法集成了探索循環的全局探索能力以及利用循環的局部收斂能力，可促進DQN算法找到問題的全局最優解。Turgut等人［29］也采用DQN算法來解決該問題，以最小化作業延誤時間。實驗結果表明，該方案有兩個啟發式調度規則，即最短處理時間和最早到期日更有效。在實際生產中，過早完工會給企業帶來庫存壓力，延誤工期會影響客戶滿意度。考慮到以上兩點，Wang［30］建立了一個基于多智能體的動態調度系統模型，將機器、緩沖區、狀態和作業設為智能體，并使用加權Q學習算法來確定作業在機器上的加工順序。生產車間的動態環境會引起系統狀態變化，從而導致狀態空間巨大。針對該問題，作者定義了四個狀態特征，并通過聚類的方法降低了狀態空間維度。此外，為避免傳統策略中的盲目搜索，還提出了一種動態貪婪搜索策略。

針對新作業插入的動態作業車間調度問題，為減少作業延誤帶來的成本，Luo［31］應用了DQN算法，提取了七個取值于［0，1］的通用特征來表示每個重調度點的狀態，并將動作設計為六個可選復合規則以確定下一個要處理的工序和分配給它的機器。針對該問題，Luo等人［32］還提出了雙層DQN在線重調度框架，該框架包含了兩個基于DQN的智能體。上層DQN用來控制下層DQN的臨時優化目標，在每個重調度點，它將當前狀態特征作為輸入，并根據優化目標來指導下層DQN的行為。下層DQN將狀態特征和從上層DQN傳遞的優化目標作為輸入，將每個調度規則的Q值作為輸出。基于該Q值，可選擇每個重調度點上最可行的調度規則。

針對機器故障和作業隨機到達的動態作業車間調度問題，Shahrabi等人［33］使用可變鄰域搜索算法來解決該問題，以最小化完工時間。針對可變鄰域搜索算法易陷入局部最優等缺陷，使用Q學習算法在每個重調度點上更新它的參數。實驗結果表明，該方案比傳統啟發式調度規則更有效。

針對作業隨機到達和產品隨機選擇的動態作業車間調度問題，為減少提前完工帶來的庫存壓力，Kardos等人［34］應用了多智能體Q學習算法來解決該問題，將每個產品設為智能體并能夠根據實時信息在每個生產步驟選擇機器。與標準調度規則的比較表明，該方案具有更好的性能。

1.2.2 基于Actor-Critic的強化學習算法

目前采用基于AC的強化學習算法來解決動態作業車間調度問題還處于初步探索階段。Wang等人［38］考慮了諸如機器故障、工件返工等各種動態因素，嘗試利用PPO算法解決該問題，以最小化最大完工時間。不同于一般的研究方法，作者將狀態定義為三個矩陣，分別為作業處理狀態矩陣、機器指定矩陣和工序的處理時間矩陣。經實驗證明，所提方案的性能優于傳統啟發式規則以及遺傳算法，且在一定程度上可以實現自適應調度。

2 流水車間調度

本章主要從靜態調度和動態調度兩個方面來闡述流水車間調度問題的研究現狀，并根據強化學習算法的不同類別進行詳細介紹。圖2為本文所涉及到的流水車間調度問題分類框架圖。

針對解決靜態流水車間調度問題的研究成果，目前基于值函數的強化學習算法占主體研究導向。在該類方法下，本章首先介紹單獨使用強化學習解決該問題的研究成果，將問題根據是否考慮自動導引運輸車（automated guided vehicle，AGV）分為兩類。其次介紹如何利用強化學習和其他算法相結合的混合算法來解決該問題。表3為采用基于值函數的強化學習算法解決靜態流水車間調度問題的研究成果匯總表。最后，本章對采用基于AC的強化學習算法來解決靜態流水車間調度問題的研究成果進行了分析說明。

針對動態流水車間調度問題，本章對采用基于值函數和基于AC的強化學習算法來解決該問題的研究成果進行了分析。

2.1 靜態調度

2.1.1 基于值函數的強化學習算法

目前，有部分研究團隊單純采用基于值函數的強化學習算法來解決靜態流水車間調度問題。Han等人［39］首次提出使用Q學習算法來解決混合流水車間問題，在算法中采用玻爾茲曼探索策略來平衡探索和利用，并以汽車發動機金屬加工廠的實例來對該算法進行驗證。在確保復雜度相同的情況下，該算法的性能優于遺傳算法，且該算法的收斂速度比人工免疫算法更快。Reyna等人［40］采用了自適應Q學習算法來解決具有序列相關生產時間、機器初始化準備時間的置換流水車間調度問題，將狀態定義為作業優先級關系，將動作定義為更改作業優先級。張東陽等人［41］同樣采用Q學習算法來解決該問題，不同的是，該算法將狀態定義為作業序列，將動作定義為選擇可選的工件，最后用OR-Library提供的標準算例進行仿真實驗，結果表明，相較于其他智能算法以及啟發式規則，Q學習算法的尋優能力更好。肖鵬飛等人［42］提出了深度時間差分網絡算法來解決非置換流水車間調度問題，該算法采用深度神經網絡來擬合值函數，用TD算法來訓練網絡模型，將啟發式調度規則設為動作并結合AC網絡結構為每次調度決策選取最優的組合行為策略。實驗證明，相較于群智能算法，該算法的性能更優。

在實際生產中，時常會用到智能運輸小車等工具進行物料運輸。針對該現象，部分研究者將柔性搬運系統結合到流水車間調度問題中。Xue等人［43］應用Q學習算法來解決流水車間中AGV的調度問題，將總完工時間最小化作為優化目標。考慮到完工時間主要受AGV等待時間與作業等待時間的影響，將AGV作為智能體，根據系統當前情況來決定所需要完成的任務，并設計改進的ε-greedy方法來平衡探索和利用。實驗結果表明，在問題規模較大的情況下，該算法的性能優于多智能體算法。Arviv等人［44］研究了具有兩個機器人的流水車間調度問題，定義了四種機器人協作方式，并使用雙重Q學習算法將兩個機器人設為智能體，并給它們分配了不同獎勵。其中一個機器人負責最小化機器空閑時間，另一個則負責最小化作業等待時間，機器人之間可通過交換獎勵值來共享信息。為驗證算法性能，用快速、中速以及慢速機器人進行仿真實驗，結果表明，兩個快速機器人之間的完全協作能夠取得最佳效果。

流水車間調度問題是一個NP難問題，解空間十分龐大，且強化學習存在易陷入局部最優等缺陷，許多研究者嘗試結合其他算法來解決該問題。考慮準備時間的直觀延誤成本（apparent tardiness cost with setups，ATCS）規則的參數能夠極大地影響該規則的性能，針對該問題，Heger等人［45］提出采用Q學習算法來自主調整ATCS規則中的k1和k2值，與其他研究成果所能得到的最佳k值相比較，其得到的k值能將平均延遲降低5%。針對置換流水車間調度問題，César等人［46］采用啟發式算法來生成作業的初始排序，并結合自適應Q學習算法以及局部搜索算法來解決該問題。在實驗中，將該算法與包括粒子群算法在內的八種其他算法進行比較，結果表明，該方案能在較短時間內得到更高質量的解。針對傳統模型受問題規模影響而難以擴展的缺陷，王凌等人［47］設計了一種新的編碼網絡來對問題進行建模，通過深度強化學習算法訓練模型來獲得該問題的初始調度解，并采用帶反饋機制的迭代貪婪算法來繼續優化該初始調度解以獲得最終調度解。ztop等人［48］采用可變鄰域搜索算法來解決無空閑流水車間調度問題，并采用Q學習算法來自適應地調節可變鄰域搜索算法的參數。實驗結果表明，該算法的性能優于傳統迭代貪婪算法。

2.1.2 基于Actor-Critic的強化學習算法

目前，在基于AC的強化學習算法中，僅有兩個研究團隊分別使用PPO以及AC算法來解決靜態流水車間問題。Zhu等人［49］首次采用PPO算法來解決具有相同并行機的混合流水車間調度問題，將最小化最大完工時間作為優化目標，并在真實實例和不同規模的隨機實例上測試了該算法的性能。實驗結果表明，在晶片酸洗實例上，該算法的性能優于遺傳算法。在隨機生成的實例上，該算法的性能優于其他啟發式調度規則。針對置換流水車間調度問題，Pan等人［50］提出了一種異構網絡深度強化學習模型，其中包括長短期內存網絡（long short term memory，LSTM）和注意力網絡。實驗結果表明，該模型在較小規模問題上的性能優于傳統啟發式算法和其他相同結構的深度強化學習模型。

2.2 動態調度

2.2.1 基于值函數的強化學習算法

目前采用基于值函數的強化學習算法解決動態流水車間調度問題的研究還處于起步階段。Yang等人［51］為了實現動態調度的實時性以及智能決策，首次提出了利用深度強化學習來求解考慮新作業到達的動態置換流水車間調度問題，采用A2C（advantage actor-critic）算法來訓練網絡模型。實驗結果表明，該方案在解決方案質量、CPU計算時間以及泛化能力等方面都明顯優于傳統元啟發式算法。此外，Yang等人［52］還采用DDQN來解決該問題，并通過大量的實例來進行訓練，其效果優于一些經典的調度規則。Wang等人［9］應用多智能體Q學習算法來解決該問題，將每個機器設為智能體，并在實驗中驗證了該算法的性能，卻發現所提方案在實際應用中的缺陷。此后作者分析了強化學習的優缺點，針對原有算法的缺陷設計了兩種改進策略。

2.2.2 基于Actor-Critic的強化學習算法

目前僅有一個研究團隊采用基于AC的強化學習算法來解決動態兩階段裝配流水車間調度問題。兩階段裝配流水車間調度問題廣泛存在于消防車制造、空調裝配和船舶生產等制造業。兩階段流水車間的生產主要包括加工和裝配兩個階段。產品先在加工階段的多臺專用機器上加工，而后被裝配階段的多臺裝配機器組裝成成品。Lin等人［12］采用PPO算法來解決動態兩階段裝配流水車間調度問題，將最小化總延遲作為優化目標。在實驗中，將單一的調度規則與所提方案進行比較。實驗結果表明，無論生產訂單的規模大小，PPO算法所得調度方案的平均總延遲時間總是低于其他調度規則。

3 車間調度問題數學模型分析

車間調度問題具有十分廣泛的工業應用背景，因此，需要了解其實際背景，明確其實際意義，以數學思想來包容問題的精髓。本章首先給出流水車間以及作業車間調度問題的一般假設和約束，再根據靜態和動態生產環境分類來分析數學模型。

流水車間以及作業車間的特征相似，因此，這兩個車間調度問題的假設以及約束條件基本一致。假設主要有以下幾點：a）不允許作業搶占，一旦作業開始在一個機器上處理，該處理過程必須不間斷直至完成；b）作業在每臺機器上的處理時間已知；c）所有資源在零時刻可用；d）針對非柔性車間，一個作業的某道工序只能由一臺機器加工。針對柔性車間，一個作業的某道工序可由多種類型的機器加工。約束條件主要有以下幾點：a）同一作業的工序有先后順序，如第一道工序必須在第二道工序開始之前完成；b）一臺機器在同一時刻只能加工一個作業；c）一個作業在同一時刻只能在一臺機器上處理。

針對靜態生產環境下車間調度問題的數學模型，有兩種比較傳統的建模方式。一種是根據約束和假設建立混合整數線性規劃模型，該模型的目標函數是線性的，約束條件也是線性的，而有部分或所有決策變量必須是整數。另一種是依據圖論建模。該種建模方式一般都是采用有向圖來建模，具體方式為G=（V，C∪D）。其中V表示對應作業所有工序的一組頂點；C是連接節點之間邊的集合，表示同一作業的兩個連續工序之間的優先級約束；D為另一組連接節點的邊，表示同一臺機器上的任務順序。動態生產環境下的數學模型較靜態環境有一些改動，需給定實時事件發生的時間以及在此期間改動的模型參數。這些參數包括作業數量、可運作的機器、工序的處理時間以及供需之間的優先級關系等。

基于模型中的多目標函數，有以下兩種較為常用的處理方式：a）直接以加權和的形式將多目標轉換為單目標；b）根據帕累托法則進行求解。具體為每個目標分配一個智能體，采用多智能體算法來分階段解決問題。在第一階段，智能體作為獨立單元，每個單元優化各自的目標；在第二階段，智能體之間相互合作為所有目標組合找到最佳解決方案。

4 馬爾可夫決策過程模型分析

雖然早在二十多年前就已經有研究者應用強化學習算法對車間調度問題進行了研究，但就目前的研究狀況而言，該研究還處于不成熟階段。強化學習算法雖然優勢突出，但也伴隨著收斂困難、難以平衡探索與利用等問題［53］。馬爾可夫決策過程（Markov decision process，MDP）的模型建立好壞直接決定了強化學習算法的性能。因此，本章主要分析利用強化學習算法解決車間調度問題時如何建立MDP模型，側重于闡述狀態、動作和獎勵三個要素的設置規律。圖3為采用強化學習算法解決車間調度問題時，MDP模型三要素的設置規律匯總圖。

針對作業車間調度問題，單獨的強化學習算法和優化群智能算法的強化學習算法在狀態、動作和獎勵設置上有所區別。一方面，對于單獨的強化學習算法，狀態一般定義為S1：工件和機器的特征，如工件在機器上所需的處理時間、工件的完成進度（已完成的工序數）和機器利用率等。動作一般為：a）A1：選擇下一步要處理的工序以及對應的機器；b）A2：選擇調度規則，通常指先進先出（first in first out，FIFO）等傳統啟發式調度規則。獎勵一般為R1：與具體的優化目標有關。另一方面，對于優化群智能算法的強化學習算法，狀態一般設置為S2：種群特征，如多樣性、最大適應度值、平均適應度值等。動作一般為A3：要優化的參數值，獎勵同樣也依賴于優化目標。但也有研究學者沒有遵循以上規則設計MDP。Samsonov等人［16］設計了一種新的動作空間，其能夠保證動作空間的規模不受作業和作業工序數量的影響，并將動作設置為選擇一段相對持續時間，隨后利用最大最小處理時間將被選擇的相對持續時間映射回絕對持續時間，最后選擇與該絕對持續時間具有最接近處理時間的工序。

針對流水車間調度問題，單獨的強化學習算法和優化群智能算法的強化學習算法在狀態、動作和獎勵設置上兩者有所區別。一方面，對于單獨的強化學習算法，MDP的建模主要取決于是否引入AGV。針對考慮AGV的流水車間調度問題，狀態一般設置為S3：目前所有AGV所處的情況。動作一般為A4：選擇機器的位置，因為AGV需要將上一臺機器處理完畢的工件運送到下一臺機器，所以需要指示AGV移動軌跡。獎勵同樣也依賴于優化目標。針對不考慮AGV的流水車間調度問題，狀態與獎勵的設置規則與上述單獨使用強化學習解決作業車間調度問題一致，但其動作的設置規則有所不同：a）A2：選擇調度規則；b）A5：選擇一個工件。另一方面，對于優化群智能算法的強化學習算法，MDP的設置規則與上述使用強化學習優化其他智能算法來解決作業車間調度問題一致。但也有研究學者沒有遵循以上規則設計MDP。針對置換流水車間調度問題，王凌等人［47］將動作設置為直接給出各工件的加工順序。針對混合流水車間問題，Zhu等人［49］將狀態設置為工件的加工順序，通過初始化狀態先設置一個工件的加工順序，并將動作設置為選擇兩個工件并交換其位置。

5 結束語

智能車間調度是依據群智能優化算法、強化學習算法等來對車間產品的生產流程進行合理的調度和規劃。隨著企業數字化轉型的需求與日俱增，智能生產和大型個性化定制等智能服務需求要求企業具有智能化的生產調度流水線，能夠應對各種突發狀況并能夠高效完成訂單任務。為了在消費市場中保持競爭力，車間調度是工廠在運營層面面臨的最重要問題之一。下面從五個方面來闡述可行的車間調度的未來研究方向：

a）解決方案落地化。目前利用強化學習方法來解決車間調度問題的研究還處于不成熟階段，大多數還停留在理論研究層面。由于生產調度是企業生產運營的關鍵環節，要提高生產效率還需要將算法運用到實際生產系統中。信息技術和運營技術融合是從理論轉換成系統，從知識轉換成生產力的必然趨勢。因此，生產調度問題還需要從實際系統部署層面進行更深一步的研究。

b）多目標車間調度。目前的研究成果在解決車間調度問題時，所要優化的目標基本都是最大完工時間最小化，過于單一。企業的實際需求還需要考慮到節能減排、訂單延誤、庫存壓力等問題。因此，未來在對車間調度問題的研究中，可以考慮更傾向于多目標優化。

c）采用混合算法。單一智能算法解決車間調度問題已經不能滿足其多樣性需求，因此混合算法成為解決該問題的新寵，其可以彌補單一算法存在的局限性。目前已有一些學者結合強化學習算法和遺傳算法來解決車間調度問題，并取得了一定的成效［24］。未來可以考慮結合其他領域算法，如機器學習算法、博弈論等。

d）考慮工人因素。目前的研究僅局限于優化機器資源，事實上機器需要由工人來操作，工人資源的分配也會對生產效率產生極大影響。因此，未來需要考慮機器與工人雙資源約束的車間調度問題。

e）基于強化學習算法的改進。強化學習算法以試錯的方式進行學習，如果無法平衡其探索和利用，就極易陷入局部最優解。在未來，應設計出更好的探索和利用方案。此外，大多數研究者傾向于應用Q學習、DQN等傳統強化學習算法來解決車間調度問題。當前，已設計出了很多其他性能更優的算法。因此，研究者可以嘗試將新算法應用于車間調度問題。

參考文獻：

［1］羅哲，夏余平，米雙山.典型車間調度問題的分析與研 究［J］.科技創新與應用，2020（9）：60-61.（Luo Zhe，Xia Yuping，Mi Shuang-shan.Analysis and research on typical workshop scheduling problems［J］.Technology Innovation Application，2020（9）：60-61.）

［2］Shvalika C，Silva T，Karunanandaa A.Reinforcement learning in dynamic task scheduling：a review［J］.SN Computer Science，2020，1（6）：1-17.

［3］Cebi C，Atac E，Sahingoz O K.Job-Shop scheduling problem and solution algorithms：a review［C］//Proc of the 11th International Confe-rence on Computing，Communication and Networking Technologies.Piscataway，NJ：IEEE Press，2020：1-7.

［4］吳銳，郭順生，李益兵，等.改進人工蜂群算法求解分布式柔性作業車間調度問題［J］.控制與決策，2019，34（12）：2527-2536.（Wu Rui，Guo Shunsheng，Li Yibing，et al.Improved artificial bee colony algorithm for distributed and flexible Job-Shop scheduling problem［J］.Control and Decision，2019，34（12）：2527-2536.）

［5］雷德明，楊冬婧.基于新型蛙跳算法的低碳混合流水車間調度［J］.控制與決策，2020，35（6）：1329-1337.（Lei Deming，Yang Dongjing.A novel shuffled frog-leaping algorithm for low carbon hybrid Flow-Shop scheduling［J］.Control and Decision，2020，35（6）：1329-1337.）

［6］馬騁乾，謝偉，孫偉杰.強化學習研究綜述［J］.指揮控制與仿真，2018，40（6）：68-72.（Ma Chengqian，Xie Wei，Sun Weijie.Summary of reinforcement learning research［J］.Command Control and Simulation，2018，40（6）：68-72.）

［7］Zhang Jian，Ding Guofu，Zou Yisheng，et al.Review of Job-Shop sche-duling research and its new perspectives under Industry 4.0［J］.Journal of Intelligent Manufacturing，2019，30（4）：1809-1830.

［8］Xie Jin，Gao Liang，Peng Kunkun，et al.Review on flexible Job-Shop scheduling［J］.IET Collaborative Intelligent Manufacturing，2019，1（3）：67-77.

［9］Wang Jinzhi，Qu Shuhui，Wang Jie，et al.Real-time decision support with reinforcement learning for dynamic Flow-Shop scheduling［C］//Proc of European Conference on Smart Objects，Systems and Technologies.［S.l.］：VDE Press，2017：1-9.

［10］李穎俐，李新宇，高亮.混合流水車間調度問題研究綜 述［J］.中國機械工程，2020，31（23）：2798-2813，2828.（Li Yingli，Li Xinyu，Gao Liang.Summary of research on scheduling problems of mixed Flow-Shop［J］.China Mechanical Engineering，2020，31（23）：2798-2813，2828.）

［11］Singh H，Oberoi J S，Singh D.Multi-objective permutation and non-permutation Flow-Shop scheduling problems with no-wait：a systematic literature review［J］.RAIRO-Operations Research，2021，55（1）：27-50.

［12］Lin Xin，Chen Jian.Deep reinforcement learning for dynamic scheduling of two-stage assembly Flow-Shop［C］//Proc of International Con-ference on Swarm Intelligence.Berlin：Springer，2021：263-271.

［13］Bouazza W，Sallez Y，Beldjilali B.A distributed approach solving partially flexible Job-Shop scheduling problem with a Q-learning effect［J］.IFAC-PapersOnLine，2017，50（1）：15890-15895.

［14］Martins M S E，Viegas J L，Coito T，et al.Reinforcement learning for dual-resource constrained scheduling［J］.IFAC-PapersOnLine，2020，53（2）：10810-10815.

［15］王維祺，葉春明，譚曉軍.基于Q學習算法的作業車間 動態調度［J］.計算機系統應用，2020，29（11）：218-226.（Wang Weiqi，Ye Chunming，Tan Xiaojun.Dynamic Job-Shop scheduling based on Q-learning algorithm［J］.Computer Systems amp; Applications，2020，29（11）：218-226.）

［16］Samsonov V，Kemmerling M，Paegert M，et al.Manufacturing control in Job-Shop environments with reinforcement learning［C］//Proc of the 13th International Conference on Agents and Artificial Intelligence.Portugal：Scitepress-Science and Technology Publications Press，2021：589-597.

［17］Wemelsfelder M.Approximating optimal solutions for Job-Shop sche-duling problems with unrelated machines in parallel using generalizable deep multi-agent reinforcement learning［D］.Amsterdam：University of Amsterdam，2020.

［18］Lang S，Behrendt F，Lanzerath N，et al.Integration of deep reinforcement learning and discrete-event simulation for real-time scheduling of a flexible Job-Shop production［C］//Proc of Winter Simulation Confe-rence.Piscataway，NJ：IEEE Press，2020：3057-3068.

［19］Méndez-hernández B M，Rodríguez-bazan E D，Martinez-Jimenei Y，et al.A multi-objective reinforcement learning algorithm for JSSP［C］//Proc of International Conference on Artificial Neural Networks.Berlin：Springer，2019：567-584.

［20］Moon J，Yang M，Jeong J.A novel approach to the Job-Shop scheduling problem based on the deep Q-network in a cooperative multi-access edge computing ecosystem［J］.Sensors，2021，21（13）：article ID 4553.

［21］Han Baoan，Yang Jianjun.Research on adaptive Job-Shop scheduling problems based on dueling double DQN［J］.IEEE Access，2020，8：186474-186495.

［22］Han Baoan，Yang Jianjun.A deep reinforcement learning based solution for flexible Job-Shop scheduling problem［J］.International Journal of Simulation Modelling，2021，20（2）：375-386.

［23］Lara-cárdenas E，Silva-gálveza，Optiz-Bayliss J C，et al.Exploring reward-based hyper-heuristics for the Job-Shop scheduling problem［C］//Proc of IEEE Symposium Series on Computational Intelligence.Piscataway，NJ：IEEE Press，2020：3133-3140.

［24］Chen Ronghua，Yang Bo，Li Shi，et al.A self-learning genetic algorithm based on reinforcement learning for flexible Job-Shop scheduling problem［J］.Computers amp; Industrial Engineering，2020，149：article ID 106778.

［25］尹愛軍，閆文濤，張厚望.面向多目標柔性作業車間調度 的強化學習NSGA-Ⅱ算法［J/OL］.重慶大學學報，2021.（2021-05-12）［2022-01-10］.http：//kns.cnki.net/kcms/detail/50.1044.N.20210511.1913.0 10.html.（Yin Aijun，Yan Wentao，Zhang Houwang.Reinforcement learning NSGA-Ⅱ algorithm for multi-objective flexible Job-Shop scheduling［J/OL］.Journal of Chongqing University，2021.（2021-05-12）［2022-01-10］.http：//kns.cnki.net/kcms/detail/5 0.1044.N.20210511.1913.010.html.）

［26］Zhao Meng，Li Xinyu，Gao Liang，et al.An improved Q-learning based rescheduling method for flexible Job-Shop with machine failures［C］//Proc of the 15th IEEE International Conference on Automation Science and Engineering.Piscataway，NJ：IEEE Press，2019：331-337.

［27］Br S，Turner D，Mohanty P K，et al.Multi agent deep Q-network approach for online Job-Shop scheduling in flexible manufacturing［C］//Proc of International Conference on Manufacturing System and Multiple Machines.2020：1-8.

［28］Luo Bin，Wang Sibao，Yang Bo，et al.An improved deep reinforcement learning approach for the dynamic Job-Shop scheduling problem with random job arrivals［C］//Proc of the 4th International Conference on Advanced Algorithms and Control Engineering.Bristol：IOP Publishing Press，2021：1-8.

［29］Turgut Y，Bozdaag C E.Deep Q-network model for dynamic Job-Shop scheduling problem based on discrete event simulation［C］//Proc of Winter Simulation Conference.Piscataway，NJ：IEEE Press，2020：1551-1559.

［30］Wang Yufang.Adaptive Job-Shop scheduling strategy based on weighted Q-learning algorithm［J］.Journal of Intelligent Manufacturing，2020，31（2）：417-432.

［31］Luo Shu.Dynamic scheduling for flexible Job-Shop with new job insertions by deep reinforcement learning［J］.Applied Soft Computing，2020，91：article ID 106208.

［32］Luo Shu，Zhang Linxuan，Fan Yushun.Dynamic multi-objective scheduling for flexible Job-Shop by deep reinforcement learning［J］.Computers amp; Industrial Engineering，2021，159：article ID 107489.

［33］Shahrabi J，Adibi M A，Mahootchi M.A reinforcement learning approach to parameter estimation in dynamic Job-Shop scheduling［J］.Computers amp; Industrial Engineering，2017，110：75-82.

［34］Kardos C，Laflamme C，Gallina V，et al.Dynamic scheduling in a Job-Shop production system with reinforcement learning［J］.Procedia CIRP，2021，97：104-109.

［35］Liu C，Chang C，Tseng C.Actor-Critic deep reinforcement learning for solving Job-Shop scheduling problems［J］.IEEE Access，2020，8：71752-71762.

［36］Park J，Chun J，Kim S H，et al.Learning to schedule Job-Shop pro-blems：representation and policy learning using graph neural network and reinforcement learning［J］.International Journal of Production Research，2021，59（11）：3360-3377.

［37］Roesch M，Linder C，Bruckdorfer C，et al.Industrial load management using multi-agent reinforcement learning for rescheduling［C］//Proc of the 2nd International Conference on Artificial Intelligence for Industries.Piscataway，NJ：IEEE Press，2019：99-102.

［38］Wang Libing，Hu Xin，Wang Yin，et al.Dynamic Job-Shop scheduling in smart manufacturing using deep reinforcement learning［J］.Computer Networks，2021，190：article ID 107969.

［39］Han Wei，Guo Fang，Su Xichao.A reinforcement learning method for a hybrid Flow-Shop scheduling problem［J］.Algorithms，2019，12（11）：article ID 222.

［40］Reyna Y C F，Martínez-Jiménez Y.Adapting a reinforcement learning approach for the Flow-Shop environment with sequence-dependent setup time［J］.Revista Cubana de Ciencias Informáticas，2017，11（1）：41-57.

［41］張東陽，葉春明.應用強化學習算法求解置換流水車間調度問題［J］.計算機系統應用，2019，28（12）：195-199.（Zhang Dongyang，Ye Chunming.Application of reinforcement learning algorithm to solve the permutation Flow-Shop scheduling problem［J］.Computer Systems amp; Applications，2019，28（12）：195-199.）

［42］肖鵬飛，張超勇，孟磊磊，等.基于深度強化學習的非置 換流水車間調度問題［J］.計算機集成制造系統，2021，27（1）：192-205.（Xiao Pengfei，Zhang Chaoyong，Meng Leilei，et al.Non-permutation Flow-Shop scheduling problem based on deep reinforcement learning［J］.Computer Integrated Manufacturing Systems，2021，27（1）：192-205.）

［43］Xue Tianfang，Zeng Peng，Yu Haibin.A reinforcement learning method for multi-AGV scheduling in manufacturing［C］//Proc of IEEE International Conference on Industrial Technology.Piscataway，NJ：IEEE Press，2018：1557-1561.

［44］Arviv K，Stern H，Edan Y.Collaborative reinforcement learning for a two-robot job transfer Flow-Shop scheduling problem［J］.Internatio-nal Journal of Production Research，2016，54（4）：1196-1209.

［45］Heger J，Voss T.Dynamically adjusting the k-values of the ATCS rule in a flexible Flow-Shop scenario with reinforcement learning［J］.International Journal of Production Research，2021，DOI：10.1080/00207543.2021.1943762.

［46］César Y，Reyna F，Cáceres A P，et al.An improvement of reinforcement learning approach for permutation of Flow-Shop scheduling problems［J］.Revista Ibérica de Sistemas e Tecnologias de Informao，2019（E18）：257-270.

［47］王凌，潘子肖.基于深度強化學習與迭代貪婪的流水車間調度優化［J］.控制與決策，2021，36（11）：2609-2617.（Wang Ling，Pan Zixiao.Flow shop scheduling optimization based on deep reinforcement learning and iterative greedy［J］.Control and Decision，2021，36 （11）：2609-2617.）

［48］ztop H，Tasgetiren M F，Kandiller L，et al.A novel general variable neighborhood search through Q-learning for no-idle Flow-Shop scheduling［C］//Proc of IEEE Congress on Evolutionary Computation .Piscataway，NJ：IEEE Press，2020：1-8.

［49］Zhu Jialin，Wang Huangang，Zhang Tao.A deep reinforcement lear-ning approach to the flexible Flow-Shop scheduling problem with makespan minimization［C］//Proc of the 9th IEEE Data Driven Control and Learning Systems Conference.Piscataway，NJ：IEEE Press，2020：1220-1225.

［50］Pan Ruyuan，Domg Xingye，Han Sheng.Solving permutation Flow-Shop problem with deep reinforcement learning［C］//Proc of Prognostics and Health Management Conference.Piscataway，NJ：IEEE Press，2020：349-353.

［51］Yang Shengluo，Xu Zhigang，Wang Junyi.Intelligent decision-making of scheduling for dynamic permutation lowshop via deep reinforcement learning［J］.Sensors，2021，21（3）：article ID 1019.

［52］Yang Shengluo，Xu Zhigang.Intelligent scheduling for permutation flow shop with dynamic job arrival via deep reinforcement learning［C］//Proc of the 5th IEEE Advanced Information Technology，Electronic and Automation Control Conference.Piscataway，NJ：IEEE Press，2021：2672-2677.

［53］劉全，翟建偉，章宗長，等.深度強化學習綜述［J］.計算機學報，2018，41（1）：1-27.（Liu Quan，Qu Jianwei，Zhang Zongchang，et al.Summary of deep reinforcement learning［J］.Chinese Journal of Computers，2018，41（1）：1-27.