基于深度強化學習的電子政務云動態化任務調度方法

摘 要：電子政務云中心的任務調度一直是個復雜的問題。大多數現有的任務調度方法依賴于專家知識，通用性不強，無法處理動態的云環境，通常會導致云中心的資源利用率降低和服務質量下降，任務的完工時間變長。為此，提出了一種基于演員評論家（actor-critic，A2C）算法的深度強化學習調度方法。首先，actor網絡參數化策略根據當前系統狀態選擇調度動作，同時critic網絡對當前系統狀態給出評分；然后，使用梯度上升的方式來更新actor策略網絡，其中使用了critic網絡的評分來計算動作的優劣；最后，使用了兩個真實的業務數據集進行模擬實驗。結果顯示，與經典的策略梯度算法以及五個啟發式任務調度方法相比，該方法可以提高云數據中心的資源利用率并縮短離線任務的完工時間，能更好地適應動態的電子政務云環境。

關鍵詞：電子政務； 云計算； 任務調度； 深度強化學習； 演員評論家算法

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

文章編號：1001-3695（2024）06-028-1797-06

doi：10.19734/j.issn.1001-3695.2023.10.0527

Scheduling of dynamic tasks in e-government clouds usingdeep reinforcement learning

Abstract：The task scheduling of e-government cloud center has always9TdnChA4fnls8NrqKYBRLQ== been a complex problem. Most existing task scheduling solutions rely on expert knowledge and are not versatile enough to deal with dynamic cloud environment， which often leads to low resource utilization and degradation of quality-of-service， resulting in longer makespan. To address this issue，this paper proposed a deep reinforcement learning（DRL） scheduling algorithm based on the actor-critic（A2C） mechanism. Firstly， the actor network parameterized the policy and chose scheduling actions based on the current system state， while the critic network assigned scores to the current system state. Then， it updated the actor policy network using gradient ascent， utilizing the scores from the critic network to determine the effectiveness of actions. Finally，it conducted simulation experiments using real data from production datacenters. The results show that this method can improve resource utilization in cloud datacenters and reduce the makespan in comparison to the classic policy gradient algorithm and five commonly used heuristic task scheduling methods. This evidence suggests that the proposed method is superiorly adapted for the dynamic e-government clouds.

Key words：e-government; cloud computing; task scheduling; deep reinforcement learning; actor-critic

0 引言

經過近20年的發展，云計算［1］已經成為主流的計算模式，為大數據、人工智能、5G等新技術提供算力支持。相應地，國內外機構、實體也建設了大量的云數據中心，為各種各樣的計算場景和服務提供基礎設施。電子政務云就是面向電子政務應用場景的云計算系統，承載政務信息與數據的分析處理任務，并提供相應的服務功能［2］。

在云計算中，任務調度是分配服務器的計算資源以滿足任務請求的過程。高效的調度方法不僅可以提高服務質量，還可以提高數據中心的資源利用率，以降低能耗和成本。因此，設計云數據中心任務調度的解決方案是有意義的，但這是一項具有挑戰性的任務。首先，不同的任務具有不同的持續時間和異構的資源需求；其次，云數據中心的可用資源和任務負載都會隨時間而變化［3］，這些因素增加了任務調度問題的復雜性。

與一般的互聯網應用云場景相比，電子政務云的計算任務更多樣，用戶需求更復雜，因此其數據中心的任務調度更具有挑戰性。具體來說，電子政務云中會運行各種在線服務和離線任務，是一種典型的混部形態［4］。

在線服務運行周期較長，對時延要求較高，而且資源使用情況會受到使用習慣的影響，相應地計算需求會呈現比較大的波動性。而離線任務通常是對時延不敏感的計算密集型任務，會盡可能地利用計算資源，對時效性要求不高，通常支持失敗重啟。兩類任務共同部署可以形成互補效應，提高資源的整體效率。但是，由于在線和離線任務的相互干擾，混部形態使得電子政務云的計算任務調度變得更加復雜。

傳統的基于規則、啟發式、元啟發式［5］和控制理論［6］的任務調度方法有很多經典的解決方案。Pradhan等人［7］提出了一種改進的循環資源分配算法，目標是減少任務的等待時間。文獻［8］通過為數據中心網絡設計能源感知模塊和地理負載平衡方案來減少數據中心的能源消耗。文獻［9］提出了一種解決Web服務組合問題的線性編程方法，在地理分布式云環境中為每個任務請求選擇最高效的服務，以提高QoS標準。文獻［10］使用基于規則的控制方法來設計功率感知作業調度程序，以提高功率效率并滿足功率限制。受粒子群算法的啟發，Kumar等人［11］提出了PSO-COGENT算法，不僅優化了執行成本和時間，還降低了云數據中心的能耗。文獻［12］使用了一種受自然啟發的元啟發式方法，通過關閉閑置的主機來保持云環境中性能和能耗之間的平衡。

盡管這些解決方案可以在一定程度上解決任務調度問題，但它們在很大程度上依賴于先驗知識來制定相應的策略。因此，這些解決方案可能在特定場景下運行良好，卻無法適應動態的計算場景和環境，例如復雜性較高的電子政務云環境。

以上傳統的任務調度方法中，基于控制理論的方法和元啟發式方法在得到任務調度方案前，需要經過大量的迭代計算，計算復雜度很高，開銷很大。所以此類方法只適用于靜態的調度環境，也就是待執行任務都是已知且固定的情況，并不適用于請求任務會不斷到達的電子政務云環境。基于規則的方法或者啟發式方法，則會根據固定的規則或流程進行計算選擇，最后得到調度方案。但這些規則和流程是專家基于云的各種特點而設計出來的，比如對請求任務進行分類，相互干擾比較強的任務不部署在同一臺機器等。電子政務云中同時部署了在線任務和離線任務，在線任務長期在云中并且占用的資源會隨時間進行波動，離線任務的到達也具有隨機性，這種情況下，想要設計一個總體效果較好的啟發式算法非常困難。但強化學習（reinforcement learning）［13］的思想能很好地解決此類問題。強化學習的模型能夠與環境交互并且給出決策。通過優化機制，模型在與環境交互的過程中，能夠學習和理解環境的信息，作出越來越優的決策。在使用強化學習方法的整個過程中，并不需要對環境擁有先驗知識，模型是在訓練中自動地獲取這些知識。

傳統的強化學習方法已經成為解決低復雜性的調度問題的一種有效方法。然而，傳統的強化學習方法在高維狀態空間中并不有效，譬如云數據中心的調度場景。為了解決這個問題，深度強化學習［14］使用了深度神經網絡來表示高維信息。目前已經有一些基于 DRL 的方法專注于任務調度問題，其中大多數可以分為基于價值的 DRL［15～18］和基于策略的DRL ［19，20］兩類。

對于基于價值的 DRL，經典的算法就是深度Q網絡（deep Q network，DQN）［21］，它根據狀態值和轉移概率學習策略。文獻［15］使用DQN算法來處理云環境中有向無環圖（DAG）任務的調度問題。文獻［18］基于DQN算法，通過設計與作業的成本、響應時間、執行時間有關的獎勵函數來實現高QoS。然而，在電子政務云數據中心中，任務不斷到達，狀態空間可能相當大且是動態變化的。因此基于價值的深度強化學習模型很難快速收斂到較優解。相比之下，基于策略的DRL，如策略梯度算法（policy gradinet，PG）［22］，可以直接輸出動作的概率分布，能更好地學習到大動作空間中的優化策略。文獻［19］利用基于策略的DRL算法來處理云數據中心的資源分配問題。文獻［20］基于PG算法開發了QoS感知調度器，旨在提高云計算中執行深度神經網絡推理工作任務時的QoS。但經典的策略梯度方法在估計策略梯度時會產生較高的方差，從而影響訓練效率，甚至導致模型不收斂。

作為基于價值和基于策略的DRL算法的綜合應用，演員評論家算法（actor-critic，A2C）旨在解決上述問題。在A2C中，actor是基于策略的模型，critic是基于價值的模型，actor根據critic評估的結果去更新參數，以減少策略梯度的方差［23］。受A2C的啟發，本文設計了一種基于A2C的數據中心任務調度方法（actor-critor task scheduling，AC-TS），以適應電子政務云的動態性。為了體現電子政務云環境的動態性，仿真實驗中的集群環境會同時處理在線任務和離線任務。在線任務是指那些需要長時間占用服務器資源的任務，通常不會終止。這類任務對服務時延比較敏感，數據中心往往需要在短時間內作出響應，而且資源使用情況容易產生波動。例如各種政務信息公開網站提供的檢索服務、各種業務辦理系統或者應急系統的后臺管理服務等。而離線任務通常不需要立刻將結果或消息返回給用戶，如果任務失敗，還可以接受任務重啟，對時效性的要求相對較低，比如輿情分析任務等。這類任務大多是一些計算密集型任務，例如 MapReduce 任務。在線任務一直在服務器上運行，不同時間、不同任務的資源使用模式不同，使得在線任務的負載具有較大波動性。因而集群保留給離線任務的資源量也時時刻刻處于變化之中，這一定程度上體現了云環境的動態性。

由于離線任務不能擠占在線任務的資源，所以在調度時，除了要考慮當前數據中心內資源的可用情況，還要考慮在線任務未來的負載變化，保留一部分資源以應對在線任務的突發負載，盡量減少離線任務被殺掉重啟的狀況。本文所提方法解決的問題是，在云數據中心運行著一定量在線任務的情況下，對資源需求和資源占用時間已知的離線任務進行調度，以提高數據中心的資源利用率。本文針對具有動態性的電子政務云環境（受在線任務影響）和異構需求的用戶任務（不同的離線任務）設計系統調度模型，以CPU利用率、內存利用率和完工時間為優化目標。基于A2C算法，定義了所提調度模型中相關的狀態空間、動作空間和獎勵函數，并利用電子政務云產生的真實數據集進行了仿真實驗，驗證其有效性。

1 系統模型描述

本文抽象出了一種電子政務云數據中心的任務調度系統，該仿真系統的目標是提高集群資源利用率、縮短完工時間。系統模型結構如圖1所示。

用戶按照自己的需求將任務提交給數據中心。如果是在線任務，就需要長時間占用數據中心的資源；離線任務則需要在任務隊列中進行排隊，等待數據中心的調度。數據中心有多個模塊，它們共同協作，一起負責任務的調度。通過任務監控模塊，數據中心可以實時了解用戶所提交的任務的信息，包括任務的執行時間、資源需求量等；通過資源監控模塊，數據中心可以了解當前集群的資源使用情況，比如當前集群的資源利用率、每臺服務器的資源清單、剩余資源量等；服務管理模塊需要對用戶所提交的任務進行監測，尤其是對在線任務，要保證服務的質量不受影響。任務調度器是一個基于DRL的代理，它接收到集群的狀態信息后，生成調度決策并將任務序列中的任務分配給服務器。

為了闡明系統模型，本文考慮具有多個服務器的云數據中心。云數據中心的服務器數量為M，第m臺服務器所擁有的資源量為Rm，如果服務器有多種類型的資源可供使用，比如資源類型數為N，則服務器上的資源清單可以表示為Rm=［R1，R2，…，RN］，本文只考慮CPU資源和內存資源，因此N=2。

對于在線任務，由于其需要長時間占用服務器的一部分資源，并且其使用的資源量隨時間動態變化，所以每個在線任務的資源占用量是一條波動的曲線。在仿真系統中，本文假設每臺服務器上部署的在線任務都是固定的（實際生產集群也是如此），并且每個在線任務的資源占用量曲線都是已知的（通過真實數據集的記錄）。因此可通過相加，把第m臺服務器上所有在線任務占用的資源抽象為一條已知的時間序列sm，每個時間點的數據項是N維的，對應不同的資源。

對于具有周期性的在線服務來說，通過一些預測算法可以預測其資源使用曲線。比如文獻［24］通過使用整合移動平均自回歸模型預測Web服務器的資源使用情況，谷歌的Borg系統使用指數平滑方法［25］對在線任務的資源需求進行預測。而近年來，深度學習方法的發展也帶動了資源預測領域的進步［26］。因此使用時間序列sm作為第m臺服務器上在線任務的資源使用曲線是合理的。

將服務器的可用資源量Rm減去在線服務的資源量sm后，就是離線任務可以使用的資源量。AC-TS算法主要解決的就是離線任務的調度問題，重點是如何調度離線8ad07d5a008e0d8f0db03e7aaa359d67任務，使得集群資源利用率盡可能高。假設整個仿真集群從0時刻開始運行，總運行時間為T（仿真實驗中以最后一個離線任務完成的時間，即完工時間作為結束時間T），集群共有M臺機器，第m臺機器的總資源為Rm，該機器上在線任務資源占用曲線為sm。在時刻t，在線任務對服務器m的資源占有量為sm（t）。在整個集群的運行時間T內，用戶提交的總的離線任務共有p個（從真實數據集中選擇p個），記為Jobtotal={J1，J2，…，Jp}。

在數據中心中，用戶提交的第i個離線任務Ji，會先在隊列Q中等待被調度。每次調度時，調度器會從隊列中取出決定調度的任務，部署到相應的服務器上。對于任務Ji，其具體信息包括到達時間Jia，運行時間Jie以及任務的資源需求情況Jir。在調度成功開始執行的時候，任務監控模塊還會記錄任務開始執行的時間Jistart和執行的機器Jim。

任務Ji在時刻t對服務器m占用的資源如式（1）所示。

調度的目標是最大化資源利用率，其本質上是一個最優化問題，所提算法要解決的調度問題可以定義為

受約束于以下條件：

超過除去在線任務后的資源剩余量Rm-sm（t）。

任務等待隊列Q中等待的任務記為Jseq={J1，J2，…，Jq}，其中q表示等待隊列中作業的數量，有q≤p。當一個作業從Jobtotal到達時，它首先要進入任務等待隊列。如果隊列滿了，則在任務到達緩存區等待（假定緩存區無限大）。任務進入等待隊列Q后如果調度器決定調度此任務，該任務會立即開始執行;否則，它將在隊列中等待。在該系統中，不考慮對任務的到達速率作出設置，調度器只能觀察到指定長度的任務等待隊列Q，當任務等待隊列中的任務數量不足時，若任務到達緩存區還有多余的任務，則會對任務等待隊列進行補齊，使其保持在固定長度。如果調度器在當前時刻能夠大量調度任務，那么保持等待隊列長度相當于任務的到達速率增加。當Jobtotal中的任務是固定的情況下，假定集群系統的運行時間T為執行完Jobtotal中所有任務的時間，即任務完工時間。那么提高集群的資源利用率，就相當于減少所有任務的最大完工時間，即最后一個任務的完成時間。

2 AC-TS算法設計

2.1 演員評論家算法

actor-critic算法主要由兩個部分組成。 actor網絡本質上是一個策略梯度模型，它可以在動作空間內選擇一個合適的動作，從而使系統環境轉移到下一個狀態。但普通的策略梯度模型是基于一個完整的動作序列的獎勵值來進行更新的，其學習效率很低。這時候使用一個基于價值的算法模型，如DQN，作為critic網絡來進行輔助，就可以使用TD方法實現actor網絡的單步更新，從而加快模型的訓練速度。actor與critic兩個網絡相互協作就形成了actor-critic算法。Vπ（s）表示馬爾可夫決策過程（Markov decision process，MDP）中的狀態價值函數，它表示從狀態s出發，遵循策略π能獲得的期望反饋獎勵。Qπ（s，a）表示MDP中的動作價值函數，表示對當前狀態s執行動作a得到的期望獎勵。假設當前時刻為t，根據定義有式（4）：

Qπ（st，at）=rt+γVπ（st+1）（4）

其中：γ表示模型的折扣因子;at表示時刻t選擇的動作;st表示時刻t的系統狀態;rt表示動作at的反饋獎勵。

假定策略網絡πθ是一個神經網絡模型，θ是對應的參數，s0是系統環境的初始狀態，在普通的策略梯度方法中，策略學習的目標函數如式（5）所示。

由式（6）可以看出，模型必須采樣一條或者多條完整的軌跡后（和環境交互T步得到的軌跡），根據軌跡中的所有（st，at，rt）記錄，計算出每一個狀態動作對（st，at）的累計獲得獎勵，才能計算梯度，更新網絡。但是在真實的訓練過程中，無法完成足夠數量的采樣，而有限次的采樣并不能很好地代表軌跡真實的期望，會引入較大的方差，這是蒙特卡羅方法的缺陷，沒有偏差但是方差大。為了減少方差，可以引入基線函數b（st），b（st）最好是使用Vπ（st）。所以基于有限采樣的情況下，一般選用st狀態下取得的累計獎勵的平均值作為基線函數值。此時式（6）可以轉換為式（7）。

actor-critic算法的主要思想就是引入基于DQN的critic網絡作為評分網絡。actor網絡是一個如上所述的策略梯度模型。actor網絡每次計算梯度，更新網絡，狀態動作對（st，at）的累計獎勵用critic網絡輸出的狀態價值來表示。并且critic網絡通過仿真系統反饋的真實rt值來訓練自身，使得critic網絡精度越來越高。

將critic價值網絡表示為狀態價值函數Vω，其中ω表示網絡參數。Vω（st）表示在系統狀態st下，critic網絡輸出該狀態的期望價值。通過時序差分（temporal difference）［27］的方法，并且使b（st）=Vω（st），可以得到式（8）。此時式（7）可以轉換為式（9），雖然引入了一定的估計偏差，但降低了采樣數據的方差的影響。

在actor網絡的優化更新過程中，critic網絡也需要優化更新。critic網絡可以直接使用均方誤差作為損失函數，如式（10）所示。其中rt+γVω（st+1）作為真值，Vω（st）作為預測值。求導可得梯度計算的方式如式（11）所示，使用梯度下降方法來更新參數即可。

2.2 狀態空間設置

假定云集群的服務器數量為M，集群內的可用資源種類為N，對于第m個服務器，在時刻t，其可用資源為Rmt=［r1t，r2t，…，rNt］。因此在時刻t，集群的服務器狀態信息可以表示為sMt=［R1t，R2t，…，RMt］。假定時刻t，任務等待隊列中的任務數為J，對于任務隊列中的離線任務j，其任務的運行時間為ej，所需要的計算資源為reqj=［r1j，r2j，…，rNj］，任務自提交到任務隊列Q后，其等待時間為wj。則時刻t，所有離線任務狀態信息為sJt=［req1，…，reqJ，w1，w2，…，wJ，e1，e2，…，eJ］。將所有服務器的狀態信息和任務等待隊列中所有任務的狀態信息拼接起來就是整個系統的當前狀態。所以在時刻t的系統狀態表示為st=［sMt，sJt］。

2.3 動作空間

算法的狀態空間是智能體所能執行的動作集合。在前面所述的調度系統模型中，智能體充當調度器的作用。智能體的動作是將任務和服務器進行匹配，所以輸出的動作是任務和服務器的元組，即（n，m），表示將任務n分配至服務器m。在調度過程中，如果智能體要通過一次決策將所有N個任務調度到相應的服務器上，那么解空間的大小為NM，很明顯，這一搜索空間的數量級是指數級的。對此，AC-TS將一個時間步的調度決策分解為一串序貫決策，也就是智能體的一次決策是為隊列中某個任務從M個服務器中選擇一個服務器進行運行。而在每次調度，智能體可以執行多次決策，對多個任務進行匹配，從而調度多個任務，直至無法調度。假設當前等待隊列有J個任務，并且觸發了調度，則該次調度過程中，強化學習模型實際上連續作出了J次動作決策，每次的動作at都是針對單個任務。此時調度動作的空間大小可以減小為M。

需要注意的是，在調度過程中，智能體可能不會把每個任務都選擇調度到服務器上運行。出于對任務調度整體的考慮，可能會選擇不調度當前的任務。所以在動作空間內需要加入一個維度，表示不執行調度的動作，因此動作空間可以表示為A={at|at∈［0，1，2，…，M］}，at=0代表不執行調度，動作空間的大小為（M+1）。

2.4 獎勵函數

2.1節中有說到每次智能體作出一次決策，仿真環境必須給出一個實時的動作反饋獎勵r。該獎勵是根據具體任務、優化目標等因素，由人工設計的，目的是指導智能體更好地學習。

實時動作反饋獎勵一般由函數給出，該函數稱作獎勵函數。為了智能體代理能學習到更好的任務調度策略，對獎勵函數進行設計時，要考慮到整個調度過程。可以預想到，對數據中心的資源利用率來說，如果能夠將任務盡早地調度到服務器上進行處理，那么集群內的資源碎片就會盡可能少，從而提高集群的資源利用率。那么，為了提高集群的資源利用率，要使整個調度過程的時間盡可能縮短，也就是縮短任務的等待時間。同時要考慮到任務所需資源量的影響，因為智能體可能會將資源需求量大、執行時間長的任務放置在任務隊列中持續等待，所以應該提高調度大任務的動作的反饋獎勵，從而使得智能體代理考慮調度等待時間較長的大任務。

基于以上的考量，每成功調度一個任務j，得到的反饋獎勵rj如式（12）所示。

用等待時間wj來反映完工時間的重要性。智能體代理需要學會讓完工時間盡可能短，因此每個任務的等待時間越小越好，獎勵與任務的等待時間wj呈負相關。為了避免智能體代理傾向于分配少資源且執行時間短的任務，將執行時間ej放在括號里面分子位置上，括號里面是執行時間和等待時間的比值，通過一個對數計算，使得該值映射到實數域。最后再乘以資源需求reqj。本文考慮CPU和內存資源，因此該值具體計算時為CPU資源需求乘以內存資源需求，為一個標量。反饋獎勵與執行時間ej、資源需求reqj正相關。智能體會選擇調度具有更多獎勵的任務，而不僅僅是資源需求少、執行時間短的任務。當智能體選擇不執行調度或調度失敗時，反饋獎勵為0。

2.5 模型訓練

基于第1章所述的仿真環境，使用AC-TS作為仿真環境中的調度器，在調度過程中對其進行訓練。每次調度的時間間隔是一個超參數。本文對數據集中的離線任務數據進行了分析，發現90%的離線任務執行時間處于幾秒到幾百秒的區間內，所以選擇了每30 s進行一次調度。

每次宏觀的調度中，智能體根據當前系統狀態st，針對當前所選任務，選擇一個動作at，如果該動作表示不執行調度，則反饋獎勵為0。如果執行調度，則仿真系統會嘗試把任務調度到對應機器上。如果調度成功，則反饋獎勵由式（12）計算。如果服務器資源不足調度失敗，反饋獎勵則為0，并且該任務重新返回等待隊列。接著系統進入下一個狀態st+1，智能體針對下一個任務作出動作at+1。當智能體對當前等待隊列中的所有任務都作出決策動作后，仿真系統會進入到下一次調度，也就是30 s后，此時集群資源和等待隊列都會有新的狀態。

基于所選用的狀態空間、動作空間及獎勵函數，AC-TS算法的步驟如算法1所示。其中：epoch為訓練輪數，每一輪為一次完整的執行所有離線任務的過程；J代表每一次觸發調度時，等待隊列中的離線任務個數。第10、11步的更新網絡公式具體如式（9）（11）所示。

算法1 基于A2C的調度算法流程

3 實驗驗證

3.1 系統模型參數

本文的仿真實驗基于真實電子政務云集群上記錄的兩個日志數據集。其中在線應用包括各種政府信息公開網站、政務服務網站、政務服務小程序的后臺服務程序，還有一些政府內部的管理系統、業務辦理系統等。而離線應用則有輿情分析、政務大數據搜索任務、政務大數據的數據挖掘任務等。

日志數據集中，對于在線任務，數據集記錄了2萬多個時間點的在線任務資源占用量。對于離線任務，則記錄了大量的任務信息，包括任務的執行時間、所需資源量等， 一般離線任務的運行時間有限，所以過濾了運行時間大于1 000 s的離線任務。對于服務器集群，本文設置10臺同構模擬服務器，為計算任務提供CPU和內存兩種資源，智能體所能觀察到的任務隊列的長度為200，每臺服務器的CPU數量為10，內存大小為4。

而A2C調度模型中，一些相關的超參數如表1所示。基于這些設置，本文進行了大量的模擬實驗來評估所提算法的性能。

3.2 實驗環境

本實驗所使用的硬件和軟件配置如下：CPU為12核Intel CoreTM i7-8700K 3.70 GHz CPU；內存為32 GB DDR4內存；Python版本為3.8.5；算法模型由PyTorch 1.12.1實現，使用CPU進行訓練。

3.3 對比算法介紹

為了評估云數據中心任務調度算法，在同一系統中采用了幾種啟發式方法和經典的策略梯度算法。a）首次適應（first fit）：將任務分配給第一個滿足資源需求的服務器；b）隨機調度（random）：調度器從所有滿足任務資源需求的服務器中，隨機選擇一個服務器來執行任務；c）最短任務優先（shortest first）：優先執行等待隊列中執行時間最短的任務；d）最小成本優先（mincost first）：將任務的執行時間與所需資源量相乘得到成本值，再更具成本值排序，優先執行成本小的任務；e）循環執行（round robin）：各個機器循環地執行等待隊列中的任務；f）策略梯度（policy gradient）［28］：基于深度強化學習的方法，調度動作由策略神經網絡輸出的概率分布確定，通過蒙特卡羅方法采樣數據進行更新。

3.4 模型收斂效果

如果所提模型經過多輪訓練依舊不能收斂到一個較優的結果，則說明該模型不適合處理該任務，無法通過訓練自主學習到處理該任務的相關知識。此外，不能收斂還有可能是模型之外的一些超參數配置所導致。為了評估所提調度算法的收斂性，即算法的有效性，本文通過實驗觀察了模型的收斂效果，如圖2、3所示。橫坐標為每一次仿真所得到的總體獎勵得分，也就是調度完所有離線任務得到的總分。可以看出，模型最終都能收斂到穩定的結果。

本文還分析了兩個基本參數對模型收斂的影響，包括actor網絡的學習率γa和critic網絡的學習率γc，通過實驗，最終選擇了兩個效果較優的數值進行后續實驗。

首先，將γa固定設置為0.000 3，γc的值分別設置為0.001、0.003和0.005。如圖2所示，雖然當γc為0.005時曲線收斂得更快，但在400個epoch后，總體來看，γc為0.003時調度過程的累積獎勵略高。由于γc為0.003時獎勵較高且較穩定，所以在后續的實驗中把γc的值固定設置為0.003。幾條不同γc值的曲線，都在訓練開始時呈下降趨勢，但經過幾個epoch后，趨勢發生逆轉，累計獎勵慢慢提升。這意味著智能體可以通過更新網絡參數來探索更高的調度獎勵，AC-TS算法在該場景下是有效的。

接下來，把γc的值固定為0.003，γa分別設置為0.001、0.000 1、0.000 3、0.000 5。如圖3所示，與其他值相比，當γa為0.000 3時，獎勵曲線收斂得最快，而且可以獲得較高的獎勵且比較穩定。當γa為0.001時，曲線需要很長時間才能收斂，并且最終獎勵比任何其他值都小。因此，接下來的實驗選用0.000 3作為γa的值。

3.5 不同任務數量下的調度過程比較

所提A2C任務調度算法性能將通過以下幾個指標進行評估：完工時間、CPU利用率和內存利用率。實驗過程中改變調度過程的總任務數量，并將所提算法與3.3節提到的其他方法進行比較。從圖4（a）可以看出，在任務量為500時， AC-TS和其他算法的最大完工時間相差不大，甚至略大于策略梯度算法，其原因是任務隊列中的任務量較少，集群資源相對充足，調度過程的優化也有限。

隨著任務數量的增加，AC-TS可以考慮到整體任務之間的影響，總是能達到這些方法中最低的完工時間。當任務數大于1 500時，AC-TC的完工時間明顯小于其他方法；尤其是任務量從2 000增加到2 500時，其最大完工時間的上升幅度較其他算法明顯下降。

圖4（b）（c）中CPU和內存的利用率隨著任務數量的增加而升高，而所提AC-TS算法的資源利用率總是這些方法里面最高的，體現了AC-TS對這種動態性的云調度場景的有效性。

4 結束語

為了解決電子政務云數據中心的計算任務調度問題，抽象出了一種含有動態性的任務調度系統，并且提出了一種基于深度強化學習的AC-TS方法用于調度。對于該方法，在不同的任務數量規模下進行實驗驗證并和其他方法對比，結果表明：AC-TS在動態云環境中的任務調度優于幾種經典的啟發式方法和普通強化學習算法，并且任務數量規模越大，優化效果越好。本文合理地把單個時間片內的任務調度過程抽象為MDP中多次決策的過程，有效地減少了算法的動作空間大小，并且在獎勵函數的設置中，綜合考慮多個與調度目標有關的因素，使得AC-TS算法可以有效地進行訓練，獲得較好的性能。

除了在線任務導致的電子政務云環境的動態變化，還有其他多種影響任務調度的因素。比如多云的任務調度，除了考慮任務所需要的資源，還需要考慮一些其他因素比如數據中心的異構資源、負載均衡等。此外，還有更復雜的任務類型，比如工作流任務。工作流任務的子任務之間是有依賴關系的，它們的調度問題復雜性更高，在動態環境下調度它們具有更大的挑戰性，這些都是進一步研究的方向。

參考文獻：

［1］Rahimikhanghah A， Tajkey M， Rezazadeh B， et al. Resource sche-duling methods in cloud and fog computing environments： a systematic literature review［J］. Cluster Computing， 2022，25： 1-35.

［2］王會金， 劉國城. 大數據時代電子政務云安全審計策略構建研究［J］. 審計與經濟研究， 2021，36（4）： 1-9. （Wang Huijin， Liu Guocheng. Research on the construction of e-government cloud secu-rity audit strategy in the era of big data［J］. Audit and Economic Research， 2021，36（4）： 1-9.）

［3］Chen Zheyi， Hu Jia， Min Geyong， et al. Towards accurate prediction for high-dimensional and highly-variable cloud workloads with deep learning［J］. IEEE Trans on Parallel and Distributed Systems， 2019，31（4）： 923-934.

［4］Zhan Yong， Ghamkhari M， Akhavan-Hejazi H， et al. Cost-aware traffic management under demand uncertainty from a colocation data center user’s perspective［J］. IEEE Trans on Services Computing， 2018，14（2）： 400-412.

［5］Nekooei-Joghdani A， Safi-Esfahani F. Dynamic scheduling of independent tasks in cloud computing applying a new hybrid metaheuristic algorithm including Gabor filter， opposition-based learning， multi-verse optimizer， and multi-tracker optimization algorithms［J］. The Journal of Supercomputing， 2022，78（1）： 1182-1243.

［6］Avgeris M， Dechouniotis D， Athanasopoulos N， et al. Adaptive resource allocation for computation offloading： a control-theoretic approach［J］. ACM Trans on Internet Technology， 2019，19（2）： 1-20.

［7］Pradhan P， Behera P K， Ray B N B. Modified round robin algorithm for resource allocation in cloud computing［J］. Procedia Computer Science， 2016，85： 878-890.

［8］Chen Tianyi， Marques A G， Giannakis G B. DGLB： distributed stochastic geographical load balancing over cloud networks［J］. IEEE Trans on Parallel and Distributed Systems， 2016，28（7）： 1866-1880.

［9］Ghobaei-Arani M， Souri A. LP-WSC： a linear programming approach for Web service composition in geographically distributed cloud environments［J］. The Journal of Supercomputing， 2019，75（5）： 2603-2628.

［10］Wang Jun， Han Dezhi， Wang Rruijun. A new rule-based power-aware job scheduler for supercomputers［J］. The Journal of Supercomputing， 2018，74： 2508-2527.

［11］Kumar M， Sharma S C. PSO-COGENT： cost and energy efficient scheduling in cloud environment with deadline constraint［J］. Sustainable Computing： Informatics and Systems， 2018，19： 147-164.

［12］Medara R， Singh R S. Energy-aware workflow task scheduling in clouds with virtual machine consolidation using discrete water wave optimization［J］. Simulation Modelling Practice and Theory， 2021，110： 102323.

［13］Daoun D， Ibnat F， Alom Z， et al. Reinforcement learning： a friendly introduction［C］//Proc of International Conference on Deep Lear-ning， Big Data and Blockchain. Cham： Springer International Publishing， 2021： 134-146.

［14］Franois-Lavet V， Henderson P， Islam R， et al. An introduction to deep reinforcement learning［J］. Foundations and Trends in Machine Learning， 2018，11（3-4）：219-354.

［15］Bi Jing， Yu Zhou， Yuan Haitao. Cost-optimized task scheduling with improved deep Q-learning in green data centers［C］//Proc of IEEE International Conference on Systems， Man， and Cybernetics. Pisca-taway，NJ：IEEE Press， 2022： 556-561.

［16］Tong Zhao， Chen Hongjian， Deng Xiaomei， et al. A scheduling scheme in the cloud computing environment using deep Q-learning［J］. Information Sciences， 2020，512： 1170-1191.

［17］Ding Ding， Fan Xiaocong， Zhao Yihuan， et al. Q-learning based dynamic task scheduling for energy-efficient cloud computing［J］. Future Generation Computer Systems， 2020， 108： 361-371.

［18］Cheng Long， Kalapgar A， Jain A， et al. Cost-aware real-time job scheduling for hybrid cloud using deep reinforcement learning［J］. Neural Computing and Applications， 2022，34（21）： 18579-18593.

［19］Mao Hongzi， Alizadeh M， Menache I， et al. Resource management with deep reinforcement learning［C］//Proc of the 15th ACM Workshop on Hot Topics in Networks. New York：ACM Press，2016： 50-56.

［20］Fang Zhou， Yu Tong， Mengshoel O J， et al. QoS-aware scheduling of heterogeneous servers for inference in deep neural networks［C］//Proc of ACM on Conference on Information and Knowledge Management. New York：ACM Press，2017： 2067-2070.

［21］Mnih V， Kavukcuoglu K， Silver D， et al. Human-level control through deep reinforcement learning［J］. Nature， 2015，518（7540）： 529-533.

［22］Sutton R S， McAllester D， Singh S， et al. Policy gradient methods for reinforcement learning with function approximation［C］//Proc of the 12th Internation Conference on Neural Information Processing System. Cambridge， MA：MIT Press， 1999：1057-1063.

［23］Cui Haoran， Wang Dongyu， Li Qi， et al. A2C deep reinforcement learning-based MEC network for offloading and resource allocation［C］//Proc of the 7th International Conference on Computer and Communications. Piscataway，NJ：IEEE Press，2021： 1905-1909.

［24］Calheiros R N， Masoumi E， Ranjan R， et al. Workload prediction using ARIMA model and its impact on cloud applications’QoS［J］. IEEE Trans on Cloud Computing， 2014，3（4）： 449-458.

［25］Rzadca K， Findeisen P， Swiderski J， et al. Autopilot： workload autoscaling at Google［C］//Proc of the 15th European Conference on Computer Systems. New York：ACM Press， 2020： 1-16.

［26］Liu Minhao， Zeng Ailing， Xu Zhijian， et al. Time series is a special sequence： forecasting with sample convolution and interaction［EB/OL］. （2021）. https：//arxiv.org/abs/2106.09305.

［27］Sutton R S. Learning to predict by the methods of temporal differences［J］. Machine Learning， 1988， 3： 9-44.

［28］陳中柘， 劉宇， 朱順鵬，等. 基于深度強化學習的柔性車間動態調度方法及仿真［J］. 實驗室研究與探索， 2023，42（4）： 107-111，117. （Chen Zhongzhe， Liu Yu， Zhu Shunpeng et al. Flexible workshop dynamic scheduling method and simulation based on deep reinforcement learning［J］. Laboratory Research and Exploration， 2023，42（4）： 107-111，117.）