肖鵬飛，張超勇+，孟磊磊,2，洪 輝，戴 穩(wěn)

(1.華中科技大學(xué)數(shù)字制造裝備與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074；2 聊城大學(xué) 計(jì)算機(jī)學(xué)院，山東 聊城 252059)

0 引言

流水車間是一類制造行業(yè)常見的生產(chǎn)布局配置形式[1-2]。流水車間調(diào)度問(wèn)題可以描述為：工件集N={J1,J2,…,Jn}由機(jī)器集M={M1,M2,…,Mm}進(jìn)行加工，每個(gè)工件經(jīng)由相同的工藝路線，即經(jīng)由機(jī)器M1，M2，…直到最后一臺(tái)機(jī)器Mm加工。調(diào)度決策就是安排工件通過(guò)每臺(tái)機(jī)器的加工順序。若規(guī)定所有m臺(tái)機(jī)器上n個(gè)工件的加工順序均相同，則稱其為置換流水車間調(diào)度(Permutation Flow-shop Scheduling，PFS)問(wèn)題；若允許不同機(jī)器上工件的加工順序可以改變，這類松弛置換約束條件的調(diào)度問(wèn)題稱為非置換流水車間調(diào)度(Non-Permutation Flow-shop Scheduling，NPFS)問(wèn)題。NPFS問(wèn)題需要滿足以下約束條件：①每臺(tái)機(jī)器每個(gè)時(shí)刻只能加工一道工序且不允許中斷；②每個(gè)工件Jj都有對(duì)應(yīng)于機(jī)器i(i=1,2,…,m)上的工序加工時(shí)間pij，準(zhǔn)備時(shí)間包含在加工時(shí)間內(nèi)或可以忽略不計(jì)；③每臺(tái)機(jī)器前的等待隊(duì)列容量足夠大，以滿足重新排列工件加工順序的需要。相較于PFS問(wèn)題n!的解規(guī)模，NPFS問(wèn)題有最多高達(dá)(n!)max{m-2,1}種不同候選解，研究表明當(dāng)機(jī)器數(shù)m≥3時(shí)，NPFS為非確定性多項(xiàng)式(NP)難題。調(diào)度方案的生產(chǎn)周期(makespan)是所有工件最后一道工序完工時(shí)間的最大值。最小化Makespan的NPFS問(wèn)題較為常見，簡(jiǎn)記為Fm||Cmax[3]。

目前，在求解流水車間調(diào)度問(wèn)題的傳統(tǒng)方法中，精確算法受限于問(wèn)題的規(guī)模和性質(zhì)，而啟發(fā)式和元啟發(fā)式算法能在較短的時(shí)間獲得問(wèn)題的近優(yōu)解。針對(duì)Fm||Cmax問(wèn)題，Ying[4]提出一種迭代貪婪(Iterated Greedy，IG)算法，并分三階段運(yùn)用IG算法改進(jìn)各組機(jī)器上工件的置換加工順序;Fernandez等[5]提出一種打破捆綁的插入規(guī)則啟發(fā)式方法，與IG算法結(jié)合取得了很好的效果;Lin等[6]和Ying等[7]研究了基于禁忌搜索和模擬退火的混合方法和基于有向圖模型的蟻群優(yōu)化算法解決該問(wèn)題。然而，啟發(fā)式和元啟發(fā)式算法將調(diào)度過(guò)程視作靜態(tài)不可分割的整體，不能適應(yīng)復(fù)雜多變的實(shí)際生產(chǎn)環(huán)境。簡(jiǎn)單構(gòu)造啟發(fā)式(Simple Constructive Heuristic，SCH)根據(jù)確定的規(guī)則在每個(gè)調(diào)度決策時(shí)刻挑選工件加工，體現(xiàn)了調(diào)度問(wèn)題的實(shí)時(shí)性特點(diǎn)。大量研究發(fā)現(xiàn)，多種SCH優(yōu)先規(guī)則的線性或隨機(jī)組合更有優(yōu)勢(shì)。Panwalker等[8]依據(jù)性能指標(biāo)對(duì)113種不同分配規(guī)則進(jìn)行了歸納和總結(jié);Mouelhi等[9]研究表明，可以通過(guò)神經(jīng)網(wǎng)絡(luò)依據(jù)制造系統(tǒng)當(dāng)前狀態(tài)和車間操作環(huán)境參數(shù)，在有機(jī)器空閑時(shí)自動(dòng)化地選擇高效分配規(guī)則。強(qiáng)化學(xué)習(xí)算法可以產(chǎn)生適應(yīng)實(shí)際生產(chǎn)狀態(tài)的調(diào)度策略。Wei等[10]通過(guò)定義“生產(chǎn)壓力”特征值和兩步調(diào)度規(guī)則，將Q學(xué)習(xí)用于作業(yè)車間的組合分配規(guī)則選取，但該方法采用的表格型強(qiáng)化學(xué)習(xí)模型并不能描述實(shí)際復(fù)雜加工過(guò)程;Wang等[11]在解決單機(jī)調(diào)度問(wèn)題時(shí)應(yīng)用Q學(xué)習(xí)算法靈活選擇調(diào)度規(guī)則，優(yōu)化了Makespan等3個(gè)目標(biāo);文獻(xiàn)[12-13]研究了Q學(xué)習(xí)算法解決最小化誤工時(shí)間相關(guān)目標(biāo)的動(dòng)態(tài)隨機(jī)作業(yè)車間調(diào)度問(wèn)題;Miyashita[14]采用結(jié)合函數(shù)泛化器的時(shí)序差分(Temporal Difference，TD)法減少平均誤工時(shí)間和在制品數(shù)量的加權(quán)總和;張志聰?shù)萚15]給每臺(tái)機(jī)器定義15個(gè)狀態(tài)特征，利用TD法訓(xùn)練線性狀值函數(shù)泛化器求解NPFS問(wèn)題，但線性函數(shù)泛化器擬合和泛化能力有限;Wang等[16]將Q學(xué)習(xí)用于隨機(jī)經(jīng)濟(jì)批量實(shí)時(shí)調(diào)度問(wèn)題;Li等[17]用強(qiáng)化學(xué)習(xí)解決訂單式生產(chǎn)系統(tǒng)聯(lián)合定價(jià)、提前期確定和調(diào)度綜合決策問(wèn)題。

采用神經(jīng)網(wǎng)絡(luò)逼近強(qiáng)化學(xué)習(xí)值函數(shù)的方法源于上世紀(jì)90年代，由于常常出現(xiàn)不穩(wěn)定不收斂的情況，一直沒(méi)有太大突破。近年來(lái)，歸因于Google 的DeepMind公司在游戲和圍棋操控方面的研究，一種基于評(píng)價(jià)(critic)和決策(actor)機(jī)制的深度強(qiáng)化學(xué)習(xí)方法被提出并引起了廣泛關(guān)注，該方法結(jié)合了深度神經(jīng)網(wǎng)絡(luò)能夠利用歷史數(shù)據(jù)在線學(xué)習(xí)和強(qiáng)化學(xué)習(xí)依據(jù)狀態(tài)靈活選取對(duì)應(yīng)行為的優(yōu)點(diǎn)。Mnih等[18-19]在神經(jīng)學(xué)認(rèn)知基礎(chǔ)上，利用卷積神經(jīng)網(wǎng)絡(luò)擬合值函數(shù)，設(shè)置類似海馬體的經(jīng)驗(yàn)回放記憶體并獨(dú)立設(shè)置目標(biāo)網(wǎng)絡(luò)，使得提出的深度Q學(xué)習(xí)網(wǎng)絡(luò)(Deep Q-learning Network，DQN)算法在游戲操作學(xué)習(xí)的過(guò)程中超出人類專業(yè)玩家水平。

本文在DQN算法的基礎(chǔ)上，首次提出一種基于狀態(tài)值TD學(xué)習(xí)的深度強(qiáng)化學(xué)習(xí)算法，該算法保留了DQN的主要優(yōu)點(diǎn)，同時(shí)創(chuàng)新性地將異策略的Q學(xué)習(xí)替換為同策略的TD學(xué)習(xí)，這是因?yàn)椋孩僬{(diào)度問(wèn)題轉(zhuǎn)化為強(qiáng)化學(xué)習(xí)問(wèn)題后，行為空間屬于多維離散空間，不適合采用基于一維離散行為值函數(shù)的Q學(xué)習(xí)；②Q學(xué)習(xí)采用異策略，用最優(yōu)估計(jì)價(jià)值的行為替代交互時(shí)采取的行為，可能造成過(guò)高估計(jì)[20]。本文所提算法的模型與實(shí)際調(diào)度過(guò)程更接近，不但適用于計(jì)算復(fù)雜度更大的NPFS問(wèn)題，而且從原理上適合解決動(dòng)態(tài)調(diào)度問(wèn)題。

1 基本原理

1.1 強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)是一種機(jī)器學(xué)習(xí)算法[21]。強(qiáng)化學(xué)習(xí)算法無(wú)須知道狀態(tài)轉(zhuǎn)移概率矩陣，無(wú)須在迭代時(shí)掃描很多狀態(tài)，因此是解決序貫決策問(wèn)題包括馬爾科夫決策過(guò)程(Markov Decision Processes, MDP)和半馬爾科夫決策過(guò)程(Semi-Markov Decision Processes, SMDP)的有效方法。

1.1.1 馬爾科夫決策過(guò)程

馬爾科夫性是指系統(tǒng)的下一個(gè)狀態(tài)僅與當(dāng)前狀態(tài)有關(guān)，而與以前狀態(tài)無(wú)關(guān)的性質(zhì)。狀態(tài)轉(zhuǎn)移滿足馬爾科夫?qū)傩缘亩嚯A段決策問(wèn)題屬于MDP問(wèn)題。MDP可以用五元組來(lái)描述：

E={Z+,S,A(s),P,R}。

(1)

式中：智能體(Agent)處于環(huán)境E中，Z+={0,1,2,…}表示各個(gè)決策階段的集合；對(duì)于狀態(tài)空間S，每個(gè)狀態(tài)s∈S是環(huán)境狀態(tài)的描述；A表示行為空間，A(s)表示狀態(tài)為s(s∈S)時(shí)可以采取的行為的集合；P為狀態(tài)轉(zhuǎn)移概率函數(shù)，P(s,a,s′)和R(s,a,s′)分別表示狀態(tài)為s時(shí)采取行為a(a∈A(s))后狀態(tài)轉(zhuǎn)移到s′的概率和獲得的即時(shí)報(bào)酬。

(2)

式(2)描述了值函數(shù)的迭代形式及兩類值函數(shù)間的關(guān)系。最優(yōu)策略及其對(duì)應(yīng)的最優(yōu)值函數(shù)定義為

?s∈S:V*(s)=Vπ*(s)。

(3)

以最優(yōu)策略更新等式(2)得到最優(yōu)貝爾曼等式：

(4)

依據(jù)式(4)可以證明，在條件為?s∈S:Vπ(s)≤Qπ(s,π′(s))下將動(dòng)作改為π′(s)=argmaxaQπ(s,a)能夠使策略更好，對(duì)應(yīng)的值函數(shù)單調(diào)遞增。

1.1.2 策略迭代和值迭代

強(qiáng)化學(xué)習(xí)需要同時(shí)更新交織在一起的策略與價(jià)值。觀察貝爾曼等式，可以將問(wèn)題視作不斷迭代優(yōu)化的過(guò)程，思路如下[20]：

(1)以某種初始策略π開始，對(duì)?s∈S計(jì)算當(dāng)前策略π對(duì)應(yīng)的值函數(shù)Vπ(s)；

(2)利用這個(gè)值函數(shù)，找到更好的策略π′；

(3)利用更優(yōu)的策略繼續(xù)更新值函數(shù)，得到Vπ′(s)；

(4)不斷重復(fù)步驟(2)和步驟(3)，直至π與π′一致。

經(jīng)過(guò)若干輪這樣的迭代，當(dāng)前策略會(huì)逐步收斂到最優(yōu)策略。這種解決問(wèn)題的思路形成的算法稱為策略迭代算法。

實(shí)際上，值函數(shù)迭代和策略更新可以同步進(jìn)行。由于存在最優(yōu)策略，對(duì)于每個(gè)狀態(tài)，最優(yōu)策略采取的行為不會(huì)比其他行為差。由此可以得到狀態(tài)值函數(shù)的更新方法：V(s)←maxaQ(s,a)，即

(5)

1.1.3 評(píng)估狀態(tài)值的TD價(jià)值迭代算法

TD法結(jié)合蒙特卡羅和動(dòng)態(tài)規(guī)劃方法，采用經(jīng)典貝爾曼公式進(jìn)行迭代，直至值函數(shù)收斂?；镜饺缦拢?/p>

V(st)←V(st)+α[rt+1+γV(st+1)-V(st)]。

(6)

式中：rt+1+γV(st+1)為TD目標(biāo);δt=rt+1+γV(st+1)-V(st)為TD偏差;α為步長(zhǎng)或?qū)W習(xí)率。迭代公式(6)是有模型強(qiáng)化學(xué)習(xí)公式的精簡(jiǎn)和變形，適用于無(wú)模型的強(qiáng)化學(xué)習(xí)。算法流程如表1所示。

表1 評(píng)估狀態(tài)值的TD算法

1.2 深度學(xué)習(xí)

1.2.1 深度神經(jīng)網(wǎng)絡(luò)

深度學(xué)習(xí)是在人工神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)上發(fā)展而來(lái)的一種表示學(xué)習(xí)，其主要模型是深度神經(jīng)網(wǎng)絡(luò)[23]神經(jīng)元和人工神經(jīng)網(wǎng)絡(luò)模型(如圖1)。深層神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)具有更大的容量和指數(shù)級(jí)的表達(dá)空間，使得模型能夠處理非線性數(shù)據(jù)，從而有更強(qiáng)的學(xué)習(xí)能力。

深度學(xué)習(xí)在近期的成功主要依賴于海量的訓(xùn)練數(shù)據(jù)、非常靈活的模型、足夠的運(yùn)算能力和足夠?qū)咕S數(shù)災(zāi)難的先驗(yàn)經(jīng)驗(yàn)。LeCun等[24]提出一種預(yù)訓(xùn)練與微調(diào)相結(jié)合的技術(shù)，大幅減少了訓(xùn)練多層神經(jīng)網(wǎng)絡(luò)的時(shí)間，各種優(yōu)化技術(shù)的出現(xiàn)，如單側(cè)抑制的Relu激活函數(shù)，使得梯度消失問(wèn)題進(jìn)一步緩解。同時(shí)深度殘差[25]的技術(shù)應(yīng)用可以使網(wǎng)絡(luò)層數(shù)的堆疊達(dá)到百層以上。

1.2.2 激活函數(shù)

激活函數(shù)(activation function)是神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)的一個(gè)核心單元，激活函數(shù)賦予神經(jīng)元自我學(xué)習(xí)和適應(yīng)的能力[26]。激活函數(shù)在神經(jīng)網(wǎng)絡(luò)中引入了非線性學(xué)習(xí)處理能力，使得模型能處理非線性數(shù)據(jù)。常用的激活函數(shù)包括階躍函數(shù)、sigmoid函數(shù)、tanh函數(shù)和近似生物神經(jīng)元的激活函數(shù)如Relu、Leaky-Relu及softplus等。由于近似生物神經(jīng)元的激活函數(shù)在絕大多數(shù)網(wǎng)絡(luò)和應(yīng)用中比傳統(tǒng)函數(shù)好，本文采用Relu激活函數(shù)。

1.2.3 優(yōu)化算法

目標(biāo)函數(shù)的優(yōu)化是神經(jīng)網(wǎng)絡(luò)訓(xùn)練中的核心問(wèn)題之一。研究應(yīng)用中除了常用的隨機(jī)梯度下降(Stochastic Gradient Descent, SGD)以外還相繼出現(xiàn)了動(dòng)量?jī)?yōu)化算法(Momentum)、RMSProp和Adam算法。這些算法策略不僅加快了求解速度，還降低了超參數(shù)(如學(xué)習(xí)率)對(duì)求解過(guò)程的影響，簡(jiǎn)化了求解過(guò)程。考慮到內(nèi)存消耗和學(xué)習(xí)率，在深度學(xué)習(xí)領(lǐng)域提及的目標(biāo)優(yōu)化方法一般是指支持?jǐn)?shù)據(jù)集分塊，并按照分塊單元數(shù)據(jù)包(mini-batch)訓(xùn)練的優(yōu)化算法。

2 深度強(qiáng)化學(xué)習(xí)方法

2.1 調(diào)度問(wèn)題的轉(zhuǎn)化

將強(qiáng)化學(xué)習(xí)應(yīng)用于調(diào)度領(lǐng)域的關(guān)鍵問(wèn)題和難點(diǎn)是將調(diào)度問(wèn)題轉(zhuǎn)化為一個(gè)SMDP問(wèn)題。首要問(wèn)題是定義系統(tǒng)各個(gè)時(shí)刻的狀態(tài)特征。

2.1.1狀態(tài)特征

狀態(tài)特征和可選行為的定義與調(diào)度問(wèn)題特征緊密相關(guān)。一般而言，遵循以下原則[15]：

(1)狀態(tài)特征能夠描述調(diào)度環(huán)境的主要特點(diǎn)和變化，包括系統(tǒng)全局特征和局部特征。

(2)所有問(wèn)題的所有狀態(tài)通過(guò)一個(gè)通用特征集來(lái)表示。

(3)狀態(tài)可以通過(guò)狀態(tài)特征來(lái)表示和概括各種不同調(diào)度問(wèn)題。

(4)狀態(tài)特征是一種對(duì)狀態(tài)變量的數(shù)值表征。

(5)特征應(yīng)易于計(jì)算。正規(guī)化特征因?yàn)榭梢杂孟鄬?duì)統(tǒng)一的尺度描述不同問(wèn)題而被優(yōu)先考慮。

流水車間中第i臺(tái)機(jī)器Mi的第k個(gè)特征記作fi,k。對(duì)于機(jī)器Mi(1≤i

表2 狀態(tài)特征列表

即使一些特征可能冗余，采用多種特征可以讓機(jī)器學(xué)習(xí)效率更優(yōu)。一些特征也可以作為是否觸發(fā)相應(yīng)行動(dòng)或工作的指示。狀態(tài)特征1描述了不同機(jī)器上的工件數(shù)量的分布；狀態(tài)特征2描述了當(dāng)前分配在各機(jī)器上的工作負(fù)荷；狀態(tài)特征3描述了各機(jī)器從當(dāng)前狀態(tài)開始須要完成的總工作負(fù)荷；狀態(tài)特征4、5描述了當(dāng)前在各個(gè)等待隊(duì)列中工件的最長(zhǎng)或最短加工時(shí)間；狀態(tài)特征6表示正在加工作業(yè)的剩余加工時(shí)間，進(jìn)而表征機(jī)器的忙/閑狀態(tài)；狀態(tài)特征7、8表示機(jī)器上等待加工工件的最長(zhǎng)或最短剩余加工時(shí)間；狀態(tài)特征9、10描述工件在某機(jī)器上加工時(shí)間與其在下一臺(tái)機(jī)器上的加工時(shí)間的比值情況；狀態(tài)特征11～14決定機(jī)器是否應(yīng)該采用Johnson-Bellman規(guī)則定義的行為；狀態(tài)15決定即使有作業(yè)等待加工時(shí)，是否應(yīng)該讓機(jī)器保持空閑。所有特征一起提供了某狀態(tài)下的機(jī)器和工件信息。智能體感知加工狀態(tài)特征的深度神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示。

2.1.2 啟發(fā)式行為

可以選取SCH給每臺(tái)機(jī)器定義候選行為集，其中優(yōu)先分配規(guī)則用于強(qiáng)化學(xué)習(xí)可以克服短視的天性。與狀態(tài)相關(guān)或無(wú)關(guān)的行為都應(yīng)該被采納，以充分利用現(xiàn)有調(diào)度規(guī)則理論和智能體從經(jīng)驗(yàn)中學(xué)習(xí)的能力。本文選取了最小化生產(chǎn)周期目標(biāo)問(wèn)題中常用的28種行為，如表3所示。

表3 每臺(tái)機(jī)器候選行為集

續(xù)表3

機(jī)器Mm-1能夠采取的行為集合是{a(k)|1≤k≤3，5≤k≤28}，機(jī)器Mm能夠采取的行為集合是{a(k)|k={1，28}，5≤k≤16}，其他機(jī)器Mi(1≤i≤m-3)上沒(méi)有行為限制。

2.1.3 報(bào)酬函數(shù)

報(bào)酬函數(shù)的選擇依據(jù)以下規(guī)則：①反映行為的即時(shí)影響，與行為的即時(shí)報(bào)酬聯(lián)系密切；②累積的總報(bào)酬反映目標(biāo)函數(shù)值；③報(bào)酬函數(shù)能夠應(yīng)用于不同規(guī)模的問(wèn)題。由于優(yōu)化目標(biāo)是最小化生產(chǎn)周期，智能體能夠在周期更短的調(diào)度中獲得更大回報(bào)。

注意到生產(chǎn)周期與機(jī)器利用率緊密相關(guān)。定義δi(t)為機(jī)器的忙閑狀態(tài)指示函數(shù)為：

(7)

報(bào)酬函數(shù)定義為：

(8)

式中：m為機(jī)器數(shù);rk表示系統(tǒng)在決策時(shí)刻tk-1執(zhí)行行為后轉(zhuǎn)移到tk時(shí)刻狀態(tài)獲得的報(bào)酬。顯然rk等于時(shí)間間隔[tk-1，tk]平均每臺(tái)機(jī)器空閑時(shí)間的相反數(shù)。可以證明最小化生產(chǎn)周期等價(jià)于從一條交互軌跡序列中最大化獲得的累積回報(bào)R。證明如下：

(9)

式中Ti表示第i臺(tái)機(jī)器在加工過(guò)程中的總空閑時(shí)間。由式(9)可知，生產(chǎn)周期越小，總回報(bào)越大。

2.2 深度時(shí)序差分強(qiáng)化學(xué)習(xí)算法

2.2.1 探索與利用

探索指在單步?jīng)Q策中，不局限于當(dāng)前最優(yōu)行為，也嘗試其他可能獲得較高行為值的行為；利用指采用當(dāng)前已知的最優(yōu)策略，獲取最大回報(bào)。為了平衡智能體在單步環(huán)境交互過(guò)程中的探索與利用的分配，采用ε-貪心策略，即以ε概率隨機(jī)選取候選行為，以1-ε概率選擇當(dāng)前已知最好行為。將狀態(tài)s下采取組合行為a的概率記作p(s,a)，可得：

(10)

式中：|A(s)|為狀態(tài)s下候選的組合行為集合的大小;a*(s)為相應(yīng)狀態(tài)下的貪婪行為，

(11)

2.2.2算法框架

本文提出一種深度時(shí)序差分強(qiáng)化學(xué)習(xí)(Deep Temporal Difference Network, DTDN)算法，算法框架如表4所示。

表4 基于狀態(tài)值的時(shí)序差分強(qiáng)化學(xué)習(xí)算法

2.2.3 算法模型和實(shí)施

為簡(jiǎn)化起見，以規(guī)模為m=3，n=4的流水車間可視化說(shuō)明算法實(shí)施過(guò)程。如圖3所示，圓形表示機(jī)器，三角形表示工件，矩形表示容量足夠大的等待隊(duì)列。

在開始加工時(shí)刻，調(diào)度系統(tǒng)處于初始狀態(tài)s0，此時(shí)所有工件位于第一個(gè)等候隊(duì)列Q1，且所有機(jī)器處于空閑狀態(tài)。然后第一臺(tái)機(jī)器選擇一個(gè)動(dòng)作a(k)(1≤k≤27)，即選擇隊(duì)列Q1中某個(gè)工件加工。之后每當(dāng)任意一臺(tái)機(jī)器完成了一道工序的加工，系統(tǒng)轉(zhuǎn)移到一個(gè)新的狀態(tài)st,該狀態(tài)下每臺(tái)機(jī)器選擇一個(gè)行為執(zhí)行。當(dāng)又有某一道工序完成時(shí)，系統(tǒng)轉(zhuǎn)移到下一個(gè)狀態(tài)st+1，智能體獲得一次回報(bào)rt+1，rt+1可以通過(guò)兩個(gè)狀態(tài)之間的時(shí)間間隔計(jì)算。由于每個(gè)決策時(shí)刻，每個(gè)機(jī)器同時(shí)選擇一個(gè)行為執(zhí)行，實(shí)際上系統(tǒng)在狀態(tài)st實(shí)施了一次由m個(gè)子行為組合而成的多維行為at+1=(a1,a2,…,am)。當(dāng)系統(tǒng)到達(dá)終止?fàn)顟B(tài)sT時(shí)，意味著所有隊(duì)列全為空，且所有工件全部加工完成，即獲得一個(gè)調(diào)度方案。

DQN網(wǎng)絡(luò)輸出層用若干個(gè)節(jié)點(diǎn)對(duì)應(yīng)有限個(gè)離散行為值，不能涵蓋指數(shù)級(jí)的多維行為空間，并且異策略的Q學(xué)習(xí)在評(píng)價(jià)行為值時(shí)用最優(yōu)值替代實(shí)際交互值造成過(guò)高估計(jì)，因此該方法不能直接適用于多維行為空間NPFS問(wèn)題。本文提出采用同策略的TD學(xué)習(xí)代替Q學(xué)習(xí)，基于狀態(tài)值間接計(jì)算行為值，適用于選取多維行為且緩解了值函數(shù)過(guò)高估計(jì)問(wèn)題。二者不同之處體現(xiàn)在網(wǎng)絡(luò)結(jié)構(gòu)和其擬合的價(jià)值函數(shù)兩方面，如圖4所示。

DTDN算法的實(shí)施流程圖如圖5所示。實(shí)施過(guò)程主要包括兩層循環(huán)：外層循環(huán)對(duì)應(yīng)于圖3中的加工周期(episode)，內(nèi)層循環(huán)對(duì)應(yīng)于圖3中每一步狀態(tài)轉(zhuǎn)移(step)。

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

3.1 標(biāo)準(zhǔn)測(cè)試集和實(shí)驗(yàn)平臺(tái)

為了評(píng)估本文所提算法的有效性，分別在小規(guī)模和大規(guī)模問(wèn)題上驗(yàn)證算法。小規(guī)模問(wèn)題來(lái)自文獻(xiàn)[28]，大規(guī)模問(wèn)題采用Demirkol 等[29]建立的標(biāo)準(zhǔn)測(cè)試調(diào)度問(wèn)題集，測(cè)試集包含600個(gè)隨機(jī)產(chǎn)生的6個(gè)基本車間調(diào)度問(wèn)題的實(shí)例。本文采用的是對(duì)應(yīng)于Fm||Cmax問(wèn)題的40個(gè)測(cè)試實(shí)例。所有作業(yè)在0時(shí)刻釋放，加工時(shí)間服從1～200的離散均勻分布。測(cè)試實(shí)例規(guī)模是2類機(jī)器數(shù)目(m=15,20)和4類工件數(shù)目(n=20,30,40,50)的8個(gè)組合，總工序數(shù)目分布在300～1 000之間，n和m的比值介于1～3.3。由m和n的每個(gè)組合生成10個(gè)實(shí)例。

鑒于問(wèn)題的規(guī)模和復(fù)雜性，實(shí)例無(wú)法求得精確解。文獻(xiàn)[29]使用5個(gè)不同構(gòu)建型啟發(fā)式和3個(gè)版本的轉(zhuǎn)移瓶頸工序啟發(fā)式算法求解每個(gè)實(shí)例。所有算法在一臺(tái)50 MHz處理器的SUN SPARC服務(wù)器多任務(wù)Unix操作系統(tǒng)上運(yùn)行。每個(gè)實(shí)例的上界(UB)是算法發(fā)現(xiàn)的最優(yōu)解，下界(LB)通過(guò)松弛容量約束條件等方法獲得。為獲得更緊湊和具有挑戰(zhàn)性的測(cè)試集，文獻(xiàn)[29]依據(jù)實(shí)例上下界間的百分距離將每個(gè)m和n的組合降序排列，只公布每個(gè)組合的前5個(gè)實(shí)例。因此，共獲得40個(gè)Fm‖Cmax問(wèn)題測(cè)試實(shí)例，每個(gè)實(shí)例以flcmax_n_m_Instance-Number標(biāo)識(shí)。

用Python語(yǔ)言在Visual Studio Code上編碼所提算法，于2.3 GHz Intel i5 處理器Linux操作系統(tǒng)PC平臺(tái)運(yùn)行。強(qiáng)化學(xué)習(xí)平臺(tái)OpenAI Gym以框架形式規(guī)范了環(huán)境(Env)類的主要成員方法，包括構(gòu)造(init)、重置(reset)、執(zhí)行(step)、繪圖(render)和結(jié)束(close)；執(zhí)行算法的智能體與環(huán)境進(jìn)行交互迭代；智能體深度神經(jīng)網(wǎng)絡(luò)模型利用后端TensorFlow實(shí)現(xiàn)。

參數(shù)選擇可能影響求解質(zhì)量，有一般性原則可以遵循。折扣因子γ衡量后續(xù)狀態(tài)值對(duì)總回報(bào)的權(quán)重，因此一般取值接近1，設(shè)γ=0.95；為便于在迭代初始階段充分探索策略空間，結(jié)束階段利用最優(yōu)策略，ε-貪心策略中設(shè)置初始ε=1，并以0.995的折扣率指數(shù)衰減；設(shè)學(xué)習(xí)率α=5×10-4，最大交互次數(shù)MAX_EPISODE=800，記憶體D容量N=6 000，采樣批量BATCH_SIZE=64；智能體深度神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)如圖2b所示，網(wǎng)絡(luò)參數(shù)采取隨機(jī)初始化策略。

3.2 實(shí)驗(yàn)結(jié)果及分析

(1)小規(guī)模問(wèn)題

以文獻(xiàn)[28]中兩個(gè)小規(guī)模測(cè)試實(shí)例說(shuō)明采用DTDN算法進(jìn)行調(diào)度決策的過(guò)程。兩個(gè)問(wèn)題的加工數(shù)據(jù)分別為：

(12)

對(duì)于式(12)問(wèn)題1，DTDN與部分常見啟發(fā)式算法求得的最優(yōu)解如表5所示，可見該算法相比啟發(fā)式算法能獲得較優(yōu)解，表中用黑體數(shù)字表示。其對(duì)應(yīng)甘特圖如圖6所示，圖6中豎直虛線表示狀態(tài)轉(zhuǎn)移分隔線，代表調(diào)度決策時(shí)間點(diǎn)。

表5 問(wèn)題1測(cè)試結(jié)果對(duì)比表

NEH是當(dāng)前解決Fm|prmu|Cmax問(wèn)題最有效的啟發(fā)式算法之一。DTDN算法和NEH及其改進(jìn)算法NEH_KK在問(wèn)題2上的測(cè)試對(duì)比結(jié)果如表6所示。DTDN算法得到的工件置換加工順序?yàn)閧1,3,5,4,6,2}，最優(yōu)解相較于NEH和NEH_KK算法效率分別提升了4.5%和3.0%。

表6 問(wèn)題2測(cè)試結(jié)果對(duì)比表

(2)大規(guī)模問(wèn)題

本算法實(shí)驗(yàn)計(jì)算結(jié)果和兩種SCH分配規(guī)則及文獻(xiàn)[7]中蟻群算法(Ant Colony System，ACS)對(duì)比情況如表7所示。蟻群算法采用常量啟發(fā)式期望(Constant Heuristic Desirability，CHD)策略，利用多階段無(wú)環(huán)有向圖模型，蟻群從模型初始節(jié)點(diǎn)到終止節(jié)點(diǎn)的一次遍歷即為一次調(diào)度過(guò)程。

表7 實(shí)驗(yàn)結(jié)果對(duì)比

續(xù)表7

由表7可知，相較于SCH和CHD-ACS算法，本文提出的深度強(qiáng)化學(xué)習(xí)算法可以獲得較優(yōu)的解，部分解已經(jīng)低于原實(shí)例的上界；由于算法采用框架性平臺(tái)和解釋性語(yǔ)言Python編寫，因此算法時(shí)間對(duì)比沒(méi)有在表7中列出，深度神經(jīng)網(wǎng)絡(luò)的訓(xùn)練過(guò)程需要一定時(shí)間，但訓(xùn)練好的網(wǎng)絡(luò)可以針對(duì)調(diào)度問(wèn)題實(shí)例在極短時(shí)間內(nèi)輸出較優(yōu)策略。值得指出的是，相較于ACS算法10 000次以上的迭代過(guò)程，本算法在800代以內(nèi)即可得到較優(yōu)解。如圖7所示為實(shí)例flcmax_20_15_6所求最優(yōu)策略得到的甘特圖。

如圖8所示為實(shí)例flcmax_20_15_6生產(chǎn)周期隨著迭代次數(shù)變化。由圖8可知，生產(chǎn)周期隨迭代過(guò)程顯著減小，在800代以內(nèi)達(dá)到較優(yōu)值。

為了分析在實(shí)驗(yàn)所有實(shí)例所得最優(yōu)策略中各個(gè)行為的利用率，得到如圖9所示的啟發(fā)式行為使用頻數(shù)分布圖。

由圖9可以看出，使用次數(shù)超過(guò)150次的行為分別是Jonhson1，Jonshon2，SPT，LPT，SRM，LRM，SSO，LSO，SPT+SSO。這些行為對(duì)獲得最優(yōu)解有較大貢獻(xiàn)度，因此也具有較大利用價(jià)值；其他行為頻數(shù)分布相對(duì)比較均勻，表現(xiàn)并不突出。因此，可以考慮增添其他構(gòu)建啟發(fā)式行為到候選行為空間，淘汰一些利用率低的行為，從而精簡(jiǎn)行為集合。

4 結(jié)束語(yǔ)

本文將深度強(qiáng)化學(xué)習(xí)算法DQN中的Q學(xué)習(xí)轉(zhuǎn)變?yōu)榛跔顟B(tài)值的時(shí)序差分TD學(xué)習(xí)，由此得到深度時(shí)序差分強(qiáng)化學(xué)習(xí)(DTDN)算法并將其順利地應(yīng)用于車間調(diào)度問(wèn)題。

實(shí)驗(yàn)表明，所提算法相較于簡(jiǎn)單構(gòu)建啟發(fā)式或群體智能算法，能夠在更小的迭代次數(shù)內(nèi)獲得較優(yōu)解。因?yàn)橐肓藸顟B(tài)特征、啟發(fā)式行為和深度神經(jīng)網(wǎng)絡(luò)，且采用基于半馬爾可夫決策過(guò)程(SMPD)的強(qiáng)化學(xué)習(xí)，所以算法具有較高的靈活性和動(dòng)態(tài)性。所提算法具有以下優(yōu)點(diǎn)：

(1)具備學(xué)習(xí)能力，實(shí)時(shí)性較強(qiáng)。由于通過(guò)輸入狀態(tài)到神經(jīng)網(wǎng)絡(luò)已選擇依據(jù)規(guī)則的SCH算法，當(dāng)神經(jīng)網(wǎng)絡(luò)訓(xùn)練成熟后，以往的經(jīng)驗(yàn)?zāi)Ｊ酱鎯?chǔ)在網(wǎng)絡(luò)參數(shù)中，可以實(shí)時(shí)做出調(diào)度決策。

(2)算法模型較為靈活。狀態(tài)特征、行為規(guī)則以及神經(jīng)網(wǎng)絡(luò)規(guī)模都可以依據(jù)需要進(jìn)行靈活增刪取舍。構(gòu)造式過(guò)程與實(shí)際調(diào)度更接近，不但適用于計(jì)算復(fù)雜度更大的NPFS問(wèn)題，而且從原理上適合解決動(dòng)態(tài)調(diào)度問(wèn)題。

(3)發(fā)展?jié)摿^大。在深度神經(jīng)網(wǎng)絡(luò)理論不斷進(jìn)步和計(jì)算機(jī)運(yùn)算能力不斷提升的當(dāng)下有很大的發(fā)展空間。

進(jìn)一步研究工作可以從以下幾方面考慮：

(1)算法模型方面。增減狀態(tài)特征，使其在最小冗余的情況下更好描述加工狀態(tài)；尋求更加頻繁高效使用的啟發(fā)式行為以及擬合、泛化能力更強(qiáng)的值函數(shù)泛化器結(jié)構(gòu)；增減候選行為集合，可以考慮適當(dāng)添加更多利用率高的構(gòu)建啟發(fā)式行為。

(2)算法流程方面。實(shí)際上DQN算法本身在提出之后便相繼出現(xiàn)了許多改進(jìn)類型，比如針對(duì)記憶體采樣優(yōu)先級(jí)的帶有優(yōu)先回放記憶體的DQN算法，可以提高算法迭代效率。

(3)算法應(yīng)用方面。可以將算法拓展應(yīng)用于復(fù)雜性更高的作業(yè)車間調(diào)度問(wèn)題以及其他動(dòng)態(tài)調(diào)度問(wèn)題。