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

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

0 引言

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

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

近年來(lái)，機(jī)器學(xué)習(xí)中的強(qiáng)化學(xué)習(xí)方法因具有自適應(yīng)能力，被應(yīng)用于解決許多具有挑戰(zhàn)性的決策問(wèn)題[15-18]，利用強(qiáng)化學(xué)習(xí)算法求解調(diào)度問(wèn)題也成為了研究熱點(diǎn)[19]。首先將調(diào)度問(wèn)題轉(zhuǎn)化為馬爾可夫決策過(guò)程(Markov decision process, MDP)，在MDP中狀態(tài)s描述了車間狀態(tài)，強(qiáng)化學(xué)習(xí)智能體(agent)觀察狀態(tài)s，然后采取調(diào)度決策a，并從車間環(huán)境獲得獎(jiǎng)勵(lì)值R，通過(guò)與車間環(huán)境交互獲取調(diào)度經(jīng)驗(yàn)，并以數(shù)據(jù)驅(qū)動(dòng)的方法學(xué)習(xí)經(jīng)驗(yàn)，最大化獎(jiǎng)勵(lì)的同時(shí)最優(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)動(dòng)態(tài)切換的調(diào)度環(huán)境。WANG等[24]將Actor-Critic算法用于晶圓制造系統(tǒng)調(diào)度，對(duì)多目標(biāo)采用加權(quán)的獎(jiǎng)勵(lì)函數(shù)。ZHANG等[25]以工件到達(dá)和機(jī)器釋放事件觸發(fā)調(diào)度，在動(dòng)作空間中考慮了等待并對(duì)獎(jiǎng)勵(lì)函數(shù)進(jìn)行證明?；趶?qiáng)化學(xué)習(xí)的方法適合解決調(diào)度問(wèn)題，但現(xiàn)有基于強(qiáng)化學(xué)習(xí)的方法僅根據(jù)實(shí)時(shí)狀態(tài)進(jìn)行調(diào)度，應(yīng)用于在線調(diào)度問(wèn)題還需考慮車間的動(dòng)態(tài)變化情況。近年來(lá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)勢(shì)動(dòng)作評(píng)論(advantage actor critic, A2C)[34]等深度強(qiáng)化學(xué)習(xí)算法。因此本文基于PPO算法展開研究，考慮到長(zhǎng)短期記憶網(wǎng)絡(luò)(long short-term memory，LSTM)具有記憶與預(yù)測(cè)功能，將其引入強(qiáng)化學(xué)習(xí)智能體以適應(yīng)在線調(diào)度環(huán)境。

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

1 問(wèn)題描述與分析

1.1 問(wèn)題描述

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

Pm|rj,online|∑wjCj

(1)

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

1.2 問(wèn)題分析

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

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

表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í)智能體通過(guò)與車間環(huán)境進(jìn)行交互，感知車間的狀態(tài)變化并嘗試各種調(diào)度行為，獲取獎(jiǎng)勵(lì)值作為調(diào)度決策的評(píng)價(jià)，通過(guò)反復(fù)試錯(cuò)以獲取更高的獎(jiǎng)勵(lì)值，實(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個(gè)模塊組成，包括記憶與預(yù)測(cè)模塊LSTM，策略模塊Actor，評(píng)價(jià)模塊Critic。Actor根據(jù)當(dāng)前的并行機(jī)環(huán)境進(jìn)行調(diào)度決策，Critic對(duì)調(diào)度決策的優(yōu)劣進(jìn)行評(píng)價(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)度時(shí)的車間狀態(tài)，mk為記憶與預(yù)測(cè)模塊提供的時(shí)序信息，ψ為L(zhǎng)STM網(wǎng)絡(luò)參數(shù)。評(píng)價(jià)模塊同樣采用一個(gè)BPNN作為值網(wǎng)絡(luò)，對(duì)真實(shí)值函數(shù)Vπ(sk)進(jìn)行逼近，可表示為V(sk,mk,ω,ψ)，其中ω為值網(wǎng)絡(luò)參數(shù)。

LSTM記憶與預(yù)測(cè)模塊的輸入為每次調(diào)度時(shí)的環(huán)境狀態(tài)和對(duì)應(yīng)的調(diào)度決策，通過(guò)編碼后輸出記憶與預(yù)測(cè)信息，如圖3中LSTM模塊所示。記憶與預(yù)測(cè)模塊的運(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ù)測(cè)信息mk與車間實(shí)時(shí)狀態(tài)sk拼接，輸入給策略模塊和評(píng)價(jià)模塊，使智能體調(diào)度時(shí)的輸入信息更完備，包括實(shí)時(shí)信息與車間時(shí)序動(dòng)態(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ù)測(cè)單元對(duì)歷史調(diào)度決策的記憶編碼輸出作為下次調(diào)度的輸入，使智能體調(diào)度時(shí)可對(duì)歷史調(diào)度進(jìn)行考慮，對(duì)前后調(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ì)列，對(duì)不確定數(shù)量的任務(wù)實(shí)現(xiàn)固定數(shù)量的參數(shù)表征。新任務(wù)到達(dá)后隨機(jī)進(jìn)入空閑緩沖區(qū)，避免智能體學(xué)習(xí)過(guò)程中的樣本不平衡。若任務(wù)緩沖區(qū)已滿則進(jìn)入等待隊(duì)列，按照先入先出原則進(jìn)入任務(wù)緩沖區(qū)中待調(diào)度。狀態(tài)矩陣s=[f1f2f3]從緩沖區(qū)、任務(wù)等待隊(duì)列、設(shè)備3個(gè)維度對(duì)并行機(jī)在線調(diào)度環(huán)境進(jìn)行描述，使強(qiáng)化學(xué)習(xí)智能體對(duì)生產(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ì)列占用率一個(gè)參數(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)度動(dòng)作空間

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

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

a=k0≤k

(5)

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

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

a=q

(6)

2.4 調(diào)度獎(jiǎng)勵(lì)函數(shù)

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

(7)

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

(8)

(9)

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

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

(10)

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

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

2.5 模型更新

強(qiáng)化學(xué)習(xí)智能體通過(guò)與等效并行機(jī)在線環(huán)境交互獲取大量的經(jīng)驗(yàn)數(shù)據(jù)(mk,sk,ak,rk)，并通過(guò)經(jīng)驗(yàn)數(shù)據(jù)對(duì)智能體的3個(gè)模塊進(jìn)行參數(shù)更新。采用現(xiàn)有的PPO算法對(duì)模型進(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)化,并通過(guò)下式對(duì)值網(wǎng)絡(luò)參數(shù)θ、ψ進(jìn)行更新：

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

(11)

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

(12)

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

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

(13)

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

(14)

因此，值網(wǎng)絡(luò)和策略網(wǎng)絡(luò)更新時(shí)，梯度均回傳至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ù)測(cè)信息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ì)算折扣獎(jiǎng)勵(lì)

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ī)律服從泊松分布，且每個(gè)工件有不同的權(quán)重wj和不同的加工時(shí)間pj,wj～U(1,pmax)，pj～U(1,pmax)，pmax為工件的最長(zhǎng)加工時(shí)間。為驗(yàn)證本方法的泛化能力，隨機(jī)生成了100個(gè)算例作為訓(xùn)練集，30個(gè)算例作為測(cè)試集，測(cè)試集僅用于對(duì)比各方法的性能，不作為訓(xùn)練過(guò)程的問(wèn)題輸入。在實(shí)驗(yàn)中，取機(jī)器的數(shù)量m=4，最長(zhǎng)加工時(shí)間pmax=10，泊松分布參數(shù)λ=0.4，每個(gè)算例的模擬調(diào)度時(shí)間為200 h。

3.1 模型訓(xùn)練

在模型訓(xùn)練開始之前，本文算法的參數(shù)主要根據(jù)經(jīng)驗(yàn)值以及智能體交互過(guò)程的實(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)元個(gè)數(shù)設(shè)置為100，LSTM單元的隱層神經(jīng)元個(gè)數(shù)設(shè)置為32，LSTM輸出的消息長(zhǎng)度為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]對(duì)網(wǎng)絡(luò)參數(shù)進(jìn)行更新。緩沖區(qū)的數(shù)量是本算法最關(guān)鍵的參數(shù)，數(shù)量過(guò)多會(huì)導(dǎo)致網(wǎng)絡(luò)復(fù)雜，同樣任務(wù)到達(dá)情況下空閑的緩沖區(qū)多，智能體選中任務(wù)的難度更高，學(xué)習(xí)更慢;緩沖區(qū)過(guò)少則導(dǎo)致緩沖區(qū)長(zhǎng)時(shí)間飽和，可能造成優(yōu)先級(jí)高的工件無(wú)法及時(shí)進(jìn)入緩沖區(qū)。通過(guò)監(jiān)控交互過(guò)程中的緩沖區(qū)和等待隊(duì)列的情況，設(shè)置緩沖區(qū)數(shù)量nslot=20，等待隊(duì)列最大容量為10，時(shí)間窗口設(shè)置為1 h。在每次迭代中，強(qiáng)化學(xué)習(xí)智能體在每個(gè)訓(xùn)練集算例上重復(fù)8次獨(dú)立實(shí)驗(yàn)。

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

(a)訓(xùn)練過(guò)程累積折扣獎(jiǎng)勵(lì)

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

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

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

表3 不同方法的時(shí)間對(duì)比

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

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

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

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

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

(a)LSTM-PPO,∑wjCj=8911

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

4 結(jié)論

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

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

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

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

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