基于長短期記憶近端策略優(yōu)化強(qiáng)化學(xué)習(xí)的等效并行機(jī)在線調(diào)度方法

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

1.東華大學(xué)機(jī)械工程學(xué)院，上海,2016202.上海交通大學(xué)機(jī)械與動力工程學(xué)院，上海,200240

0 引言

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

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

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

考慮到加權(quán)完工時間和是提升客戶滿意度和降低庫存成本的重要指標(biāo)，本文針對等效并行機(jī)在線調(diào)度問題，以最小化加權(quán)完工時間和為優(yōu)化目標(biāo)，提出基于長短期記憶近端策略優(yōu)化(proximal policy optimization with long short-term memory，LSTM-PPO)的等效并行機(jī)在線調(diào)度方法。針對任務(wù)在線到達(dá)的不確定性，設(shè)計(jì)了考慮等待策略的在線調(diào)度決策流程；針對進(jìn)行等待所需考慮的全局信息，在強(qiáng)化學(xué)習(xí)智能體結(jié)構(gòu)中引入LSTM實(shí)現(xiàn)時間維的車間狀態(tài)信息融合，構(gòu)建高效的LSTM-PPO在線調(diào)度算法。

1 問題描述與分析

1.1 問題描述

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

Pm|rj,online|∑wjCj

(1)

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

1.2 問題分析

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

圖1 有無等待的調(diào)度方法對比

表1 案例中的任務(wù)參數(shù)

2 基于LSTM-PPO強(qiáng)化學(xué)習(xí)的等效并行機(jī)在線調(diào)度系統(tǒng)

在基于強(qiáng)化學(xué)習(xí)的調(diào)度系統(tǒng)中，強(qiáng)化學(xué)習(xí)智能體通過與車間環(huán)境進(jìn)行交互，感知車間的狀態(tài)變化并嘗試各種調(diào)度行為，獲取獎勵值作為調(diào)度決策的評價(jià)，通過反復(fù)試錯以獲取更高的獎勵值，實(shí)現(xiàn)最優(yōu)的調(diào)度策略?；趶?qiáng)化學(xué)習(xí)的等效并行機(jī)調(diào)度系統(tǒng)交互流程如圖2所示。

圖2 基于強(qiáng)化學(xué)習(xí)的等效并行機(jī)調(diào)度交互流程

2.1 調(diào)度智能體

LSTM-PPO強(qiáng)化學(xué)習(xí)調(diào)度智能體是一種Actor-Critic結(jié)構(gòu)類型的智能體，如圖3所示,由3個模塊組成，包括記憶與預(yù)測模塊LSTM，策略模塊Actor，評價(jià)模塊Critic。Actor根據(jù)當(dāng)前的并行機(jī)環(huán)境進(jìn)行調(diào)度決策，Critic對調(diào)度決策的優(yōu)劣進(jìn)行評價(jià)。策略模塊采用前饋神經(jīng)網(wǎng)絡(luò)(back propagation neural network，BPNN)逼近最優(yōu)的調(diào)度策略π*，表示為π(a|sk,mk,θ,ψ)，其中θ為網(wǎng)絡(luò)參數(shù)，sk為第k次調(diào)度時的車間狀態(tài)，mk為記憶與預(yù)測模塊提供的時序信息，ψ為LSTM網(wǎng)絡(luò)參數(shù)。評價(jià)模塊同樣采用一個BPNN作為值網(wǎng)絡(luò)，對真實(shí)值函數(shù)Vπ(sk)進(jìn)行逼近，可表示為V(sk,mk,ω,ψ)，其中ω為值網(wǎng)絡(luò)參數(shù)。

LSTM記憶與預(yù)測模塊的輸入為每次調(diào)度時的環(huán)境狀態(tài)和對應(yīng)的調(diào)度決策，通過編碼后輸出記憶與預(yù)測信息，如圖3中LSTM模塊所示。記憶與預(yù)測模塊的運(yùn)行可表示為

圖3 LSTM-PPO智能體結(jié)構(gòu)

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

(2)

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

(3)

式中，hk-1和ck-1為k次決策后LSTM網(wǎng)絡(luò)輸出的隱狀態(tài);sak-1為k次決策的車間狀態(tài)sk-1與調(diào)度決策ak-1組成的向量。

在功能方面，將輸出的記憶與預(yù)測信息mk與車間實(shí)時狀態(tài)sk拼接，輸入給策略模塊和評價(jià)模塊，使智能體調(diào)度時的輸入信息更完備，包括實(shí)時信息與車間時序動態(tài)信息。在網(wǎng)絡(luò)結(jié)構(gòu)方面，mk作為中間變量將LSTM網(wǎng)絡(luò)輸出層與值網(wǎng)絡(luò)的輸入層、策略網(wǎng)絡(luò)的輸入層相連，使得LSTM網(wǎng)絡(luò)成為值網(wǎng)絡(luò)和策略網(wǎng)絡(luò)共享前綴網(wǎng)絡(luò)。

將記憶與預(yù)測單元對歷史調(diào)度決策的記憶編碼輸出作為下次調(diào)度的輸入，使智能體調(diào)度時可對歷史調(diào)度進(jìn)行考慮，對前后調(diào)度決策之間的相互關(guān)聯(lián)與影響進(jìn)行表征，實(shí)現(xiàn)全局優(yōu)化。

2.2 調(diào)度狀態(tài)空間

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

表2 并行機(jī)環(huán)境狀態(tài)參數(shù)

綜上，設(shè)緩沖區(qū)數(shù)量為nslot，機(jī)器數(shù)量為m，得到一維等效并行機(jī)環(huán)境狀態(tài)矩陣尺寸ns如下:

ns=nslot×4+1+m×3

(4)

2.3 調(diào)度動作空間

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

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

a=k0≤k

(5)

式中，q為緩沖區(qū)的最大數(shù)量。

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

a=q

(6)

2.4 調(diào)度獎勵函數(shù)

強(qiáng)化學(xué)習(xí)在最大化獎勵值R的同時實(shí)現(xiàn)目標(biāo)最優(yōu)化。獎勵函數(shù)R對智能體的調(diào)度決策對目標(biāo)函數(shù)做出的貢獻(xiàn)進(jìn)行量化評估，為智能體學(xué)習(xí)調(diào)度策略提供有效指導(dǎo)。將目標(biāo)函數(shù)∑wjCj分解，轉(zhuǎn)化為每次調(diào)度決策的獎勵值，避免獎勵稀疏：

(7)

因式(7)中到達(dá)時間rj與加工時間pj為常量，所有優(yōu)化目標(biāo)等效于最小化加權(quán)的等待時間和，進(jìn)一步通過下式分解到每個單位時間：

(8)

(9)

式中，sj為任務(wù)的加工狀態(tài)參數(shù)，判定任務(wù)是否處于等待狀態(tài)。

因此，最小化加權(quán)完工時間和實(shí)際上等效于最小化每一時間節(jié)點(diǎn)的待加工任務(wù)數(shù)權(quán)重之和，據(jù)此推論設(shè)計(jì)獎勵函數(shù)R如下：

(10)

式中，St為t時刻的狀態(tài)。

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

2.5 模型更新

強(qiáng)化學(xué)習(xí)智能體通過與等效并行機(jī)在線環(huán)境交互獲取大量的經(jīng)驗(yàn)數(shù)據(jù)(mk,sk,ak,rk)，并通過經(jīng)驗(yàn)數(shù)據(jù)對智能體的3個模塊進(jìn)行參數(shù)更新。采用現(xiàn)有的PPO算法對模型進(jìn)行更新，此外，因LSTM網(wǎng)絡(luò)是策略網(wǎng)絡(luò)和值網(wǎng)絡(luò)的共同前綴層，因此在模型更新階段值網(wǎng)絡(luò)和策略網(wǎng)絡(luò)的損失均回傳至LSTM網(wǎng)絡(luò)以實(shí)現(xiàn)整體網(wǎng)絡(luò)優(yōu)化,并通過下式對值網(wǎng)絡(luò)參數(shù)θ、ψ進(jìn)行更新：

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

(11)

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

(12)

通過下式對值網(wǎng)絡(luò)參數(shù)ω、ψ進(jìn)行更新：

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

(13)

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

(14)

因此，值網(wǎng)絡(luò)和策略網(wǎng)絡(luò)更新時，梯度均回傳至LSTM網(wǎng)絡(luò)并更新其參數(shù)ψ，如圖3中損失傳播路線所示。綜上得到基于LSTM-PPO的等效并行機(jī)在線調(diào)度算法：

1: 隨機(jī)初始化智能體參數(shù)θ,ω,ψ

2: for each episode do:

3:k=0

4: 初始化任務(wù)序列、記憶與預(yù)測信息mk、經(jīng)驗(yàn)緩存池和狀態(tài)sk

5: while not done ork≤Kdo:

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

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

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

9: 將經(jīng)驗(yàn)[sk,mk,ak,rk]保存至經(jīng)驗(yàn)緩存池

10:k←k+1

11: 更新并行機(jī)環(huán)境狀態(tài)s←s′

12: end while

13: 計(jì)算折扣獎勵

14: if緩沖區(qū)經(jīng)驗(yàn)數(shù)目>小批量數(shù)目Mdo:

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

17: 更新策略網(wǎng)絡(luò)和LSTM(θ,ψ)←(θ,ψ)+αθJ(θ,ψ)

18: 更新值網(wǎng)絡(luò)和LSTM(ω,ψ)←(ω,ψ)-αωL(ω,ψ)

19: end for

20:θold,wold,ψo(hù)ld←θ,w,ψ

21: end if

22: end for

3 實(shí)驗(yàn)驗(yàn)證

使用Pycharm軟件進(jìn)行編程，在Windows10操作系統(tǒng)、2.9 GHz CPU、16G內(nèi)存的計(jì)算機(jī)和Python3.5環(huán)境下運(yùn)行。以面向?qū)ο蟮男问酱罱瞬⑿袡C(jī)環(huán)境類，包括機(jī)器類、工件類等，并用Pytorch實(shí)現(xiàn)了智能體的模型搭建。

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

3.1 模型訓(xùn)練

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

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

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

3.2 仿真算例驗(yàn)證

將訓(xùn)練后的LSTM-PPO模型進(jìn)行保存，在測試集上與改進(jìn)前的PPO算法、現(xiàn)有啟發(fā)式算法進(jìn)行對比，仿真的測試集包括30個算例，智能體在學(xué)習(xí)過程中未學(xué)習(xí)過這些測試算例。首先將本文提出的LSTM-PPO算法與現(xiàn)有的PPO算法進(jìn)行對比以驗(yàn)證融入LSTM的有效性，如表3中的前兩列所示，在相同訓(xùn)練次數(shù)與迭代條件下，LSTM-PPO算法優(yōu)于未改進(jìn)的PPO算法，融入的LSTM網(wǎng)絡(luò)能結(jié)合過去的歷史狀態(tài)和歷史調(diào)度進(jìn)行預(yù)測，并將預(yù)測的消息片段輔助智能體進(jìn)行調(diào)度。

將經(jīng)過訓(xùn)練后的強(qiáng)化學(xué)習(xí)智能體與現(xiàn)有的3種啟發(fā)式算法進(jìn)行對比。D-WSPT和AD-WSPT為兩種改進(jìn)的WSPT規(guī)則，可根據(jù)當(dāng)前時間和任務(wù)權(quán)重以及加工時間判定是否等待。訓(xùn)練結(jié)束后最終測試結(jié)果的均值和方差見表3，LSTM-PPO方法的均值和方差最優(yōu)；除本文方法外，性能最好的是WSPT規(guī)則，D-WSPT規(guī)則和AD-WSPT規(guī)則的等待策略對具有不確定性的在線調(diào)度環(huán)境缺乏自適應(yīng)性。

表3 不同方法的時間對比

3.3 調(diào)度策略分析

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

圖5 不同權(quán)重和加工時長的工件被延遲的頻率

3.4 企業(yè)算例驗(yàn)證

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

(a)LSTM-PPO,∑wjCj=8911

表4 實(shí)際歷史任務(wù)的工件參數(shù)

4 結(jié)論

(1)本文針對等效并行機(jī)在線調(diào)度問題，以最小化加權(quán)完工時間和為目標(biāo)，對任務(wù)在線到達(dá)的特性和決策等待的難點(diǎn)進(jìn)行了分析，提出考慮等待的在線調(diào)度策略。

(2)針對任務(wù)到達(dá)的動態(tài)性設(shè)計(jì)了帶時序信息融合的LSTM-PPO強(qiáng)化學(xué)習(xí)智能體，并定義了調(diào)度的狀態(tài)空間、動作空間和獎勵函數(shù)，成功將LSTM-PPO調(diào)度決策智能體應(yīng)用于等效并行機(jī)在線調(diào)度問題。

(3)智能體觀察車間的實(shí)時狀態(tài)和動態(tài)信息進(jìn)行調(diào)度，通過調(diào)度交互獲取經(jīng)驗(yàn)并通過梯度下降法更新策略實(shí)現(xiàn)最小化加權(quán)完工時間和，訓(xùn)練得到的最優(yōu)調(diào)度策略存儲在神經(jīng)網(wǎng)絡(luò)，調(diào)度決策速度快。

(4)實(shí)驗(yàn)結(jié)果表明，所得模型的調(diào)度結(jié)果優(yōu)于3種啟發(fā)式算法。對調(diào)度策略中的工件延遲加工頻率分布和甘特圖進(jìn)行分析，證明本文提出的方法通過自學(xué)習(xí)得到在線環(huán)境下自適應(yīng)等待的調(diào)度策略，對動態(tài)環(huán)境下的生產(chǎn)調(diào)度策略探索具有一定參考價(jià)值。

在大規(guī)模問題中，設(shè)計(jì)的緩沖區(qū)數(shù)量決定了輸出神經(jīng)元的個數(shù)，隨著問題規(guī)模的增大，需要的輸出神經(jīng)元數(shù)量增大，可能導(dǎo)致網(wǎng)絡(luò)難以訓(xùn)練。下一步將尋求一種更為彈性的方法以代替緩沖區(qū)，且能解決規(guī)則選擇方法過于壓縮解空間的問題。進(jìn)一步對問題進(jìn)行深入研究，考慮在線的并行批處理機(jī)調(diào)度問題，研究如何實(shí)現(xiàn)多智能體協(xié)作機(jī)制，并實(shí)現(xiàn)在晶圓制造、航天制造等領(lǐng)域的實(shí)際應(yīng)用。