基于長短期記憶近端策略優化強化學習的等效并行機在線調度方法

賀俊杰 張 潔 張 朋 汪俊亮 鄭 鵬 王 明

1.東華大學機械工程學院，上海,2016202.上海交通大學機械與動力工程學院，上海,200240

0 引言

在晶圓制造、航天制造等生產系統中，各工序生產單元通常需要連續不斷地將動態到達的工件指派到多臺并行設備上，該類生產單元的調度問題是典型的等效并行機在線調度問題。以航天制造業為例，航天企業迫切需要實現短周期、高品質、快速響應的生產模式[1]，但航天產品制造過程中有的零件包含復雜曲面，其特征復雜且加工質量要求高，需采用昂貴的多軸精密數控機床進行加工。此類零件的加工時間長且在加工過程中易報廢，使得復雜曲面的數控加工工序成為航天零件實際生產過程中的瓶頸工序。航天零件生產具有設計迭代快、生產批量小的特點，需要車間調度人員快速作出調度響應。為降低生產成本，該類零件往往安排在同一車間生產，通過其中的任意一臺同型號的數控機床進行加工。此外，晶圓生產的光刻區調度、爐管區調度，以及紡織品生產的織機調度、染缸調度，鋼鐵生產的轉爐煉鋼等都可抽象為此類調度問題。面對這類生產調度問題，在實現快速響應的同時最大程度上實現調度優化，是滿足客戶要求的必要條件，具有重要的理論意義和工程實際應用價值。

目前針對等效并行機在線調度問題的研究方法分為兩種，一是啟發式規則，BANSAL[2]和LEONARDI等[3]提出了最小化流動時間的啟發式算法；SITTERS[4]和HALL等[5]提出了最小化完工時間的啟發式算法，這種方法執行時間短，能夠實現快速響應，但往往針對一種特定場景設計，缺乏自適應性[6]。二是智能算法，柳丹丹等[7]設計了改進遺傳算法應用于等效并行機在線調度問題；許顯楊等[8]提出了面向設備動態性的蟻群算法，該方法雖能精確求解，但求解時間長，無法實時響應，且頻繁的滾動調度會導致準備工作效率低下[9]。在半導體制造、紡織品生產[10]等行業，因在制品眾多且無法搶占加工，調度時需考慮等待未來到達的工件，進一步優化調度方案，因此，是否等待是最關鍵的問題。有學者在加權最短加工時間優先(weighted shortest processing time first, WSPT)規則[11-12]的基礎上設計等待機制，如ANDERSON等[13]提出D-WSPT規則以優化單機的加權完工時間和；TAO[14]進一步提出針對等效并行機的AD-WSPT算法，但以上兩種方法對在線調度的自適應性不足。

近年來，機器學習中的強化學習方法因具有自適應能力，被應用于解決許多具有挑戰性的決策問題[15-18]，利用強化學習算法求解調度問題也成為了研究熱點[19]。首先將調度問題轉化為馬爾可夫決策過程(Markov decision process, MDP)，在MDP中狀態s描述了車間狀態，強化學習智能體(agent)觀察狀態s，然后采取調度決策a，并從車間環境獲得獎勵值R，通過與車間環境交互獲取調度經驗，并以數據驅動的方法學習經驗，最大化獎勵的同時最優化調度策略[20-21]。GABEL等[22]提出了基于策略梯度(policy gradient, PG)的作業車間調度方法，在狀態矩陣中設計了下一道工序預覽。王世進等[23]提出基于Q-Learning的單機調度方法，適用于多目標動態切換的調度環境。WANG等[24]將Actor-Critic算法用于晶圓制造系統調度，對多目標采用加權的獎勵函數。ZHANG等[25]以工件到達和機器釋放事件觸發調度，在動作空間中考慮了等待并對獎勵函數進行證明?；趶娀瘜W習的方法適合解決調度問題，但現有基于強化學習的方法僅根據實時狀態進行調度，應用于在線調度問題還需考慮車間的動態變化情況。近年來提出的近端策略優化(proximal policy optimization, PPO)算法是一種基于策略的深度強化學習算法，該算法交互的經驗數據可進行重復利用使得采樣效率更高，該算法獨有的損失函數裁剪使得該算法學習穩定性更強，在交通[26-27]、機器人[28-29]、車間調度[30-31]等智能控制領域得到了實際應用，且明顯優于策略梯度(policygradient, PG)[32]、信任區域策略優化(trust region policy optimization, TRPO)[33]、優勢動作評論(advantage actor critic, A2C)[34]等深度強化學習算法。因此本文基于PPO算法展開研究，考慮到長短期記憶網絡(long short-term memory，LSTM)具有記憶與預測功能，將其引入強化學習智能體以適應在線調度環境。

考慮到加權完工時間和是提升客戶滿意度和降低庫存成本的重要指標，本文針對等效并行機在線調度問題，以最小化加權完工時間和為優化目標，提出基于長短期記憶近端策略優化(proximal policy optimization with long short-term memory，LSTM-PPO)的等效并行機在線調度方法。針對任務在線到達的不確定性，設計了考慮等待策略的在線調度決策流程；針對進行等待所需考慮的全局信息，在強化學習智能體結構中引入LSTM實現時間維的車間狀態信息融合，構建高效的LSTM-PPO在線調度算法。

1 問題描述與分析

1.1 問題描述

有n個工件需在m臺相同的設備上進行加工，每個工件j有到達時間rj、權重wj和加工時長pj，直到工件到達才已知該工件的所有信息。工件一旦開始加工則無法中斷。當一個工件到達后就可進行加工，且一個工件僅能在一臺機器上加工一次[14]。因此，本調度問題用三元描述法描述如下：

Pm|rj,online|∑wjCj

(1)

式中，Pm表示等效并行機；online表示在線環境；Cj為工件j的完工時間。

1.2 問題分析

在線環境下有效的等待策略是優化∑wjCj的關鍵。圖1的案例展示了在t1時刻是否等待的兩種情形，案例中任務j1和j2的參數如表1所示。t1時刻無等待的調度方案先加工j1再加工j2；t1時刻等待的調度方案則先加工j2再加工j1，因j2的權重較大且加工時間短，j1的加工時間長且權重較小，故有等待的調度方案加權完工時間和比無等待的多45。但由于t1時刻未知j2的到達時間等參數，因而在t1時刻合理的調度決策較困難。在線環境下，有效融合時間維度的任務和機器狀態對當前時刻的調度決策有重要意義。

圖1 有無等待的調度方法對比

表1 案例中的任務參數

2 基于LSTM-PPO強化學習的等效并行機在線調度系統

在基于強化學習的調度系統中，強化學習智能體通過與車間環境進行交互，感知車間的狀態變化并嘗試各種調度行為，獲取獎勵值作為調度決策的評價，通過反復試錯以獲取更高的獎勵值，實現最優的調度策略?；趶娀瘜W習的等效并行機調度系統交互流程如圖2所示。

圖2 基于強化學習的等效并行機調度交互流程

2.1 調度智能體

LSTM-PPO強化學習調度智能體是一種Actor-Critic結構類型的智能體，如圖3所示,由3個模塊組成，包括記憶與預測模塊LSTM，策略模塊Actor，評價模塊Critic。Actor根據當前的并行機環境進行調度決策，Critic對調度決策的優劣進行評價。策略模塊采用前饋神經網絡(back propagation neural network，BPNN)逼近最優的調度策略π*，表示為π(a|sk,mk,θ,ψ)，其中θ為網絡參數，sk為第k次調度時的車間狀態，mk為記憶與預測模塊提供的時序信息，ψ為LSTM網絡參數。評價模塊同樣采用一個BPNN作為值網絡，對真實值函數Vπ(sk)進行逼近，可表示為V(sk,mk,ω,ψ)，其中ω為值網絡參數。

LSTM記憶與預測模塊的輸入為每次調度時的環境狀態和對應的調度決策，通過編碼后輸出記憶與預測信息，如圖3中LSTM模塊所示。記憶與預測模塊的運行可表示為

圖3 LSTM-PPO智能體結構

mk=LSTM(sak-1,hk-1,ck-1,ψ)

(2)

sak-1=(sk-1,ak-1)

(3)

式中，hk-1和ck-1為k次決策后LSTM網絡輸出的隱狀態;sak-1為k次決策的車間狀態sk-1與調度決策ak-1組成的向量。

在功能方面，將輸出的記憶與預測信息mk與車間實時狀態sk拼接，輸入給策略模塊和評價模塊，使智能體調度時的輸入信息更完備，包括實時信息與車間時序動態信息。在網絡結構方面，mk作為中間變量將LSTM網絡輸出層與值網絡的輸入層、策略網絡的輸入層相連，使得LSTM網絡成為值網絡和策略網絡共享前綴網絡。

將記憶與預測單元對歷史調度決策的記憶編碼輸出作為下次調度的輸入，使智能體調度時可對歷史調度進行考慮，對前后調度決策之間的相互關聯與影響進行表征，實現全局優化。

2.2 調度狀態空間

狀態空間S的定義與優化目標密切相關，需反映車間調度相關特征和車間狀態變化。設定任務緩沖區和等待隊列，對不確定數量的任務實現固定數量的參數表征。新任務到達后隨機進入空閑緩沖區，避免智能體學習過程中的樣本不平衡。若任務緩沖區已滿則進入等待隊列，按照先入先出原則進入任務緩沖區中待調度。狀態矩陣s=[f1f2f3]從緩沖區、任務等待隊列、設備3個維度對并行機在線調度環境進行描述，使強化學習智能體對生產狀態進行完備的觀察。其中緩沖區狀態f1=(f1,1，f1,2，…,f1,k,…，f1,q)，緩沖區k的狀態向量f1,k=(f1,k,1,f1,k,2,f1,k,3,f1,k,4)，其中任務等待隊列狀態f2僅包含等待隊列占用率一個參數；機器狀態f3=(f3,1，f3,2，…,f3,i,…，f3,m)，其中設備i的狀態向量f3,i定義為(f3,i,1,f3,i,2,f3,i,3)，參數表達式如表2所示。

表2 并行機環境狀態參數

綜上，設緩沖區數量為nslot，機器數量為m，得到一維等效并行機環境狀態矩陣尺寸ns如下:

ns=nslot×4+1+m×3

(4)

2.3 調度動作空間

調度動作空間A即調度決策集合，主要包括以下調度決策：

(1)選擇第k個緩沖區。若該緩沖區中存在一個工件j，則將該工件加載到任意一臺空閑機器上；若該緩沖區為空，則作用同調度決策(2)。通過選緩沖區間接選擇工件，改善了規則選擇可能導致的解空間縮小和冗余的問題:

a=k0≤k

(5)

式中，q為緩沖區的最大數量。

(2)等待。不選擇任何工件進行加工。通過將等待引入到調度的動作空間，使智能體可在調度時選擇等待:

a=q

(6)

2.4 調度獎勵函數

強化學習在最大化獎勵值R的同時實現目標最優化。獎勵函數R對智能體的調度決策對目標函數做出的貢獻進行量化評估，為智能體學習調度策略提供有效指導。將目標函數∑wjCj分解，轉化為每次調度決策的獎勵值，避免獎勵稀疏：

(7)

因式(7)中到達時間rj與加工時間pj為常量，所有優化目標等效于最小化加權的等待時間和，進一步通過下式分解到每個單位時間：

(8)

(9)

式中，sj為任務的加工狀態參數，判定任務是否處于等待狀態。

因此，最小化加權完工時間和實際上等效于最小化每一時間節點的待加工任務數權重之和，據此推論設計獎勵函數R如下：

(10)

式中，St為t時刻的狀態。

對式(10)中的加權等待時間取相反數，因此目標函數∑wjCj越小，獎勵值R越大。

2.5 模型更新

強化學習智能體通過與等效并行機在線環境交互獲取大量的經驗數據(mk,sk,ak,rk)，并通過經驗數據對智能體的3個模塊進行參數更新。采用現有的PPO算法對模型進行更新，此外，因LSTM網絡是策略網絡和值網絡的共同前綴層，因此在模型更新階段值網絡和策略網絡的損失均回傳至LSTM網絡以實現整體網絡優化,并通過下式對值網絡參數θ、ψ進行更新：

θ←θ+αθJ(θ,ψ)

(11)

ψ←ψ+αθJ(θ,ψ)

(12)

通過下式對值網絡參數ω、ψ進行更新：

ω←ω-αωL(ω,ψ)

(13)

ψ←ψ-αωL(ω,ψ)

(14)

因此，值網絡和策略網絡更新時，梯度均回傳至LSTM網絡并更新其參數ψ，如圖3中損失傳播路線所示。綜上得到基于LSTM-PPO的等效并行機在線調度算法：

1: 隨機初始化智能體參數θ,ω,ψ

2: for each episode do:

3:k=0

4: 初始化任務序列、記憶與預測信息mk、經驗緩存池和狀態sk

5: while not done ork≤Kdo:

6: 根據策略π采取調度決策ak～π(a|sk,mk,θ,ψ)

7:sk+1,rk,done←Env(sk,ak)

8: 刷新LSTM信息mk+1=LSTM(sak,hk,ck,ψ)

9: 將經驗[sk,mk,ak,rk]保存至經驗緩存池

10:k←k+1

11: 更新并行機環境狀態s←s′

12: end while

13: 計算折扣獎勵

14: if緩沖區經驗數目>小批量數目Mdo:

15: forepoch=1,2,…,Ndo:

17: 更新策略網絡和LSTM(θ,ψ)←(θ,ψ)+αθJ(θ,ψ)

18: 更新值網絡和LSTM(ω,ψ)←(ω,ψ)-αωL(ω,ψ)

19: end for

20:θold,wold,ψold←θ,w,ψ

21: end if

22: end for

3 實驗驗證

使用Pycharm軟件進行編程，在Windows10操作系統、2.9 GHz CPU、16G內存的計算機和Python3.5環境下運行。以面向對象的形式搭建了并行機環境類，包括機器類、工件類等，并用Pytorch實現了智能體的模型搭建。

在仿真算例實驗中，采用與文獻[14]相同的算例生成方法：設工件的到達規律服從泊松分布，且每個工件有不同的權重wj和不同的加工時間pj,wj～U(1,pmax)，pj～U(1,pmax)，pmax為工件的最長加工時間。為驗證本方法的泛化能力，隨機生成了100個算例作為訓練集，30個算例作為測試集，測試集僅用于對比各方法的性能，不作為訓練過程的問題輸入。在實驗中，取機器的數量m=4，最長加工時間pmax=10，泊松分布參數λ=0.4，每個算例的模擬調度時間為200 h。

3.1 模型訓練

在模型訓練開始之前，本文算法的參數主要根據經驗值以及智能體交互過程的實際數據情況進行設置。首先，LSTM-PPO強化學習智能體的Actor網絡和Critic網絡均為BP神經網絡，隱含層的神經元個數設置為100，LSTM單元的隱層神經元個數設置為32，LSTM輸出的消息長度為8，取Actor網絡的學習率α1=0.001，Critic網絡的學習率α2=0.002，累積折扣因子γ=0.9，損失裁剪參數ε=0.2，為加快收斂速度，采用Adam算法[35]對網絡參數進行更新。緩沖區的數量是本算法最關鍵的參數，數量過多會導致網絡復雜，同樣任務到達情況下空閑的緩沖區多，智能體選中任務的難度更高，學習更慢;緩沖區過少則導致緩沖區長時間飽和，可能造成優先級高的工件無法及時進入緩沖區。通過監控交互過程中的緩沖區和等待隊列的情況，設置緩沖區數量nslot=20，等待隊列最大容量為10，時間窗口設置為1 h。在每次迭代中，強化學習智能體在每個訓練集算例上重復8次獨立實驗。

圖4a展示了LSTM-PPO方法的訓練迭代過程。在迭代次數為0時，由于強化學習智能體中網絡參數均初始化為隨機數，故LSTM-PPO方法與隨機調度非常接近，而隨著迭代次數的增加，本文方法獲得的獎勵函數值逐漸超越現有的幾種啟發式算法。啟發式算法和隨機調度因不具學習能力，故獎勵值和目標函數值均不隨迭代次數發生變化。通過與環境的交互獲取經驗并學習，可見LSTM-PPO智能體可快速學習如何調度以獲取更高的獎勵值。同時，圖4b表明在訓練集上的加權完工時間和也在相應地減小，驗證了所設計的獎勵函數指導優化智能體優化目標函數的有效性，直至迭代7000次已基本收斂，且在這些訓練集上訓練迭代7000次時，強化學習智能體的平均水平已優于現有的幾種啟發式算法。

(a)訓練過程累積折扣獎勵

3.2 仿真算例驗證

將訓練后的LSTM-PPO模型進行保存，在測試集上與改進前的PPO算法、現有啟發式算法進行對比，仿真的測試集包括30個算例，智能體在學習過程中未學習過這些測試算例。首先將本文提出的LSTM-PPO算法與現有的PPO算法進行對比以驗證融入LSTM的有效性，如表3中的前兩列所示，在相同訓練次數與迭代條件下，LSTM-PPO算法優于未改進的PPO算法，融入的LSTM網絡能結合過去的歷史狀態和歷史調度進行預測，并將預測的消息片段輔助智能體進行調度。

將經過訓練后的強化學習智能體與現有的3種啟發式算法進行對比。D-WSPT和AD-WSPT為兩種改進的WSPT規則，可根據當前時間和任務權重以及加工時間判定是否等待。訓練結束后最終測試結果的均值和方差見表3，LSTM-PPO方法的均值和方差最優；除本文方法外，性能最好的是WSPT規則，D-WSPT規則和AD-WSPT規則的等待策略對具有不確定性的在線調度環境缺乏自適應性。

表3 不同方法的時間對比

3.3 調度策略分析

對本文方法在調度過程中的等待決策進行分析。若存在機器空閑且有待加工工件，調度決策為等待，則這些待加工工件定義為被延遲。記錄所有的等待決策，分析工件被延遲的頻率。如圖5所示，每個方塊中的數值表示該權重和加工時間的工件被延遲的頻率。由圖可知，加工時間越長且權重越小的工件被延遲的頻率越高，這是智能體從數據中學習的等待策略。工件延遲加工，若短時間內到達加工時間更短或權重更大的工件即可減小加權完工時間和∑wjCj。圖5表明權重大且加工時間短的任務會有更高的加工優先級，極少被延遲加工，若可加工任務均權重較小且加工時間較長，則被延遲加工的概率較高。智能體學習到的策略是一種提升的WSPT規則，調度輸入的是更全面的車間狀態矩陣和時序動態信息，通過神經網絡梯度下降進行策略學習，得到了通過合理等待實現目標優化的調度策略。

圖5 不同權重和加工時長的工件被延遲的頻率

3.4 企業算例驗證

將本文提出的算法應用于某航天機加車間的真實調度算例。該車間有4臺設備，43個歷史加工任務，各工件的加工時間等相關參數見表4。利用不同算法對算例進行在線調度，調度結果繪制成甘特圖，如圖6所示，每個方塊表示一個工件，方塊內的數字表示工件的到達時間，被延遲的工件用藍色標出。由圖6可知，LSTM-PPO方法的等待決策發生在機器2空閑時，智能體選擇等待即將到達的較短加工時間的工件k，而工件j被延遲加工。由于工件j的加工時間較長，故延遲該工件j的加工而等待工件k有效降低了目標函數值。由甘特圖可知，WSPT規則無法等待，D-WSPT規則與AD-WSPT規則的等待觸發條件均與當前時刻相關，使得等待決策發生在調度起始的一段時間內，本文方法的在線環境自適應性更強。

(a)LSTM-PPO,∑wjCj=8911

表4 實際歷史任務的工件參數

4 結論

(1)本文針對等效并行機在線調度問題，以最小化加權完工時間和為目標，對任務在線到達的特性和決策等待的難點進行了分析，提出考慮等待的在線調度策略。

(2)針對任務到達的動態性設計了帶時序信息融合的LSTM-PPO強化學習智能體，并定義了調度的狀態空間、動作空間和獎勵函數，成功將LSTM-PPO調度決策智能體應用于等效并行機在線調度問題。

(3)智能體觀察車間的實時狀態和動態信息進行調度，通過調度交互獲取經驗并通過梯度下降法更新策略實現最小化加權完工時間和，訓練得到的最優調度策略存儲在神經網絡，調度決策速度快。

(4)實驗結果表明，所得模型的調度結果優于3種啟發式算法。對調度策略中的工件延遲加工頻率分布和甘特圖進行分析，證明本文提出的方法通過自學習得到在線環境下自適應等待的調度策略，對動態環境下的生產調度策略探索具有一定參考價值。

在大規模問題中，設計的緩沖區數量決定了輸出神經元的個數，隨著問題規模的增大，需要的輸出神經元數量增大，可能導致網絡難以訓練。下一步將尋求一種更為彈性的方法以代替緩沖區，且能解決規則選擇方法過于壓縮解空間的問題。進一步對問題進行深入研究，考慮在線的并行批處理機調度問題，研究如何實現多智能體協作機制，并實現在晶圓制造、航天制造等領域的實際應用。