深度強(qiáng)化學(xué)習(xí)算法求解作業(yè)車間調(diào)度問題

李寶帥，葉春明

上海理工大學(xué) 管理學(xué)院，上海 200093

作業(yè)車間調(diào)度問題是常見的調(diào)度問題之一，其目標(biāo)是在一定約束條件下對(duì)工件和機(jī)器按時(shí)間進(jìn)行分配并安排加工次序，使得加工性能指標(biāo)達(dá)到最優(yōu)。針對(duì)作業(yè)車間調(diào)度問題的求解，有精確算法與近似求解算法可用于求解。精確算法如分支定界法、線性規(guī)劃法等，但其局限性是在大規(guī)模調(diào)度問題上無法適用。近似求解算法可分為啟發(fā)式算法與元啟發(fā)式算法，可在短時(shí)間內(nèi)獲得調(diào)度問題的較優(yōu)解。張騰飛等[1]利用改變初始解的生成方式、對(duì)染色體進(jìn)行分段編碼以及使用交叉算子等措施對(duì)遺傳算法進(jìn)行改進(jìn)，并在標(biāo)準(zhǔn)算例上驗(yàn)證了改進(jìn)遺傳算法在柔性車間調(diào)度問題上的高效性；劉洪銘等[2]通過對(duì)粒子群算法中慣性系數(shù)、參數(shù)因子以及初始群生成方式進(jìn)行改進(jìn)，求解以機(jī)器加工時(shí)間最短為目標(biāo)的車間調(diào)度問題。啟發(fā)式方法，即調(diào)度規(guī)則也適用于解決調(diào)度問題，Panwalkar等[3]對(duì)調(diào)度規(guī)則進(jìn)行了研究，系統(tǒng)總結(jié)了共113種調(diào)度規(guī)則，并對(duì)每條調(diào)度規(guī)則進(jìn)行了相應(yīng)描述；Mouelhi-Chibani等[4]利用小規(guī)模問題訓(xùn)練神經(jīng)網(wǎng)絡(luò)，根據(jù)系統(tǒng)狀態(tài)實(shí)時(shí)選擇兩種調(diào)度規(guī)則進(jìn)行調(diào)度，實(shí)驗(yàn)結(jié)果證明優(yōu)于單一靜態(tài)的調(diào)度規(guī)則選取方法。

強(qiáng)化學(xué)習(xí)算法擁有自決策的特點(diǎn)，可根據(jù)生產(chǎn)狀態(tài)進(jìn)行策略調(diào)整。Riedmiller等[5]首先利用強(qiáng)化學(xué)習(xí)對(duì)車間調(diào)度問題進(jìn)行研究，利用強(qiáng)化學(xué)習(xí)方法，每個(gè)智能體對(duì)應(yīng)每個(gè)機(jī)器，使用Q-learning算法學(xué)習(xí)車間中的調(diào)度策略以減少總拖延時(shí)間，在單一案例和多重案例上驗(yàn)證了算法有效性和泛化性；Aydin等[6]提出一種基于強(qiáng)化學(xué)習(xí)的動(dòng)態(tài)調(diào)度系統(tǒng)，通過改進(jìn)Q-learning算法，訓(xùn)練智能體根據(jù)車間狀態(tài)變化選擇當(dāng)前最優(yōu)的調(diào)度規(guī)則，在仿真系統(tǒng)中與單一調(diào)度規(guī)則進(jìn)行對(duì)比，體現(xiàn)了算法優(yōu)越性；Wang等[7]針對(duì)車間調(diào)度問題，利用Q-learning訓(xùn)練一個(gè)單機(jī)調(diào)度系統(tǒng)，選擇三個(gè)調(diào)度規(guī)則來最小平均延誤時(shí)間；Wang[8]基于強(qiáng)化學(xué)習(xí)方法，提出一種聚類與自適應(yīng)調(diào)度策略的加權(quán)Q-learning來解決動(dòng)態(tài)調(diào)度問題；張東陽等[9]針對(duì)置換流水車間調(diào)度問題，利用Q-learning算法引入狀態(tài)變量與動(dòng)作變量，將調(diào)度問題映射到強(qiáng)化學(xué)習(xí)問題中，算法在標(biāo)準(zhǔn)算例上表現(xiàn)優(yōu)異。

但長(zhǎng)期以來，強(qiáng)化學(xué)習(xí)的應(yīng)用受限于問題規(guī)模解決問題本質(zhì)上的低維度性，無法解決大規(guī)模問題與高維度問題，深度神經(jīng)網(wǎng)絡(luò)的融入解決了這一難題。Mnih等[10-11]提出了深度Q網(wǎng)絡(luò)（Deep Q Network，DQN），使用神經(jīng)網(wǎng)絡(luò)擬合值函數(shù)，設(shè)置獨(dú)立的目標(biāo)網(wǎng)絡(luò)以及經(jīng)驗(yàn)回放機(jī)制，用于多款游戲的訓(xùn)練，并在多個(gè)游戲中擊敗了專業(yè)人類玩家。此后深度強(qiáng)化學(xué)習(xí)算法快速發(fā)展，同樣應(yīng)用于車間調(diào)度領(lǐng)域，肖鵬飛等[12]利用改進(jìn)的DQN算法，通過定義狀態(tài)空間、動(dòng)作空間和獎(jiǎng)懲函數(shù)，把調(diào)度問題轉(zhuǎn)換為多階段決策問題，將機(jī)器實(shí)時(shí)加工狀態(tài)作為數(shù)據(jù)特征作為輸入，輸出最優(yōu)生產(chǎn)周期對(duì)應(yīng)的調(diào)度規(guī)則組合，解決以最大完成時(shí)間為目標(biāo)的非置換流水車間調(diào)度問題，在標(biāo)準(zhǔn)問題上驗(yàn)證了有效性；Liu等[13]提出一種異步更新和深度確定性策略梯度（Deep Deterministic Policy Gradient，DDPG）的并行算法解決作業(yè)車間調(diào)度問題，采用多個(gè)智能體，將狀態(tài)空間表示為三矩陣形式，設(shè)置調(diào)度規(guī)則集為動(dòng)作空間，對(duì)調(diào)度問題進(jìn)行了轉(zhuǎn)換與研究；Luo[14]利用深度雙Q網(wǎng)絡(luò)[15]（Double DQN）算法研究了柔性車間調(diào)度問題，將柔性車間調(diào)度問題視為馬爾可夫決策過程，設(shè)計(jì)七個(gè)狀態(tài)特征表示生產(chǎn)狀態(tài)，提出了六種復(fù)合調(diào)度規(guī)則作為動(dòng)作空間，與Q-learning算法、多個(gè)調(diào)度規(guī)則在實(shí)例問題上進(jìn)行對(duì)比，體現(xiàn)了算法的優(yōu)越性與通用性；Yang等[16]利用DQN及DDQN算法以總延誤為目標(biāo)，研究了新作業(yè)到達(dá)下的動(dòng)態(tài)置換流水作業(yè)調(diào)度問題，分別設(shè)計(jì)五種狀態(tài)特征作為狀態(tài)空間，五個(gè)調(diào)度規(guī)則作為動(dòng)作空間，與元啟發(fā)式算法在調(diào)度問題上進(jìn)行對(duì)比，驗(yàn)證了算法的優(yōu)越性。

綜上所述，已有將DQN及其變體應(yīng)用于調(diào)度問題的研究，本文利用DQN的改進(jìn)版本，即DDQN與競(jìng)爭(zhēng)網(wǎng)絡(luò)架構(gòu)的DQN算法[17]（Dueling DQN）結(jié)合而成的D3QN（Double Deep Q-Learning Network with Dueling Architecture）解決作業(yè)車間調(diào)度問題。D3QN算法對(duì)DQN進(jìn)行改進(jìn)，算法使用兩個(gè)Q網(wǎng)絡(luò)進(jìn)行學(xué)習(xí)，實(shí)現(xiàn)動(dòng)作選擇與動(dòng)作狀態(tài)值函數(shù)的解耦，解決了DQN過高的值函數(shù)估計(jì)[18]，并且利用競(jìng)爭(zhēng)網(wǎng)絡(luò)模型代替DQN算法中的網(wǎng)絡(luò)模型，可以解決獎(jiǎng)勵(lì)偏見問題，學(xué)習(xí)到更真實(shí)的價(jià)值函數(shù)。本文創(chuàng)新點(diǎn)在于通過定義狀態(tài)空間、動(dòng)作空間和獎(jiǎng)懲函數(shù)將調(diào)度問題轉(zhuǎn)化為一系列序列決策過程，利用D3QN算法對(duì)車間調(diào)度問題進(jìn)行研究。在標(biāo)準(zhǔn)算例上與智能優(yōu)化算法的實(shí)驗(yàn)結(jié)果對(duì)比驗(yàn)證了算法的有效性，同時(shí)算法原理上基于神經(jīng)網(wǎng)絡(luò)與強(qiáng)化學(xué)習(xí)，也適用于解決動(dòng)態(tài)調(diào)度問題。

1 基本原理

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

強(qiáng)化學(xué)習(xí)（Reinforcement Learning，RL）是機(jī)器學(xué)習(xí)的重要分支之一[19]。RL的本質(zhì)是互動(dòng)學(xué)習(xí)，目標(biāo)是使智能體在與環(huán)境的交互過程中獲得最大的累計(jì)獎(jiǎng)勵(lì)值，從而學(xué)得對(duì)自身動(dòng)作的最優(yōu)控制。RL的數(shù)學(xué)基礎(chǔ)理論基于馬爾可夫決策過程（Markov Decision Processes，MDP）。

1.1.1 馬爾可夫決策過程

馬爾可夫性質(zhì)（Markov Property）指的是系統(tǒng)的下一個(gè)狀態(tài)只與目前狀態(tài)有關(guān)，而與之前的所有狀態(tài)都不相關(guān)。如果一個(gè)系統(tǒng)具有馬爾可夫性質(zhì)，則可根據(jù)當(dāng)前狀態(tài)與動(dòng)作預(yù)測(cè)未來狀態(tài)和獎(jiǎng)勵(lì)[20]，馬爾可夫性質(zhì)使得馬爾可夫決策過程易于表示，滿足馬爾可夫性質(zhì)的RL任務(wù)稱為MDP[21]，具體而言，一個(gè)馬爾可夫決策過程可由一個(gè)四元組組成，即MDP=(S,A,Psa,R)。S為狀態(tài)空間集合，A為動(dòng)作空間集合，Psa為狀態(tài)轉(zhuǎn)移概率，表示在當(dāng)前狀態(tài)下執(zhí)行動(dòng)作后轉(zhuǎn)移到另一個(gè)狀態(tài)的概率，R為獎(jiǎng)勵(lì)函數(shù)。

1.1.2 強(qiáng)化學(xué)習(xí)求解

在RL中，智能體從環(huán)境中不斷采樣，最終目標(biāo)是學(xué)習(xí)到一個(gè)最優(yōu)動(dòng)作策略π*，即在任意時(shí)間步中執(zhí)行動(dòng)作a所得到的累計(jì)獎(jiǎng)勵(lì)R最大。在實(shí)際應(yīng)用中，通常用折扣未來獎(jiǎng)勵(lì)累計(jì)獎(jiǎng)勵(lì)G1來表示時(shí)間步t內(nèi)的未來累計(jì)獎(jiǎng)勵(lì)，即：

其中γ是折扣因子。狀態(tài)值函數(shù)v(s)是表示在狀態(tài)s下執(zhí)行動(dòng)作a得到的獎(jiǎng)勵(lì)期望：

動(dòng)作值函數(shù)q(s,a)是評(píng)估當(dāng)前智能體在狀態(tài)s下選擇動(dòng)作a的好壞程度：

最優(yōu)值函數(shù)是在每一個(gè)狀態(tài)上，其值大于其他值函數(shù)在該狀態(tài)的值的值函數(shù)，即：

值函數(shù)的貝爾曼方程為：

基于式（3）、（4）、（5），可以得到最優(yōu)貝爾曼方程：

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

深度學(xué)習(xí)是一種有監(jiān)督的學(xué)習(xí)方法，使用神經(jīng)網(wǎng)絡(luò)對(duì)原始數(shù)據(jù)特征進(jìn)行多步特征轉(zhuǎn)換，不斷對(duì)原始數(shù)據(jù)中的特征進(jìn)行表征，最終得到可表示數(shù)據(jù)本質(zhì)特征的高維抽象特征[22]。目前，深度學(xué)習(xí)采用的模型主要是神經(jīng)網(wǎng)絡(luò)模型。

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

深度學(xué)習(xí)的核心是深度神經(jīng)網(wǎng)絡(luò)，神經(jīng)網(wǎng)絡(luò)可看作非線性模型，其基本組成單位時(shí)具有非線性激活函數(shù)的神經(jīng)元，通過大量神經(jīng)元的連接，神經(jīng)網(wǎng)絡(luò)成為非線性的模型。如圖1所示是神經(jīng)元與多層前饋神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)示意圖。

圖1 神經(jīng)元與多層前饋神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖Fig.1 Neuron and multi-layer feedforward neural network structure

神經(jīng)元由連接、求和節(jié)點(diǎn)和激活函數(shù)構(gòu)成，其實(shí)現(xiàn)了對(duì)輸入數(shù)據(jù)的非線性變化。多層前饋神經(jīng)網(wǎng)絡(luò)一般由多個(gè)網(wǎng)絡(luò)層組成，每層網(wǎng)絡(luò)層都由多個(gè)神經(jīng)元構(gòu)成。深度學(xué)習(xí)首先通過對(duì)有標(biāo)簽數(shù)據(jù)的訓(xùn)練得到網(wǎng)絡(luò)模型，之后進(jìn)入預(yù)測(cè)階段，新數(shù)據(jù)輸入網(wǎng)絡(luò)模型，最后得到新數(shù)據(jù)的預(yù)測(cè)結(jié)果。

1.2.2 神經(jīng)網(wǎng)絡(luò)優(yōu)化方法

神經(jīng)網(wǎng)絡(luò)優(yōu)化目標(biāo)是找到更好的局部最小值及提高優(yōu)化效率，其改善方法可分為以下幾類：

（1）使用更有效的優(yōu)化算法來提高梯度下降的效率和穩(wěn)定性，如使用學(xué)習(xí)率衰減、周期學(xué)習(xí)率調(diào)整等自適應(yīng)調(diào)整學(xué)習(xí)率方法；使用動(dòng)量法、Adam算法對(duì)梯度估計(jì)進(jìn)行修正。

（2）改進(jìn)參數(shù)初始化方法。參數(shù)設(shè)置在神經(jīng)網(wǎng)絡(luò)中非常關(guān)鍵，可使用隨機(jī)初始化方法，如正交初始化方法、基于方差縮放的初始化方法來提高神經(jīng)網(wǎng)絡(luò)的訓(xùn)練效果。

（3）修改神經(jīng)網(wǎng)絡(luò)模型，比如使用逐層歸一化，Relu激活函數(shù)以及殘差鏈接等。

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

2.1 調(diào)度問題的轉(zhuǎn)換

利用深度強(qiáng)化學(xué)習(xí)方法研究車間調(diào)度問題，首先需進(jìn)行車間調(diào)度問題向馬爾可夫決策過程的轉(zhuǎn)化，使得調(diào)度問題可以得到較好的表示與解決，首先需要適當(dāng)定義車間調(diào)度問題中的狀態(tài)空間、動(dòng)作空間與獎(jiǎng)懲函數(shù)。

2.1.1 狀態(tài)空間

狀態(tài)空間是調(diào)度過程中所有狀態(tài)的集合，為了充分表示調(diào)度過程中的狀態(tài)變化，狀態(tài)空間的表示應(yīng)該遵循以下原則：

狀態(tài)特征可描述調(diào)度環(huán)境的主要特征和變化；狀態(tài)特征的選擇應(yīng)該與調(diào)度目標(biāo)相關(guān)，否則會(huì)造成特征冗余；不同調(diào)度問題的所有狀態(tài)都用一個(gè)共同的特征集來表示；狀態(tài)特征是對(duì)狀態(tài)屬性的數(shù)值表示，狀態(tài)特征應(yīng)易于計(jì)算與表示。

本文采用文獻(xiàn)[23]的方法，將狀態(tài)特征表示為三個(gè)矩陣的形式，第一個(gè)矩陣為各工件每個(gè)工序的處理時(shí)間所組成的矩陣，第二個(gè)矩陣為當(dāng)前時(shí)間步長(zhǎng)的調(diào)度結(jié)果組成的矩陣，第三個(gè)矩陣為機(jī)器利用率組成的矩陣。以一個(gè)3×3的調(diào)度例子說明，如圖2所示為前三個(gè)工序的調(diào)度過程與狀態(tài)空間矩陣的轉(zhuǎn)化，在初始狀態(tài)，處理時(shí)間矩陣?yán)锩婷總€(gè)值都是工序的加工時(shí)間，調(diào)度結(jié)果矩陣與機(jī)器利用率矩陣都為零，當(dāng)前三個(gè)工序加工完成時(shí)，處理時(shí)間矩陣中已完成的工序轉(zhuǎn)換為零，調(diào)度結(jié)果矩陣轉(zhuǎn)換已完成的工序，機(jī)器利用率矩陣也進(jìn)行相應(yīng)的轉(zhuǎn)換。

圖2 狀態(tài)空間矩陣轉(zhuǎn)化情況圖Fig.2 State space matrix transformation

2.1.2 動(dòng)作空間

動(dòng)作空間為智能體在當(dāng)前狀態(tài)下可采取動(dòng)作的集合。在調(diào)度問題中，智能體執(zhí)行的動(dòng)作是根據(jù)調(diào)度規(guī)則選擇優(yōu)先加工的作業(yè)，動(dòng)作空間的選取為啟發(fā)式行為，為避免單一規(guī)則的短視性，選擇多個(gè)與最大完工時(shí)間相關(guān)的調(diào)度規(guī)則作為動(dòng)作空間。為了更好地確定調(diào)度規(guī)則，選取的調(diào)度規(guī)則要盡可能多樣化，調(diào)度規(guī)則本身可以與調(diào)度目標(biāo)相關(guān)，也可以不相關(guān)，選擇多樣化的調(diào)度規(guī)則來充分發(fā)揮智能體從經(jīng)驗(yàn)中學(xué)習(xí)的能力。本文共選取了20個(gè)調(diào)度規(guī)則，如表1所示。

表1 調(diào)度規(guī)則Table 1 Scheduling rules

應(yīng)用基于矩陣形式的狀態(tài)空間與以調(diào)度規(guī)則為動(dòng)作空間的調(diào)度轉(zhuǎn)化方法，適應(yīng)深度強(qiáng)化學(xué)習(xí)算法要求，根據(jù)生產(chǎn)狀態(tài)的變化選取調(diào)度規(guī)則，可以充分發(fā)揮算法的自主決策與優(yōu)化能力。相較于元啟發(fā)式算法傳統(tǒng)的兩段式編碼解碼方法，更能體現(xiàn)機(jī)器與加工工件在加工過程中的變化，更貼近實(shí)際生產(chǎn)狀態(tài)的變化。

2.1.3 獎(jiǎng)勵(lì)函數(shù)

獎(jiǎng)勵(lì)函數(shù)選取適當(dāng)與否與深度強(qiáng)化學(xué)習(xí)效果相關(guān)，短期獎(jiǎng)勵(lì)可以看作是每個(gè)動(dòng)作的短期回報(bào)，也代表該動(dòng)作對(duì)調(diào)度方案的短期影響。累計(jì)獎(jiǎng)勵(lì)反應(yīng)的是每個(gè)動(dòng)作產(chǎn)生的獎(jiǎng)勵(lì)總和，深度強(qiáng)化學(xué)習(xí)的最終目標(biāo)就是最大化累計(jì)獎(jiǎng)勵(lì)。

本文的調(diào)度目標(biāo)是最小最大完工時(shí)間，這一目標(biāo)可通過最大加工機(jī)器利用率來進(jìn)行轉(zhuǎn)換，因此使用平均機(jī)器利用率來表示機(jī)器加工的利用率，平均機(jī)器利用率可以表示為：

U為平均機(jī)器利用率，M為機(jī)器數(shù)，Cmax為最大完工時(shí)間，Tijm是機(jī)器加工工件某工序所需時(shí)間。令R=U，則獎(jiǎng)勵(lì)函數(shù)可以表示為：

2.2 D3QN算法

D3QN算法以DQN算法為基礎(chǔ)，結(jié)合了Double DQN與Dueling DQN。Double DQN可解決DQN過高的值函數(shù)估計(jì)問題，由于DQN算法在根據(jù)下一時(shí)間步的狀態(tài)選擇動(dòng)作的過程中可能會(huì)選擇過高的估計(jì)值，從而導(dǎo)致過高的值函數(shù)估計(jì)，因此Double DQN在計(jì)算目標(biāo)Q值時(shí)使用兩個(gè)不同的網(wǎng)絡(luò)模型參數(shù)，使得動(dòng)作的選擇和動(dòng)作的狀態(tài)值估計(jì)解耦，進(jìn)而可避免過高的值函數(shù)估計(jì)。Dueling DQN對(duì)DQN網(wǎng)絡(luò)架構(gòu)進(jìn)行修改，大幅提升了學(xué)習(xí)效果，如圖3所示，Dueling DQN對(duì)于DQN的改進(jìn)在于全連接層，將全連接層改為兩個(gè)流，一條輸出關(guān)于價(jià)值的函數(shù)，另一條輸出關(guān)于動(dòng)作的優(yōu)勢(shì)函數(shù)的值，二者結(jié)合成價(jià)值函數(shù)，智能體可學(xué)習(xí)到在沒有動(dòng)作影響下更真實(shí)的價(jià)值函數(shù)。

圖3 Dueling DQN與DQN網(wǎng)絡(luò)架構(gòu)對(duì)比圖Fig.3 Dueling DQN versus DQN network architecture

2.2.1 探索與利用

探索的目的是找到更多有關(guān)環(huán)境的信息，而利用的目的是利用已知的環(huán)境信息來最大限度地提高獎(jiǎng)勵(lì)。在算法嘗試次數(shù)有限的前提下，探索和利用兩者本身是矛盾的，增加探索的次數(shù)就會(huì)降低利用的次數(shù)，反之亦然，因此必須平衡探索與利用的次數(shù)，以達(dá)到最大累計(jì)獎(jiǎng)勵(lì)。本文使用ε-貪婪算法來實(shí)現(xiàn)智能體的探索與利用，ε-貪婪算法的數(shù)學(xué)表達(dá)式為：

P=ε表示算法以ε的概率選擇動(dòng)作空間的動(dòng)作，P=1-ε表示算法以1-ε的概率選擇當(dāng)前時(shí)間步內(nèi)價(jià)值最大的動(dòng)作作為下個(gè)時(shí)間步要執(zhí)行的動(dòng)作。

2.2.2 算法流程與實(shí)施

本文利用結(jié)合DDQN與Dueling DQN算法的D3QN算法應(yīng)用于作業(yè)車間調(diào)度問題，D3QN算法框架如下：

（1）初始化復(fù)用池D的容量為N；初始化動(dòng)作值函數(shù)Q，設(shè)置隨機(jī)權(quán)重θ；初始化目標(biāo)動(dòng)作值網(wǎng)絡(luò)Q?，權(quán)重參數(shù)為θ-=θ。

（2）forepisode=1，Mdo；初始化序列以及第一個(gè)對(duì)狀態(tài)的預(yù)處理序列。

（3）fort=1，Tdo；以ε的概率隨機(jī)選擇一個(gè)動(dòng)作at否則選擇。

（4）在調(diào)度環(huán)境中執(zhí)行動(dòng)作at并安排優(yōu)先級(jí)最高的工件，將完成的工序從第一個(gè)矩陣中刪除并加入到第二個(gè)矩陣中。

（5）觀察獎(jiǎng)勵(lì)ri和下一個(gè)狀態(tài)st+1；下一個(gè)狀態(tài)st+1=st,at,xi+1，下一個(gè)預(yù)處理序列?t+1=?(st+1)。

（6）存儲(chǔ)樣本于經(jīng)驗(yàn)復(fù)用池D中，隨機(jī)抽取小批量樣本(?j,aj,rj,?j+1)。

（7）計(jì)算每個(gè)樣本的TD目標(biāo)差，在(yt-Q(?j,aj;θ))2上執(zhí)行梯度下降；每隔c步重設(shè)Q?=Q。

算法共有兩個(gè)循環(huán)，算法開始階段，將一個(gè)調(diào)度實(shí)例的工序處理時(shí)間矩陣、調(diào)度結(jié)果矩陣以及機(jī)器利用率矩陣組成的三通道矩陣輸入卷積神經(jīng)網(wǎng)絡(luò)，輸出是單個(gè)動(dòng)作的預(yù)測(cè)Q值。在episode開始時(shí)，調(diào)度方案被重置，獲得初始狀態(tài)s0，在t≤T時(shí)，智能體觀察當(dāng)前狀態(tài)，根據(jù)ε-貪婪策略執(zhí)行一個(gè)動(dòng)作，在動(dòng)作執(zhí)行以后，具有最高優(yōu)先級(jí)的工件進(jìn)行處理，完成的工序會(huì)從工件工序處理時(shí)間矩陣中刪除，剩余的工序仍然保存在當(dāng)前時(shí)間步長(zhǎng)處理結(jié)果矩陣中。之后智能體得到獎(jiǎng)勵(lì)r1并觀察下一個(gè)狀態(tài)st+1，并將序列(?t,at,rt,?t+1)存入經(jīng)驗(yàn)復(fù)用池。當(dāng)經(jīng)驗(yàn)復(fù)用池中存儲(chǔ)了足夠多的樣本后，從其中隨機(jī)取出小批量樣本，計(jì)算每個(gè)樣本的TD差，之后對(duì)θ執(zhí)行梯度下降法求解，每隔c步重設(shè)Q?=Q。算法流程如圖4所示。

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

3.1 模型與參數(shù)設(shè)置

本文應(yīng)用算法為Dueling Double DQN（D3QN），基于Python語言與Tensorflow2.0框架實(shí)現(xiàn)，配置Intel Core i5-9300H CPU＠2.40 GHz，RAM 16 GB。在D3QN中，第一層為狀態(tài)空間輸入層，之后連接三個(gè)卷積層，在進(jìn)行卷積操作后，將提取的特征分流競(jìng)爭(zhēng)網(wǎng)絡(luò)層，競(jìng)爭(zhēng)網(wǎng)絡(luò)層包括兩個(gè)支路，價(jià)值網(wǎng)絡(luò)和優(yōu)勢(shì)動(dòng)作網(wǎng)絡(luò)，二者都是完全連接的，價(jià)值網(wǎng)絡(luò)只有一個(gè)輸出，動(dòng)作優(yōu)勢(shì)網(wǎng)絡(luò)的輸出與動(dòng)作空間一樣多，二者最終匯合到一起得Q值，卷積層激活函數(shù)選用Relu，算法模型結(jié)構(gòu)如圖5所示。

參數(shù)設(shè)置對(duì)于算法的表現(xiàn)具有較大影響，但參數(shù)范圍較廣，難以確定合適參數(shù)，因此遵循一般的設(shè)置原則。部分參數(shù)設(shè)置如表2所示。

圖4 算法流程圖Fig.4 Algorithm process

圖5 算法模型結(jié)構(gòu)圖Fig.5 Algorithm model structure

表2 D3QN模型部分參數(shù)設(shè)置Table 2 Some parameter settings for D3QN model

3.2 算例實(shí)驗(yàn)與分析

為驗(yàn)證算法的有效性，對(duì)算法進(jìn)行實(shí)例驗(yàn)證，選取的實(shí)例來源于已公開的FT、LA、SWV[23]基準(zhǔn)測(cè)試實(shí)例。

本文選取最大完工時(shí)間為評(píng)價(jià)指標(biāo)，算法的動(dòng)作空間為調(diào)度規(guī)則，因此選用兩個(gè)單一調(diào)度規(guī)則以及標(biāo)準(zhǔn)遺傳算法、粒子群算法與本算法進(jìn)行比較，算例實(shí)驗(yàn)對(duì)比情況如表3所示，其中最優(yōu)調(diào)度結(jié)果以粗體顯示。

表3 實(shí)驗(yàn)結(jié)果對(duì)比Table 3 Comparison of experimental results

分析表3可知，D3QN在標(biāo)準(zhǔn)算例上的表現(xiàn)明顯優(yōu)于單一調(diào)度規(guī)則，相較于標(biāo)準(zhǔn)遺傳算法和粒子群算法，在小規(guī)模問題的表現(xiàn)上具有一定優(yōu)勢(shì)，雖在部分問題上也并未取得最優(yōu)解，但在大規(guī)模問題的表現(xiàn)上明顯較好。在面對(duì)大規(guī)模問題時(shí)，D3QN雖未在調(diào)度問題上取得最優(yōu)解，但所求解的質(zhì)量下降較為緩慢，且這一趨勢(shì)會(huì)隨著問題規(guī)模的增大而更為明顯，這表明算法本身的適應(yīng)度較好。由于算法使用Python語言及Tensorflow框架，算法時(shí)間對(duì)比并未列出，基于神經(jīng)網(wǎng)絡(luò)的算法在經(jīng)過訓(xùn)練之后可以在較短時(shí)間內(nèi)輸出調(diào)度結(jié)果。圖6、圖7所示是D3QN對(duì)比粒子群算法、遺傳算法在ft10與swv06算例上完工時(shí)間隨迭代次數(shù)變化對(duì)比圖。

圖6 ft10最大完工時(shí)間迭代對(duì)比圖Fig.6 ft10 maximum completion time iteration

圖7 swv06最大完工時(shí)間迭代對(duì)比圖Fig.7 swv06 maximum completion time iteration

分析圖6、圖7可了解D3QN算法相較于PSO、GA在前期完工時(shí)間迭代下降較為緩慢，但在后期迭代過程中則會(huì)得到算例的較優(yōu)值。

4 結(jié)束語

本文利用D3QN對(duì)作業(yè)車間調(diào)度問題進(jìn)行研究，將調(diào)度問題轉(zhuǎn)化為一個(gè)序列決策問題，用多通道圖像來表示每個(gè)時(shí)間步的調(diào)度狀態(tài)，使用啟發(fā)式規(guī)則及組合作為動(dòng)作空間，設(shè)置獎(jiǎng)勵(lì)函數(shù)，在標(biāo)準(zhǔn)算例的驗(yàn)證下，算法的調(diào)度效果優(yōu)于單一調(diào)度規(guī)則與智能優(yōu)化算法，總體上取得了較為可觀的調(diào)度結(jié)果。

進(jìn)一步的研究工作可以集中在以下幾個(gè)方面，獎(jiǎng)勵(lì)函數(shù)的設(shè)置利用了兩個(gè)連續(xù)時(shí)間步的機(jī)器利用率之差，將進(jìn)一步研究更有效的設(shè)置方法來達(dá)到更好的效果；使用的D3QN算法模型本質(zhì)上是基于價(jià)值的DRL方法，為進(jìn)一步提升算法性能可考慮基于策略的DRL方法，例如AC、AC3等；研究問題集中于單一的作業(yè)車間調(diào)度問題，可進(jìn)一步研究算法在多目標(biāo)車間調(diào)度問題、動(dòng)態(tài)調(diào)度問題其他復(fù)雜調(diào)度問題上的應(yīng)用效果。