深度強化學習算法求解作業(yè)車間調(diào)度問題

李寶帥，葉春明

上海理工大學 管理學院，上海 200093

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

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

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

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

1 基本原理

1.1 強化學習

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

1.1.1 馬爾可夫決策過程

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

1.1.2 強化學習求解

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

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

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

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

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

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

1.2 深度學習

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

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

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

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

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

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

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

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

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

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

2 深度強化學習方法

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

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

2.1.1 狀態(tài)空間

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

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

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

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

2.1.2 動作空間

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

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

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

2.1.3 獎勵函數(shù)

獎勵函數(shù)選取適當與否與深度強化學習效果相關(guān)，短期獎勵可以看作是每個動作的短期回報，也代表該動作對調(diào)度方案的短期影響。累計獎勵反應的是每個動作產(chǎn)生的獎勵總和，深度強化學習的最終目標就是最大化累計獎勵。

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

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

2.2 D3QN算法

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

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

2.2.1 探索與利用

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

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

2.2.2 算法流程與實施

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

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

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

（3）fort=1，Tdo；以ε的概率隨機選擇一個動作at否則選擇。

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

（5）觀察獎勵ri和下一個狀態(tài)st+1；下一個狀態(tài)st+1=st,at,xi+1，下一個預處理序列?t+1=?(st+1)。

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

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

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

3 實例驗證

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

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

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

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

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

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

3.2 算例實驗與分析

為驗證算法的有效性，對算法進行實例驗證，選取的實例來源于已公開的FT、LA、SWV[23]基準測試實例。

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

表3 實驗結(jié)果對比Table 3 Comparison of experimental results

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

圖6 ft10最大完工時間迭代對比圖Fig.6 ft10 maximum completion time iteration

圖7 swv06最大完工時間迭代對比圖Fig.7 swv06 maximum completion time iteration

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

4 結(jié)束語

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

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