基于深度強化學習的隨機資源受限多項目動態調度策略

收稿日期：2022-03-01；修回日期：2022-04-18

作者簡介：郭曉劍（1971-），男，江西贛州人，副教授，碩士，主要研究方向為項目管理、BIM技術人工智能；胡方勇（1999-），男，浙江溫州人，碩士，主要研究方向為項目調度與管理（1443204684@qq.com）．

摘 要：目前對于隨機工期的分布式資源受限多項目調度問題（SDRCMPSP）的研究較少且大多數為靜態調度方案，無法針對環境的變化實時地對策略進行調整優化，及時響應頻繁發生的動態因素。為此建立了最小化總拖期成本為目標的隨機資源受限多項目動態調度DRL模型，設計了相應的智能體交互環境，采用強化學習中的DDDQN算法對模型進行求解。實驗首先對算法的超參數進行靈敏度分析，其次將最優組合在活動工期可變和到達時間不確定兩種不同條件下對模型進行訓練及測試，結果表明深度強化學習算法能夠得到優于任意單一規則的調度結果，有效減少隨機資源受限多項目期望總拖期成本，多項目調度決策優化提供良好的依據。

關鍵詞：分布式多項目；隨機調度；深度強化學習；資源約束

中圖分類號：TP18"" 文獻標志碼：A

文章編號：1001-3695（2022）09-029-2752-05

doi：10.19734/j.issn.1001-3695.2022.03.0065

Stochastic resource-constrained multi-project dynamic scheduling strategy based on deep reinforcement learning

Guo Xiaojian，Hu Fangyong

（School of Economics amp; Management，Jiangxi University of Science amp; Technology，Ganzhou Jiangxi 341000，China）

Abstract：There are few studies on the problem of stochastic resource-constrained distributed multi-project scheduling（SDRCMPSP） and most of them are static scheduling schemes，which cannot adjust and optimize the strategy in real time according to changes in the environment and respond to frequent dynamic factors in a timely manner.Therefore，this paper established a stochastic resource-constrained multi-project dynamic scheduling DRL model with the goal of minimizing the total drag cost，designed the corresponding agent interaction environment，and used the DDDQN algorithm in reinforcement learning to solve the model.The experiment firstly analyzed the hyperparameters of the algorithm，and then trained and tested the model under two different conditions of variable activity duration and uncertain arrival time，and the results show that the deep reinforcement learning algorithm can obtain scheduling results that are better than any single rule，effectively reduce the total drag-off cost of random resources limited multi-project expectations，and provide a good basis for multi-project scheduling decision optimization.

Key words：distributed multi-project；stochastic scheduling；deep reinforcement learning；resource-constrained

0 引言

隨著社會的發展，項目管理技術顯得尤為重要，在項目調度的過程中，資源的合理配置與調度起著決定性的作用，該類問題通常稱之為資源受限項目調度問題（resource-constrained project scheduling problem，RCPSP）［1］。現實情況下往往需要同時調度多個資源受限的項目［2］，且存在局部與全局資源的約束稱之為分布式資源受限多項目調度問題（distributed resource-constrained multi-project scheduling problem，DRCMPSP）。然而在工程實際中，項目實施可能受到各種不確定因素的影響，如缺少相關項目經驗、生產設備故障、資源不可用、天氣狀況等導致活動工期或項目到達時間與預估時間產生偏離［3］，使預先制定的多項目計劃不可行，便需要一種有效的方法減少多項目的期望總拖期成本ETTC（except total tardiness cost），該類問題稱之為隨機資源受限多項目調度問題（SDRCMPSP）。目前關于SDRCMPSP的文獻相對較少，并且大部分調度策略是靜態的［4］，如優先規則算法［5，6］。此外Song等人［7］采用優先規則啟發式算法來生成基線計劃，并將受影響的活動推至最早可行的時間執行。Tosselli等人［8］采用了重復協商博弈的方法。劉東寧等人［9］采用了多優先規則啟發式方法（MPRH），該方法雖然能夠在活動工期變化的動態環境下減少多項目工期延誤成本，但在每次決策點時需要進行多次仿真實驗，未對以往經驗進行有效的利用，無法及時對動態環境作出實時的決策。

以目標為導向的強化學習算法，以其能夠實現離線學習與在線應用的優勢被廣泛運用于動態環境下的調度問題上［10］。且由以往文獻可知強化學習算法被廣泛運用于車間作業的動態調度問題上并取得較好的結果［11～14］，且目前并未有文獻研究深度強化學習算法在多項目隨機調度問題上的應用，因此本文將該算法運用至SDRCMPSP的動態調度上。

本文針對活動工期、項目到達日期偏差情況而造成多項目作業的總拖期成本（total tardiness cost，TTC）增加的影響，通過深度強化學習中智能體不斷與環境進行仿真交互，采用文獻［14］的DDDQN算法進行調度策略的優化。首先提出靜態環境下多項目調度的數學模型并將其結合并行調度方案轉換為動態調度過程；其次根據多項目動態調度流程及總拖期成本搭建與智能體交互的環境，運用DDDQN算法使智能體在環境中根據當前狀態不斷進行探索和對現有知識的利用優化不同狀態下的策略，以此降低隨機資源約束多項目調度的ETTC。將所建立的模型與算法進行超參數的策略組合分析求出最優的超參數組合，后將該組合運用于活動工期可變或項目到達時間不確定的動態環境下進行仿真研究。仿真結果表明，應用深度強化學習方法能夠使智能體學習到優于任何單一規則的調度策略，為多項目在動態環境下的調度提供良好的決策依據。

1 問題描述

1.1 多項目靜態問題

假設一個多項目是由m單一項目i（i=1，…，m）所組成，在項目i中存在aij（j=1，…，Ji）個實活動，其工期為dij和兩個工期及資源用量為零的虛擬活動ai0、ai（Ji+1）。Aij表示活動aij的緊前活動集合，活動aij的開始時間需大于Aij中活動完成時間的最大值；Li表示項目i的局部資源集合；Ril表示局部資源的可用量；G表示全局資源集合用Rg表示其可用量；活動aij在任意時刻被執行時，需要rlij及rgij的局部和全局可更新資源；項目i的到達時間為STi，其完工日期以項目i的ai（Ji+1）活動的完工時間FTi（Ji+1）表示。當FTi（Ji+1）超出截止日期時便會產生拖期成本（tardiness cost，TC），對于項目i，其延期成本TCi為

TCi=（FTi（Ji+1）-STi-cpli）×ci（1）

其中：ci表示項目i單位延期成本；STi+cpli表示項目i的截止日期。而在考慮全局資源分配的多項目調度問題中，其目標為最小化各項目的總拖期成本TTC，即

Min ∑mi=1TCi（2）

1.2 多項目動態調度轉換

然而在實際情況中，活動工期受到環境的不確定性而產生變化服從一定的概率分布，此時多項目的靜態調度問題轉變為動態調度問題。由于串行調度盡早安排活動的原理，不適用于動態環境下多項目的調度，本文采用并行調度方式實現多項目的動態調度。在多項目的并行調度過程中，t表示當前時間（多項目開工至今的時間且初始為0），存在的集合包括已完工活動集合F、正在執行的活動作業集合D、所有緊前活動均已完工的候選活動集合P、各項目未選擇活動的集合U。多項目動態調度流程如下：

a）輸入多項目調度信息包括各項目的規模、活動工期、優先級關系、局部與全局資源需求量，清空所有活動集合。

b）判斷所有未添加至U集合的項目開始時間STi是否小于等于t，若是則將對應項目的所有活動添加至U。

c）判斷U中是否存在所有緊前活動均已完工的活動，若存在則將其添加至P中并從U中刪除該活動，否則轉至步驟c）。

d）若P為非空集合，則根據調度規則從P中選取優先級最高的活動并判斷所選活動與D中活動是否存在資源沖突，若是則轉至步驟d），否則將該活動從P中刪除后添加至D中，并繼續步驟c）；若P為空集合，轉至步驟d）。

e）判斷D中最早完工的一個或若干個活動，令t等于這些活動的完工時間，將其從D中移除并添加至F中。

f）判斷多項目的活動是否全部完成，若是則輸出各項目的完工時間即FTi（Ji+1）（i=1，…，m），同時計算+TTC，否則轉至步驟b）。

2 基于DDDQN的分布式多項目動態調度

多項目動態調度的問題是要從當前時刻各項目的可執行活動集中按照一定規則，并在滿足局部、全局資源約束的條件下選取優先執行的若干個活動進行作業，直到所有項目的活動均調度完成為止。這是一個連續的決策過程，因此可以將該問題轉換為馬爾可夫或半馬爾可夫決策問題，即對問題的狀態、動作、即時獎勵進行定義。

2.1 狀態描述

狀態的特征定義應能夠充分反映當前時刻智能體所處環境的局部和全局特征，當進行決策時，智能體需根據當前時刻的環境特征作出左右決策。當問題的狀態集為有限個時，可以采取數組或表格的方式進行表示，被稱之為RL。然而在實際問題中往往具有較大或者連續的狀態空間，此時需要采用深度神經網絡函數逼近的能力，消除RL算法面臨的維度災難問題。在本文中多項目調度的狀態特征包括三個m×max（Ji+1）的矩陣，max（Ji+1）表示所有項目活動規模中的最大值，三個矩陣分別為調度結果矩陣FN、活動作業矩陣DN、可執行活動矩陣PN。

FN是由每個項目中各活動的完工時間組成的矩陣，在輸入網絡前對其進行最大值標準化處理，初始賦值為零。

FN=FT1，1…FT1，J1-1…FT1，max（Ji-1）

FTi，1FTi，Ji-1FT1，max（Ji-1）

FTm，1…FTm，Jm-1…FTm，max（Ji-1）（3）

DN表示各項目中每個活動當前所處狀態，若正在執行則為1，否則為0。由于該矩陣中的數值取值為1或0，所以不需要規范化。

DN=1…1…0

1…0…0

0…0…0（4）

PN表示各項目中每個活動是否在當前時刻執行（即該活動的所有緊前活動均已完成），若是則為1，否則為0。同理無須進行規范化。

PN=0…1…0

0…1…0

0…1…0（5）

考慮到深度學習原始輸入中的特征提取，將三個特征矩陣看做高度為矩陣行數、寬度為矩陣列數的圖像的三個不同通道，采用卷積輸入的形式進行訓練。

2.2 動作定義

在多項目動態調度DRL模型中，動作空間是由許多單一規則的調度算法組成的，通過強化學習算法針對不同狀態選擇合適的調度規則，以此克服單一規則的局限性。本文選用15個單一的調度規則，前7個為集中式調度規則，后8個為復合式調度規則。其中OFTi表示項目i在僅考慮局部資源約束下的最優調度方案，采用基于活動列表編碼的改進灰狼算法求解所得。15個調度規則如表1所示，其中項目i表示已經到達且候選活動集非空的項目，j表示該項目中的候選活動。其中規則1～6將各項目的候選活動集視為一個集合在選擇活動的同時確定了該活動所在項目，規則7～14則是優先選擇項目p之后從項目p的候選活動集中選取活動。

2.3 獎勵函數

由于本文研究的分布式多項目動態調度的目標時實現總拖期成本最小，為了即時獎勵能夠準確評價動作進行如下設定：

rt=∑mi=1（∑j∈Ftidij-∑j∈Ft-1idij）∑mi=1 ∑Ji+1j=1dij+（max{FTt-1i}-max{FTti}）×ωi∑mi=1 ∑Ji+1j=1dij（6）

其中：max{FTii}表示t時刻項目i已完工活動的最大完工時間；ωi表示項目拖期成本。令

ut=∑mi=1（∑j∈Ftdij-max{FTti}×ωi）∑mi=1 ∑Ji+1j=1dij（7）

則u0=0。此時算法的累計獎勵計算公式如下：

R=∑Ttrt=∑Tt=1ut-1-ut=u0-u1+u1-u2+…+uT-1-uT=

u0-uT=∑mi=1 ∑Jij=1dij-max{FTTi}×ωi∑mi=1 ∑Ji+1j=1dij（8）

因此累計獎勵R最大化等同于uT最小，由于各活動的預計工期dij均為常數，則uT最小等同于各項目完工工期與拖期成本乘積之和最小，即TTC最小。

2.4 探索利用策略

合理探索利用策略能夠使得智能體充分利用所學到的經驗知識，同時保證能夠探索新的策略行為。本文采用的探索利用策略為線性遞減的貪婪策略，智能體的動作策略如下：

a=arg maxa′Q（a′）rand（）lt;ε

randomrand（）gt;ε（9）

其中：rand（）為一個［0，1］的隨機數；ε為貪婪策略的概率，服從分布為

εt=min（εmin，εt-1×εrate）（10）

其中：εmin為ε的最小值；εrate為衰減率。

2.5 DDDQN算法流程

a）定義算法折扣因學習率α，經驗池容量M，網絡訓練周期L，目標網絡更新周期N，最小訓練批量mini_batch，最大訓練回合T_max，初始化Q網絡與目標Q網絡參數θ、θ′，輸入多項目調度信息，令step=0。

b）重置各項目調度計劃信息并清除調度結果集，初始化多項目調度狀態s0。

c）根據當前狀態state，依據探索利用策略選擇當前決策點智能體的action選擇的優先規則調度算法，進行多項目調度流程中的步驟b）～e）。

d）根據式（6）計算當前時刻的即時獎勵值reward與下一時刻狀態state_以及訓練是否結束標志done（結束為true，未結束為1），將{state，action，reward，state_，done}五元組存儲至經驗池中。

e）判斷是否滿足網絡參數更新條件，若是則根據TD誤差對網絡參數進行更新，否則轉至步驟f）。

f）判斷所有項目是否全部完工，若是則令step+=1轉至步驟g），否則轉至步驟c）。

g）判斷是否達到最大訓練回合即step=T_max，若是則停止訓練并將Q網絡參數保存至本地，否則轉至步驟b）。

算法1 基于DDDQN的多項目動態調度流程

1 初始化最小訓練批量mini_batch，step-size η，經驗池容量 M，網絡訓練周期 L 和目標網絡更新周期 N，最大訓練周期T_max，動作選擇次數num=0

2 隨機初始化Q網絡參數θ并將其參數復制給目標Q′網絡θ′

3 for step=1 to M do

4" 重置多項目調度信息、清除調度結果，初始化調度狀態s1

5" while多項目活動未全部完工 then

6"" 基于探索利用策略選擇動作及對應的優先規則，num+=1

7"" 根據最大優先規則執行多項目調度中的步驟2～4直到產生資源沖突

8"" 計算當前獎勵rt和下一狀態st+1，判斷done是否為true

9""" 將（st，at，rt，st+1，done）存儲至經驗池M

10"" if num% L==0 and numgt;mini_batch then

11"" 從經驗池中隨機選取mini_batch個（st，at，rt，st+1，done）。

12""" for j=1 to mini_batch do

13"""" 令yj=rjif done=true

rj+γQ′（sj+1，argmaxaQ（sj+1，a；θ），θ′）otherwise

14""" end for

15""" 根據y與Q（s，a；θ）采用反向傳播更新Q網絡參數θ

16"" end if

17"" if num% N==0 then

18""" 將Q網絡的參數θ復制給目標Q網絡θ′←θ

19" end if

20 break

21 end for

3 仿真實驗

為驗證所搭建仿真環境的有效性以及DDDQN算法解決對分布式多項目動態調度問題的有效性，選取MPSPLIB標準庫中的MP30_5和MP90_2問題集進行測試，各問題集均含有5個算例，具體信息如表2所示。實驗在配備Windows 10 64位系統、24 GB運行內存、處理器為AMD R7 4800H的筆記本上搭建TensorFlow 2.0的環境下運行。同時，多項目中活動工期服從常見概率分布類型，如表3所示。

3.1 參數分析

在強化學習中超參數對于網絡學習性能至關重要，目前對于超參數的確定一般依靠人工經驗和隨機搜索。為確定最優的超參數組合，本文選用算例MP30_5_5在工期為U1分布類型對模型的網絡結構、速率rate、目標網絡更新周期N、最小訓練批量mini_batch、折扣率γ等超參數進行了靈敏度分析，同時在對某一超參數進行靈敏度分析時其他超參數的取值均保持不變。圖1為DRL模型的超參數在不同取值下的累計獎勵迭代圖，通過訓練過程中累計獎勵的變化來判斷該超參數取值的效果。從圖中可以看出，不同網絡結構能夠影響算法的性能，當網絡結構取值為紅線（見電子版）所示時算法的性能最佳，將其確定為本文模型的網絡結構，此時其他參數均保持不變。同理可得模型的其他超參數的取值，最終確定超參數策略如表4所示。

圖1（a）表示五種不同卷積層對算法的影響，每一行表示濾波器數量和內核大小，其中步幅均為（1，1）。由圖中可以看出第四種網絡結構相對于其他四種，能夠為算法帶來更有效的性能提升。圖1（b）表示不同的學習率對于算法的影響，可以看出，當rate較低時算法訓練性能最差，而rate較高時算法性能有所下降，因此本文選取學習率為0.000 1。圖1（c）表示不同的目標網絡更新周期對算法的影響，從圖中可以看出，當N=100周期的訓練性能最好。從圖1（d）可以看出，最小訓練批量對算法的影響較小，當mini_batch為64時算法的性能會有所下降，當mini_batch為256或128時算法的收斂趨勢較為穩定，但由于256需要更多的訓練時間，所以選用128。圖1（e）表示不同的折扣系數對于算法的影響，同理當γ較低時會降低算法性能，當γ較高時算法收斂較慢，選取0.99折扣率。

3.2 DRL模型求解問題集

本節將本文提出的DRL模型運用至兩種問題集的10個算例上，實驗分為模型訓練階段和測試階段。在訓練階段，將DRL模型分別在不同工期分布下的10個算例分別進行5 000次仿真訓練，模型的超參數取值策略如表4所示，并將各算例訓練完成的模型保存在本地。在模型的測試階段，將10個算例所訓練完成的10個模型分別在對應算例的5種工期分布下進行50次仿真調度求得平均的TTC。

圖2為算例MP30_5_5在5種工期分布下的訓練過程。可以看出，對于方差相對較小的U1、B1的TTC迭代曲線處于最下方且波動最小；對于方差中等的U2、B2的TTC迭代曲線處于中間位置且波動中等；對于方差較大的Exp的TTC迭代曲線處于最上方位置且波動較大，表明總拖期成本的期望水平隨著活動工期不確定程度的增加而增大。

圖2 不同工期分布下的TTC迭代過程

Fig.2 TTC iteration process under different duration distributions

對于算例MP30_5_5訓練完成的模型測試階段，將訓練完成模型與動作空間中15種單一調度規則在對應工期分布下分別進行50次仿真調度求得平均的TTC，如圖3所示。由圖3可以看出，DRL算法克服單一規則的短視性，在動態環境中獲得了更好的調度結果。進一步選取15種規則在5種工期分布下表現最好的規則與DRL模型所得的結果進行對比，如表5所示，并以改進率improve作為評價指標，如式（11）所示。表6為優先規則算法和DRL模型調度在完成50次多項目調度過程的運行時間。可以看出，與優先規則調度算法相比，訓練后的模型可以根據環境的當前狀態快速作出最優調度決策，速度相當于優先規則算法。

improve=best-agentbest×100%（11）

MP30_5與MP90_2問題集在不同工期分布下50次調度的平均TTC值如表7所示。對比文獻［9］，其中MP30_5在U1分布下的結果本文較差，而MP90_2的結果本文較優。

3.3 不確定到達時間

在實際情況中，項目的到達時間往往會因局部資源的缺乏而與預計的到達時間產生偏差。因此本節研究了DRL模型在項目到達時間不確定環境下對多項目總拖期成本的影響，其中項目活動的工期為常工期分布，項目到達時間服從以下分布：

STi=U1a=0

U2a=1

Expa=2

B1a=3

B2a=4（12）

式（12）中的分布類型特征與3.2節工期分布相同；a取值為［0，4］，隨機整數TCi=（FTi（Ji+1）-STi-cpli）×ci，例如當a=0時表示項目i的到達時間為服從U1分布的隨機數。

多項目到達時間不確定所產生的狀態組合小于不確定工期情況，因此DRL模型的訓練回合設置為5 000次且模型的超參數組合與3.2節相同。圖4為模型訓練過程的總拖期成本TTC的變化曲線，在訓練的過程中TTC隨著訓練回合的增加不斷減少并趨于穩定，表明模型進行了有效的訓練。

現有文獻并沒有對不確定項目到達時間的DRCMPSP的研究，因此將訓練完成的模型進行100次仿真實驗后所得的平均TTC值為3 022.01，與15種規則中最優規則的TTC值4 973.75進行對比，其改進率為64.6%。

4 結束語

本文首次將深度強化學習運用至多項目調度問題，在此基礎上提出基于DRL的分布式多項目動態調度模型，以實現隨機工期下分布式多項目調度問題總拖期成本最小化的目標，并搭建了智能體交互的仿真環境，以算例MP30_5和MP90_2問題集中的算例進行仿真實驗，一方面對模型的超參數取值策略進行靈敏度分析，另一方面對通過算例對模型進行訓練和測試。結果表明本文所提出的DRL模型對于實現分布式多項目在隨機環境下的動態調度有一定優勢，訓練好的模型在決策階段的作出策略的速度與優先規則相差無幾，同時能夠有效降低隨機分布式多項目調度所需的總拖期成本，拓展了深度強化學習在隨機性項目調度問題上的運用。

參考文獻：

［1］Lova A，Tormos P.Analysis of scheduling schemes and heuristic rules performance in resource-constrained multi-project scheduling［J］.Annals of Operations Research，2001，102（1-4）：263-286.

［2］Lee Y H，Kumara S，Chatterjee K.Multi-agent based dynamic resource scheduling for distributed multiple projects using a market mechanism［J］.Journal of Intelligent Manufacturing，2003，14（5）：471-484.

［3］Davari M，Demeulemeester E.Important classes of reactions for the proactive and reactive resource-constrained project scheduling problem［J］.Annals of Operations Research，2019，274（1-2）：187-210.

［4］Satic U，Jacko P，Kirkbride C.Performance evaluation of scheduling policies for the dynamic and stochastic resource-constrained multi-project scheduling problem［J］.International Journal of Production Research，2020，60（4）：1411-1423.

［5］Wang Yanting，He Zhengwen，Kerkhove L P，et al.On the performance of priority rules for the stochastic resource constrained multi-project scheduling problem［J］.Computers amp; Industrial Engineering，2017，114：223-234.

［6］Chen Haojie，Ding Guofu，Zhang Jian，et al.Research on priority rules for the stochastic resource constrained multi-project scheduling problem with new project arrival［J］.Computers amp; Industrial Enginee-ring，2019，137：106060.

［7］Song Wen，Xi Hui，Kang Donghun，et al.An agent-based simulation system for multi-project scheduling under uncertainty［J］.Simulation Modelling Practice and Theory，2018，86（11）：187-203.

［8］Tosselli L，Bogado V，Martínez E.A repeated-negotiation game approach to distributed（re） scheduling of multiple projects using decoupled learning［J］.Simulation Modelling Practice and Theory，2019，98（4）：101980.

［9］劉東寧，徐哲.基于多優先規則啟發式的分布式多項目隨機調度［J］.系統工程理論與實踐，2021，41（12）：3294-3303.（Liu Dongning，Xu Zhe.A stochastic scheduling for distributed multi-project with multi-PR heuristic［J］.Systems Engineering-Theory amp; Practice，2021，41（12）：3294-3303.）

［10］韓忻辰，俞勝平，袁志明，等.基于Q-learning的高速鐵路列車動態調度方法［J］.控制理論與應用，2021，38（10）：1511-1521.（Han Xincheng，Yu Shengping，Yuan Zhiming，et al.High-speed railway dynamic scheduling based on Q-learning method［J］.Control Theory amp; Applications，2021，38（10）：1511-1521.）

［11］Waschneck B，Reichstaller A，Belzner L，et al.Deep reinforcement learning for semiconductor production scheduling［C］//Proc of the 29th Annual Advanced Semiconductor Manufacturing Conference.

［12］Lin Chuncheng，Deng D J，Chih Y L，et al.Smart manufacturing scheduling with edge computing using multi-class deep Q network［J］.IEEE Trans on Industrial Informatics，2019，15（7）：4276-4284.

［13］Liu Chienliang，Chang Chuanchin，Tseng C J.Actor-critic deep reinforcement learning for solving Job-Shop scheduling problems［J］.IEEE Access，2020，8：71752-71762.

［14］Han Baoan，Yang Jianjun.Research on adaptive Job-Shop scheduling problems based on dueling double DQN[J].IEEE Access，2020，8：186474-186495.