# A Deep Reinforcement Learning Approach to the Optimization of Data Center Task Scheduling

Authors: Haiying Che; Zixing Bai; Rong Zuo; Honglei Li
Journal: Complexity
 (2020)

---

## Abstract

With more businesses are running online, the scale of data centers is increasing dramatically. The task-scheduling operation with traditional heuristic algorithms is facing the challenges of uncertainty and complexity of the data center environment. It is urgent to use new technology to optimize the task scheduling to ensure the efficient task execution. This study aimed at building a new scheduling model with deep reinforcement learning algorithm, which integrated the task scheduling with resource-utilization optimization. The proposed scheduling model was trained, tested, and compared with classical scheduling algorithms on real data center datasets in experiments to show the effectiveness and efficiency. The experiment report showed that the proposed algorithm worked better than the compared classical algorithms in the key performance metrics: average delay time of tasks, task distribution in different delay time levels, and task congestion degree.


---

## Body

## 1. Introduction

For the data centers with a huge number of servers, even a little bit improvement of the operation can save millions of dollars. Good task scheduling has been proved to be a practical way to bring benefits without extra hardware investment. Today’s data center scheduling systems mostly use heuristic algorithms such as Fair Scheduling (Fair), First-Come-First-Service (FCFS) scheduling, and Shortest-Job-First (SJF) scheduling. These algorithms are easy to understand and implement but only take effects in some certain situations due to the limitation of the complicated production environment. The challenges of data center scheduling in the real world are as follows:(1)
The data center environment is complex and dynamically changing. To achieve efficient and effective scheduling, traditional heuristic algorithms mostly rely on precise environment modeling. In other words, if the environment cannot be accurately modeled, the reasonable and effective scheduling algorithm will not be successfully applied. Therefore, most data center scheduling algorithms still use basic and simple heuristic algorithms, such as Fair, FCFS, and SJF. Practically, it is too hard to model the environment precisely due to the uncertainty of the coming tasks and the dynamic environment. For example, the execution time of a task is affected by network bandwidth, the processing performance of different machines, the disk speed, and the location of the required resources to support the task execution.(2)
Data center scheduling is usually performed without sufficient information support. There are no patterns to predict the task arriving way. That is, the number and size of tasks coming next are unknown. So, the algorithm has to schedule the tasks at once without any prior experience and prepared information.(3)
Resource requirements change dynamically. For data center services or tasks, the demand for resources varies according to different time period, environmental conditions, and so on. The scheduling algorithm needs automatically optimize resource utilization based on the changing demand.In order to solve the above problems, a lot of related studies are carried out. Most of them focus on specific scheduling scenarios or rely on the acquired details of the coming tasks in advance. In addition, most of the previous studies are single objective optimization-oriented.In recent years, the deep reinforcement learning [1, 2] which achieves outstanding performance in complex control fields strongly shows its superiority of decision making in complex and unknown environments. Mao et al. tried to translate the problem of packing tasks with multiple resource demands into a learning problem. Their work shows that deep reinforcement learning performs comparably to state-of-the-art heuristics, adapts to different conditions, converges quickly, and learns strategies that are sensible in hindsight [3]. Inspired by these research results, we believe that deep reinforcement learning is suitable for task scheduling of data centers in complex production environments. This paper proposed a method based on deep reinforcement learning to improve task scheduling performance and resource utilization of data centers. With the neural network model trained through deep reinforcement learning, tasks scheduling and resource utilization improvement were achieved.In this study, we used deep reinforcement learning and aimed at two objectives: minimizing the average task completion time and improving resource utilization efficiency without any prior knowledge of the coming tasks. The experiments and verification were performed using real production data from the Alibaba Cluster Trace Program sponsored by Alibaba Group [4]. The results showed that compared with the traditional heuristic algorithms, the proposed method achieved better performance.This paper is organized as follows. In Section2, related studies were discussed. Reinforcement learning-based scheduling as the prevailing technology used in task scheduling of the data center was introduced. In Section 3, the technical architecture and related definitions of the scheduling system proposed in this paper were illustrated. In Section 4, the reinforcement learning algorithm for scheduling optimization was introduced in detail. In Section 5, experiments were performed on Alibaba real production dataset to show the advantage of the proposed scheduling model. In the last section, the conclusion and future work were discussed.


## 2. Related Studies

For data center task scheduling, many studies have been launched in the past decade. Heuristic algorithms and reinforcement learning are popular in this domain.


### 2.1. Heuristic Algorithm-Based Studies

The traditional methods are mainly based on heuristic algorithms. Typically, Delimitrou and Kozyrakis proposed the ARQ algorithm, a multiclass admission control protocol that constrains application waiting time and limits application latency to achieve QoS [5]. They evaluated the algorithm with a wide range of workload scenarios, on both small- and large-scale systems and found that it enforces performance guarantees for 91 percent of applications, while the utilization is improved. Perry et al. proposed a Fastpass algorithm to improve data center transmission efficiency [6]. Fastpass incorporates two fast algorithms: the first determines the time at which each packet should be transmitted, while the second determines the path used for that packet. They deployed and evaluated Fastpass in a portion of Facebook’s data center network, which shows that Fastpass achieves better efficiency in transmission. Tseng et al. argued that previous studies have typically focused on modifying the original TCP or increasing additional switch hardware costs, and rarely focused on the existing data center network (DCN) environments. So, they proposed a cross-layer flow schedule with a dynamic grouping (CLFS-DG) algorithm to reduce the effect of TCP incast in DCNs [7]. Yuan et al. solved the cost optimization problem under CDCs (cloud data centers) from two aspects. Firstly, a revenue-based workload admission control method is proposed to selectively accept requests. Then, a cost-aware workload scheduling method is proposed to allocate requests among multiple Internet service providers connected to the distributed CDCs. Finally, intelligent scheduling requests are realized, which can achieve lower cost and higher throughput for CDC providers [8]. Yuan et al. proposed the profit maximization algorithm (PMA) for the profit maximization challenge in the hybrid cloud scenario. The algorithm uses the hybrid heuristic optimization algorithm to simulate annealing particle swarm optimization (SAPSO) to improve the throughput and profit of private cloud [9]. Bi et al. proposed a new dynamic hybrid meta heuristic algorithm based on simulated annealing and particle swarm optimization (PSO) for minimizing energy cost and maximizing revenue of various applications running in virtualized cloud data centers [10]. Yuan et al. proposed a heuristic time scheduling algorithm (TTSA) to minimize the cost of private cloud data centers in hybrid cloud, which can effectively improve the throughput of private cloud data centers [11]. Yuan et al. proposed a biological target differential evolution algorithm (SBDE) based on simulated annealing, aiming at the challenges of maximizing profit and minimizing the probability of average task loss in distributed green data centers scenario. Compared with several existing scheduling algorithms, SBDE achieves greater benefits [12].With the development of data centers, reasonable prediction is very important to improve the efficiency of task scheduling. Although prediction is not involved in the experiment, it is necessary to predict the execution time when the model is transferred to the actual scene. Zhang et al. (2018) proposed an integrated forecasting method equipped with noise filtering and data frequency representation, named Savitzky–Golay and wavelet-supported stochastic configuration networks (SGW-SCNs) [13]. Bi et al. also proposed an integrated forecasting method that combines Savitzky–Golay filtering and wavelet decomposition with stochastic configuration networks to get the workload forecast in the next period [14]. Bi et al. proposed an integrated prediction method that combines the Savitzky–Golay filter and wavelet decomposition with stochastic configuration networks to predict workload at the next time slot [15].Although the previous research results are quite abundant, Luo et al. argued that not only because the scheduling problem is theoretically NP-hard, but also because it is tough to perform practical flow scheduling in large-scale DCNs. It is quite challenging to minimize the task completion time in today’s DCNs [16]. That means because of the scalability, complexity, and variability of data center production environment, heuristic algorithms cannot achieve the expected performance even with the deliberated design and exhausting tuning work in real production environment.


### 2.2. Reinforcement Learning-Based Studies

Reinforcement learning [1, 17], as the prevailing machine learning technology, dramatically becomes a new way to the task scheduling of data centers in recent years. Unlike supervised learning which requires amount of manpower and time to prepare the labeled data, reinforcement learning can work with unlabeled data. This so-called model-free mode allows users to start the modeling without the preparation of accurate server environmental data from the scratch. Therefore, at present, more researchers turn to try reinforcement learning to solve task scheduling in complex data center environments. For example, for the purpose of energy saving, Yuan et al. used the Q-learning algorithm to reduce the data center energy consumption. They tested the algorithm in the CloudSim, a cloud computing simulation framework issued by cloud computing, and distributed system laboratory of the University of Melbourne. The result shows that it can reduce about 40% of the energy consumption of the non-power-aware data center and reduce 1.7% energy consumption of the greedy scheduling algorithm in data center scheduling area [18]. Lin et al. used TD-error reinforcement learning to reduce the energy consumption of data centers, which does not rely on any given stationary assumptions of the job arrival and job service processes. The effectiveness of the proposed reinforcement learning-based data center power management framework was verified with real Google cluster data traces [19]. Li et al. also proposed an end-to-end cooling control algorithm (CCA) that is based on the deep deterministic policy gradient algorithm (DDPG) to optimize the control of cooling system in the data center. The result shows that CCA can achieve about 11% cooling cost saving on the simulation platform compared with a manually configured baseline control algorithm [20]. Shaw et al. proposed an advanced reinforcement learning consolidation agent (ARLCA) based on the Sarsa algorithm to reduce cloud energy consumption [21]. Their work proved that the ARLCA makes a significant improvement in energy saving while the number of service violations is reduced.Scholars also apply reinforcement learning to solve the problems on other purposes of the data center task scheduling. Basu et al. applied reinforcement learning to build cost-models on standard online transaction processing datasets [22]. They modeled the execution of queries and updates as a Markov decision process whose states are database configurations, actions are configuration changes, and rewards are functions of the cost of configuration change and query and update evaluation. The approach was empirically and comparatively evaluated on a standard OLTP dataset. The result shows that the approach is competitive with state-of-the-art adaptive index tuning, which is dependent on a cost model. Peng et al. tried Gaussian process regression with reinforcement learning based on the Q-learning algorithm to solve the problem of state-action space incomplete exploration of reinforcement in cloud data centers [23]. The computational results demonstrated that the schema can balance the exploration and exploitation in the learning process and accelerate the convergence to a certain extent. Ruffy et al. presented a new emulator, Iroko, to support different network topologies, congestion control algorithms, and deployment scenarios. Iroko interfaces with the OpenAI Gym toolkit, which allows for fast and fair evaluation of different reinforcement learning and traditional congestion control algorithms under the same conditions [24]. By the way, some scholars try to combine neural network with heuristic algorithm and have achieved valuable research results. For example, He et al. proposed a new strategy iteration method for online H ∞ optimal control law design based on neural network for nonlinear systems. Numerical simulation is carried out to verify the feasibility and applicability of the algorithm [25]. In the next year, a PI algorithm based on neural network was proposed to solve the problem of online adaptive optimal control of nonlinear systems. Two examples were given to illustrate the effectiveness and applicability of the method [26].The above studies show that reinforcement learning can help us to deal with the scheduling problems of data centers in many domains. However, most of them aim at single objective or are based on the ideal hypothesis that the information about the coming tasks and environment are accurate and adequate in advance, which limits the application of the related studies in real production environment.Furthermore, for most of today’s data centers, resources in fixed scale are usually allocated in advance for most business, which is apparently a low-efficiency mode. In fact, the amount of resources required by business may change with time. If we cannot customize the resource amount according to the changing requirement, when more resources are needed, it will cause serious task delay and affect the user experience badly. Or if fewer resources are needed, more unused resources will be wasted. In this article, we proposed reinforcement learning to optimize scheduling efficiency and to improve resource utilization simultaneously. This is a two-objective optimization work which addresses the primary demand of data center operations.


## 2.1. Heuristic Algorithm-Based Studies

The traditional methods are mainly based on heuristic algorithms. Typically, Delimitrou and Kozyrakis proposed the ARQ algorithm, a multiclass admission control protocol that constrains application waiting time and limits application latency to achieve QoS [5]. They evaluated the algorithm with a wide range of workload scenarios, on both small- and large-scale systems and found that it enforces performance guarantees for 91 percent of applications, while the utilization is improved. Perry et al. proposed a Fastpass algorithm to improve data center transmission efficiency [6]. Fastpass incorporates two fast algorithms: the first determines the time at which each packet should be transmitted, while the second determines the path used for that packet. They deployed and evaluated Fastpass in a portion of Facebook’s data center network, which shows that Fastpass achieves better efficiency in transmission. Tseng et al. argued that previous studies have typically focused on modifying the original TCP or increasing additional switch hardware costs, and rarely focused on the existing data center network (DCN) environments. So, they proposed a cross-layer flow schedule with a dynamic grouping (CLFS-DG) algorithm to reduce the effect of TCP incast in DCNs [7]. Yuan et al. solved the cost optimization problem under CDCs (cloud data centers) from two aspects. Firstly, a revenue-based workload admission control method is proposed to selectively accept requests. Then, a cost-aware workload scheduling method is proposed to allocate requests among multiple Internet service providers connected to the distributed CDCs. Finally, intelligent scheduling requests are realized, which can achieve lower cost and higher throughput for CDC providers [8]. Yuan et al. proposed the profit maximization algorithm (PMA) for the profit maximization challenge in the hybrid cloud scenario. The algorithm uses the hybrid heuristic optimization algorithm to simulate annealing particle swarm optimization (SAPSO) to improve the throughput and profit of private cloud [9]. Bi et al. proposed a new dynamic hybrid meta heuristic algorithm based on simulated annealing and particle swarm optimization (PSO) for minimizing energy cost and maximizing revenue of various applications running in virtualized cloud data centers [10]. Yuan et al. proposed a heuristic time scheduling algorithm (TTSA) to minimize the cost of private cloud data centers in hybrid cloud, which can effectively improve the throughput of private cloud data centers [11]. Yuan et al. proposed a biological target differential evolution algorithm (SBDE) based on simulated annealing, aiming at the challenges of maximizing profit and minimizing the probability of average task loss in distributed green data centers scenario. Compared with several existing scheduling algorithms, SBDE achieves greater benefits [12].With the development of data centers, reasonable prediction is very important to improve the efficiency of task scheduling. Although prediction is not involved in the experiment, it is necessary to predict the execution time when the model is transferred to the actual scene. Zhang et al. (2018) proposed an integrated forecasting method equipped with noise filtering and data frequency representation, named Savitzky–Golay and wavelet-supported stochastic configuration networks (SGW-SCNs) [13]. Bi et al. also proposed an integrated forecasting method that combines Savitzky–Golay filtering and wavelet decomposition with stochastic configuration networks to get the workload forecast in the next period [14]. Bi et al. proposed an integrated prediction method that combines the Savitzky–Golay filter and wavelet decomposition with stochastic configuration networks to predict workload at the next time slot [15].Although the previous research results are quite abundant, Luo et al. argued that not only because the scheduling problem is theoretically NP-hard, but also because it is tough to perform practical flow scheduling in large-scale DCNs. It is quite challenging to minimize the task completion time in today’s DCNs [16]. That means because of the scalability, complexity, and variability of data center production environment, heuristic algorithms cannot achieve the expected performance even with the deliberated design and exhausting tuning work in real production environment.


## 2.2. Reinforcement Learning-Based Studies

Reinforcement learning [1, 17], as the prevailing machine learning technology, dramatically becomes a new way to the task scheduling of data centers in recent years. Unlike supervised learning which requires amount of manpower and time to prepare the labeled data, reinforcement learning can work with unlabeled data. This so-called model-free mode allows users to start the modeling without the preparation of accurate server environmental data from the scratch. Therefore, at present, more researchers turn to try reinforcement learning to solve task scheduling in complex data center environments. For example, for the purpose of energy saving, Yuan et al. used the Q-learning algorithm to reduce the data center energy consumption. They tested the algorithm in the CloudSim, a cloud computing simulation framework issued by cloud computing, and distributed system laboratory of the University of Melbourne. The result shows that it can reduce about 40% of the energy consumption of the non-power-aware data center and reduce 1.7% energy consumption of the greedy scheduling algorithm in data center scheduling area [18]. Lin et al. used TD-error reinforcement learning to reduce the energy consumption of data centers, which does not rely on any given stationary assumptions of the job arrival and job service processes. The effectiveness of the proposed reinforcement learning-based data center power management framework was verified with real Google cluster data traces [19]. Li et al. also proposed an end-to-end cooling control algorithm (CCA) that is based on the deep deterministic policy gradient algorithm (DDPG) to optimize the control of cooling system in the data center. The result shows that CCA can achieve about 11% cooling cost saving on the simulation platform compared with a manually configured baseline control algorithm [20]. Shaw et al. proposed an advanced reinforcement learning consolidation agent (ARLCA) based on the Sarsa algorithm to reduce cloud energy consumption [21]. Their work proved that the ARLCA makes a significant improvement in energy saving while the number of service violations is reduced.Scholars also apply reinforcement learning to solve the problems on other purposes of the data center task scheduling. Basu et al. applied reinforcement learning to build cost-models on standard online transaction processing datasets [22]. They modeled the execution of queries and updates as a Markov decision process whose states are database configurations, actions are configuration changes, and rewards are functions of the cost of configuration change and query and update evaluation. The approach was empirically and comparatively evaluated on a standard OLTP dataset. The result shows that the approach is competitive with state-of-the-art adaptive index tuning, which is dependent on a cost model. Peng et al. tried Gaussian process regression with reinforcement learning based on the Q-learning algorithm to solve the problem of state-action space incomplete exploration of reinforcement in cloud data centers [23]. The computational results demonstrated that the schema can balance the exploration and exploitation in the learning process and accelerate the convergence to a certain extent. Ruffy et al. presented a new emulator, Iroko, to support different network topologies, congestion control algorithms, and deployment scenarios. Iroko interfaces with the OpenAI Gym toolkit, which allows for fast and fair evaluation of different reinforcement learning and traditional congestion control algorithms under the same conditions [24]. By the way, some scholars try to combine neural network with heuristic algorithm and have achieved valuable research results. For example, He et al. proposed a new strategy iteration method for online H ∞ optimal control law design based on neural network for nonlinear systems. Numerical simulation is carried out to verify the feasibility and applicability of the algorithm [25]. In the next year, a PI algorithm based on neural network was proposed to solve the problem of online adaptive optimal control of nonlinear systems. Two examples were given to illustrate the effectiveness and applicability of the method [26].The above studies show that reinforcement learning can help us to deal with the scheduling problems of data centers in many domains. However, most of them aim at single objective or are based on the ideal hypothesis that the information about the coming tasks and environment are accurate and adequate in advance, which limits the application of the related studies in real production environment.Furthermore, for most of today’s data centers, resources in fixed scale are usually allocated in advance for most business, which is apparently a low-efficiency mode. In fact, the amount of resources required by business may change with time. If we cannot customize the resource amount according to the changing requirement, when more resources are needed, it will cause serious task delay and affect the user experience badly. Or if fewer resources are needed, more unused resources will be wasted. In this article, we proposed reinforcement learning to optimize scheduling efficiency and to improve resource utilization simultaneously. This is a two-objective optimization work which addresses the primary demand of data center operations.


## 3. The Reinforcement Learning-Based Scheduling Model

In this session, all key parts of the scheduling model as well as the related definitions and equations were illustrated. The important notations are listed in Table1 for better understanding.Table 1
Notations in the scheduling system model.
NotationMemoTypeTThe duration of period of task schedulingModel parameterT^The duration of period of resource optimizationModel parameterpiThe priority function to estimate the priority of taskiFunctiontThe start time of task scheduling which also represents the ID of period of task scheduling (the period is also called time slot)Variablet^The start time of resource optimization which also represents the ID of period of resource optimizationVariables1,a1,r1The state, action, and reward vector for task scheduling agentVariables2,a2,r2The state, action, and reward vector for resource optimization agentVariableμ, ηCalibration parameters to adjust the influence of average task priority and active virtual machine proportionModel parameterμ^, η^Calibration parameters to tune the proportion of the active virtual machine and the proportion of idle virtual machinesModel parametere_tt^,e_tt^′The sum of the execution time of tasks arriving in periodt^ and the sum of the execution time of tasks not executed in period t^Variablen_tt^,n_tt^′The number of tasks arriving in periodt^ and the number of tasks not executed in period t^VariableMThe number of virtual machines in cloud serverModel parameterKThe ratio ofT^ to TModel parameterα,β,H,γThe hyperparameter of A2C algorithmHyperparameter


### 3.1. The Model of Scheduling System

The reinforcement learning-based scheduling system consisted of two parts: environment and scheduling agents. As shown in Figure1, the environment contained task queue, virtual machine cluster, and scheduler. The task queue was the pool to collect the unimplemented tasks in the data center. The virtual machine cluster was the container of virtual machine handlers. The scheduler was the dispatcher to execute the actions from scheduling agents. In this scheduling system, it was assumed that the number of virtual machines was fixed. The configuration and performance of all virtual machines were the same. Tasks in task queue can be scheduled to any idle virtual machine. The virtual machine cluster was defined as VMs=vm1,vm2,vm3,…,vmm where vmi was the handler of virtual machine i.Figure 1
Scheduling system architecture.The agent part included two scheduling agents: Agent1 and Agent2. Each agent was responsible for its optimization objective. Agent1 was for task scheduling, and Agent2 was for resource utilization.In the scheduling model, time is an important factor in task scheduling and optimization of resource utilization. The time in the scheduling model was divided into two types, timet and time t^ shown in Figure 2. t was the start time of task scheduling, and t^ was the start time of optimization of resource utilization. Time t and t^ were defined in the relative time period for ease of calculation. The initial value of t and t^ was 0. In the scheduling model, each task scheduling last Tseconds and each optimization of resource utilization last T^ seconds. T^=K∗TK>0, where K was a parameter in the scheduling model configuration, which hinted the optimization of resource utilization spends more time than task scheduling. In this paper, we defined the interval between t and t+1 as time slot t. So, T was the duration of time slot t. The same definitions were for time slot t^.Figure 2
Model of scheduling time.At timet, Agent1 made the decision on whether to execute each task in the task queue. The scheduling action decision was stored in a1t. After T^ seconds, that is, at time t^, the system started to optimize resource utilization. The virtual machine cluster would turn on or off a certain number of virtual machines according to the optimization decision action a2t^ output by Agent2. The procedure was illustrated in detail as follows.Whenever timet came, the system would receive the tasks arriving from time tand store the tasks in the task queue. Then, the following actions were performed in sequence:(i)
The system selected tasks according to the priority calculated bypi, the task priority function defined in equation (1), and input the current state of the environment s1t to Agent1(ii)
Agent1 output actiona1t and returned it to the environment(iii)
The environment executeda1t and returned the reward r1t to Agent1 when a1twas finishedWhen all tasks in the queue were arranged to execute according toa1t, the system entered the next task scheduling time slot t+1.When the system reached timet^, the system would start the optimization of resource utilization. At time t^, the corresponding actions were performed in the following steps:(i)
The system input the current environment statuss2t^ to Agent2(ii)
Agent2 output action decisiona2t^ and returned it to the environment(iii)
The environment executed action decisiona2t^ to shut down or start up a certain number of virtual machines and returned the reward r2t to Agent2; then, the system entered the next time slot t^+1


### 3.2. Related Definitions

#### 3.2.1. Task Priority

Tasks were the jobs running on virtual machine cluster. Tasks arriving in time slott were added to the task queue waiting for virtual machine allocation. As mentioned above, the environment had little information about the exact number and size of tasks in advance, so the task priority could hardly be simply calculated by waiting time or task execution time. We proposed function pi to estimate the priority of task i. In this function, ei was the execution time of the task i and wi was the waiting time of the task i. pi is defined in the following equation:(1)pi=ei+wiei.After the priorities were calculated, all tasks were scheduled according to their priorities.


#### 3.2.2. Action1

Action1 was the action space of all actions in task schedule. The element of Action1,a1i, indicated whether a certain virtual machine was allocated to the task i. a1i∈0,1. The values of a1i were determined in the following equation:(2)a1i=1,if  taskigets a virtual  machine,0,if taskidoes not get a irtual machine.


#### 3.2.3. State1

State1 was the status space of environment for task scheduling.s1t, the instance of State1, was defined as the vector e1t,pt,m1t,n1t, where e1t was the execution time of the task that was allocated a virtual machine, pt was the priority of the task that was allocated a virtual machine, m1t was the average priority of all the tasks in the task queue (see equation (3)), n1t was the proportion of the active virtual machines in virtual machine cluster (see equation (4)), and Nt was the number of tasks in time slot t:(3)m1t=1Nt∑i=1Ntpi,(4)n1t=nactive_vmM.


#### 3.2.4. Reward1

The reward value represented the feedback value after the action was performed. The reward value of time slott is defined in the following equation:(5)r1t=μ∗m1t+η∗n1t,where μ and η were calibration parameters, which were used to adjust the influence of average task priority m1t and active virtual machine proportion n1t. The values of μ and η were between -1 and 1.


#### 3.2.5. Action2

Action2 represented the number of virtual machines turned on or off in time slott^. The instance of Action2 was defined as a2t^∈−M,M. When a2t^ was greater than 0, it meant there were a2t^ virtual machines turned on. When a2t^ was equal to 0, it meant that no change occurred. When a2t^ was less than 0, it meant that there were a2t^ virtual machines shut down.


#### 3.2.6. State2

State2 was the state space for Agent2.s2t^, the instance of State2, was defined as e2t^,lt^,m2t^,n2t^, where e2t^ was defined as the logarithm of the sum of e_tt^ and e_tt^−1′, where e_tt^ was the sum of the task execution time of the tasks arrived in time slot t^, and e_tt^−1′ was the sum of the task execution time of the tasks not executed at previous time slot t^−1. lt^ was the logarithm of the sum of n_tt^ and n_tt^−1′, where n_tt^ was the number of tasks arrived in time slot t^ and n_tt^−1′ was the number of tasks not executed in the previous time slot t^−1. m2t^ was the average value of m1t in time slot t^. n2t^ was the average proportion of idle virtual machines in time slot t^. `(6)e2t^=loge_tt^+e_tt^−1′,t^=0,1,2,3,…,lt^=logn_tt^+n_tt^−1′,t^=0,1,2,3,…,m2t^=1K∑i=K∗t^−1K∗t^m1i,t^=0,1,2,3,…;K=T^T,n2t^=1K∑i=k∗t^−1k∗t^1−n1i,t^=0,1,2,3,…;K=T^T.


#### 3.2.7. Reward2

Reward2 was the value of reward function for Agent2. It was determined in equation (7), where μ^ and η^ were calibration parameters. We adjusted the value of μ^ and η^ according to the actual situation to tune the proportion of the active virtual machine and the proportion of idle virtual machines in time slot t^:(7)r2t^=μ^n2t^−η^m2t^.


## 3.1. The Model of Scheduling System

The reinforcement learning-based scheduling system consisted of two parts: environment and scheduling agents. As shown in Figure1, the environment contained task queue, virtual machine cluster, and scheduler. The task queue was the pool to collect the unimplemented tasks in the data center. The virtual machine cluster was the container of virtual machine handlers. The scheduler was the dispatcher to execute the actions from scheduling agents. In this scheduling system, it was assumed that the number of virtual machines was fixed. The configuration and performance of all virtual machines were the same. Tasks in task queue can be scheduled to any idle virtual machine. The virtual machine cluster was defined as VMs=vm1,vm2,vm3,…,vmm where vmi was the handler of virtual machine i.Figure 1
Scheduling system architecture.The agent part included two scheduling agents: Agent1 and Agent2. Each agent was responsible for its optimization objective. Agent1 was for task scheduling, and Agent2 was for resource utilization.In the scheduling model, time is an important factor in task scheduling and optimization of resource utilization. The time in the scheduling model was divided into two types, timet and time t^ shown in Figure 2. t was the start time of task scheduling, and t^ was the start time of optimization of resource utilization. Time t and t^ were defined in the relative time period for ease of calculation. The initial value of t and t^ was 0. In the scheduling model, each task scheduling last Tseconds and each optimization of resource utilization last T^ seconds. T^=K∗TK>0, where K was a parameter in the scheduling model configuration, which hinted the optimization of resource utilization spends more time than task scheduling. In this paper, we defined the interval between t and t+1 as time slot t. So, T was the duration of time slot t. The same definitions were for time slot t^.Figure 2
Model of scheduling time.At timet, Agent1 made the decision on whether to execute each task in the task queue. The scheduling action decision was stored in a1t. After T^ seconds, that is, at time t^, the system started to optimize resource utilization. The virtual machine cluster would turn on or off a certain number of virtual machines according to the optimization decision action a2t^ output by Agent2. The procedure was illustrated in detail as follows.Whenever timet came, the system would receive the tasks arriving from time tand store the tasks in the task queue. Then, the following actions were performed in sequence:(i)
The system selected tasks according to the priority calculated bypi, the task priority function defined in equation (1), and input the current state of the environment s1t to Agent1(ii)
Agent1 output actiona1t and returned it to the environment(iii)
The environment executeda1t and returned the reward r1t to Agent1 when a1twas finishedWhen all tasks in the queue were arranged to execute according toa1t, the system entered the next task scheduling time slot t+1.When the system reached timet^, the system would start the optimization of resource utilization. At time t^, the corresponding actions were performed in the following steps:(i)
The system input the current environment statuss2t^ to Agent2(ii)
Agent2 output action decisiona2t^ and returned it to the environment(iii)
The environment executed action decisiona2t^ to shut down or start up a certain number of virtual machines and returned the reward r2t to Agent2; then, the system entered the next time slot t^+1


## 3.2. Related Definitions

### 3.2.1. Task Priority

Tasks were the jobs running on virtual machine cluster. Tasks arriving in time slott were added to the task queue waiting for virtual machine allocation. As mentioned above, the environment had little information about the exact number and size of tasks in advance, so the task priority could hardly be simply calculated by waiting time or task execution time. We proposed function pi to estimate the priority of task i. In this function, ei was the execution time of the task i and wi was the waiting time of the task i. pi is defined in the following equation:(1)pi=ei+wiei.After the priorities were calculated, all tasks were scheduled according to their priorities.


### 3.2.2. Action1

Action1 was the action space of all actions in task schedule. The element of Action1,a1i, indicated whether a certain virtual machine was allocated to the task i. a1i∈0,1. The values of a1i were determined in the following equation:(2)a1i=1,if  taskigets a virtual  machine,0,if taskidoes not get a irtual machine.


### 3.2.3. State1

State1 was the status space of environment for task scheduling.s1t, the instance of State1, was defined as the vector e1t,pt,m1t,n1t, where e1t was the execution time of the task that was allocated a virtual machine, pt was the priority of the task that was allocated a virtual machine, m1t was the average priority of all the tasks in the task queue (see equation (3)), n1t was the proportion of the active virtual machines in virtual machine cluster (see equation (4)), and Nt was the number of tasks in time slot t:(3)m1t=1Nt∑i=1Ntpi,(4)n1t=nactive_vmM.


### 3.2.4. Reward1

The reward value represented the feedback value after the action was performed. The reward value of time slott is defined in the following equation:(5)r1t=μ∗m1t+η∗n1t,where μ and η were calibration parameters, which were used to adjust the influence of average task priority m1t and active virtual machine proportion n1t. The values of μ and η were between -1 and 1.


### 3.2.5. Action2

Action2 represented the number of virtual machines turned on or off in time slott^. The instance of Action2 was defined as a2t^∈−M,M. When a2t^ was greater than 0, it meant there were a2t^ virtual machines turned on. When a2t^ was equal to 0, it meant that no change occurred. When a2t^ was less than 0, it meant that there were a2t^ virtual machines shut down.


### 3.2.6. State2

State2 was the state space for Agent2.s2t^, the instance of State2, was defined as e2t^,lt^,m2t^,n2t^, where e2t^ was defined as the logarithm of the sum of e_tt^ and e_tt^−1′, where e_tt^ was the sum of the task execution time of the tasks arrived in time slot t^, and e_tt^−1′ was the sum of the task execution time of the tasks not executed at previous time slot t^−1. lt^ was the logarithm of the sum of n_tt^ and n_tt^−1′, where n_tt^ was the number of tasks arrived in time slot t^ and n_tt^−1′ was the number of tasks not executed in the previous time slot t^−1. m2t^ was the average value of m1t in time slot t^. n2t^ was the average proportion of idle virtual machines in time slot t^. `(6)e2t^=loge_tt^+e_tt^−1′,t^=0,1,2,3,…,lt^=logn_tt^+n_tt^−1′,t^=0,1,2,3,…,m2t^=1K∑i=K∗t^−1K∗t^m1i,t^=0,1,2,3,…;K=T^T,n2t^=1K∑i=k∗t^−1k∗t^1−n1i,t^=0,1,2,3,…;K=T^T.


### 3.2.7. Reward2

Reward2 was the value of reward function for Agent2. It was determined in equation (7), where μ^ and η^ were calibration parameters. We adjusted the value of μ^ and η^ according to the actual situation to tune the proportion of the active virtual machine and the proportion of idle virtual machines in time slot t^:(7)r2t^=μ^n2t^−η^m2t^.


## 3.2.1. Task Priority

Tasks were the jobs running on virtual machine cluster. Tasks arriving in time slott were added to the task queue waiting for virtual machine allocation. As mentioned above, the environment had little information about the exact number and size of tasks in advance, so the task priority could hardly be simply calculated by waiting time or task execution time. We proposed function pi to estimate the priority of task i. In this function, ei was the execution time of the task i and wi was the waiting time of the task i. pi is defined in the following equation:(1)pi=ei+wiei.After the priorities were calculated, all tasks were scheduled according to their priorities.


## 3.2.2. Action1

Action1 was the action space of all actions in task schedule. The element of Action1,a1i, indicated whether a certain virtual machine was allocated to the task i. a1i∈0,1. The values of a1i were determined in the following equation:(2)a1i=1,if  taskigets a virtual  machine,0,if taskidoes not get a irtual machine.


## 3.2.3. State1

State1 was the status space of environment for task scheduling.s1t, the instance of State1, was defined as the vector e1t,pt,m1t,n1t, where e1t was the execution time of the task that was allocated a virtual machine, pt was the priority of the task that was allocated a virtual machine, m1t was the average priority of all the tasks in the task queue (see equation (3)), n1t was the proportion of the active virtual machines in virtual machine cluster (see equation (4)), and Nt was the number of tasks in time slot t:(3)m1t=1Nt∑i=1Ntpi,(4)n1t=nactive_vmM.


## 3.2.4. Reward1

The reward value represented the feedback value after the action was performed. The reward value of time slott is defined in the following equation:(5)r1t=μ∗m1t+η∗n1t,where μ and η were calibration parameters, which were used to adjust the influence of average task priority m1t and active virtual machine proportion n1t. The values of μ and η were between -1 and 1.


## 3.2.5. Action2

Action2 represented the number of virtual machines turned on or off in time slott^. The instance of Action2 was defined as a2t^∈−M,M. When a2t^ was greater than 0, it meant there were a2t^ virtual machines turned on. When a2t^ was equal to 0, it meant that no change occurred. When a2t^ was less than 0, it meant that there were a2t^ virtual machines shut down.


## 3.2.6. State2

State2 was the state space for Agent2.s2t^, the instance of State2, was defined as e2t^,lt^,m2t^,n2t^, where e2t^ was defined as the logarithm of the sum of e_tt^ and e_tt^−1′, where e_tt^ was the sum of the task execution time of the tasks arrived in time slot t^, and e_tt^−1′ was the sum of the task execution time of the tasks not executed at previous time slot t^−1. lt^ was the logarithm of the sum of n_tt^ and n_tt^−1′, where n_tt^ was the number of tasks arrived in time slot t^ and n_tt^−1′ was the number of tasks not executed in the previous time slot t^−1. m2t^ was the average value of m1t in time slot t^. n2t^ was the average proportion of idle virtual machines in time slot t^. `(6)e2t^=loge_tt^+e_tt^−1′,t^=0,1,2,3,…,lt^=logn_tt^+n_tt^−1′,t^=0,1,2,3,…,m2t^=1K∑i=K∗t^−1K∗t^m1i,t^=0,1,2,3,…;K=T^T,n2t^=1K∑i=k∗t^−1k∗t^1−n1i,t^=0,1,2,3,…;K=T^T.


## 3.2.7. Reward2

Reward2 was the value of reward function for Agent2. It was determined in equation (7), where μ^ and η^ were calibration parameters. We adjusted the value of μ^ and η^ according to the actual situation to tune the proportion of the active virtual machine and the proportion of idle virtual machines in time slot t^:(7)r2t^=μ^n2t^−η^m2t^.


## 4. Reinforcement Learning Algorithm for Scheduling Optimization

In this section, the actor-critic deep reinforcement learning algorithm [21, 27, 28] was applied to create the model for scheduling optimization of data centers. The actor-critic algorithm is a hybrid algorithm based on Q-learning and policy gradient which are two classic algorithms of reinforcement learning. The actor-critic algorithm shows outstanding performance in complicated machine learning missions.A2C was selected in this study. The structure based on A2C is shown in Figure3. In A2C, the actor network is used for action selection and the critic network is used to evaluate the action.Figure 3
Advantage actor-critic structure.As mentioned in Section3, Agent1 acted as the optimization model for task scheduling and Agent2 as the optimization model for resource utilization. (State1, Action1, Reward1) and (State2, Action2, Reward2) were used to describe the state space, action space, and reward function of Agent1 and Agent2, respectively. Hence, s1t,a1t,r1t and s2t^,a2t^,r2t^ separately represented one instance in the state spaces, action space, and the reward functions of Agent1 and Agent2 at time slot t and time slot t^. The data entry st,at,rt,st+1 was recorded as a sample for the training with the A2C algorithm.The parameter of the actor network is updated by advantage functionAst,at (see equation (8)). θa (see equation (9)) and θc (see equation (10)) are the parameters of the actor network and critic network, respectively:(8)Ast,at=rt+γVπθst+1;θc−Vπθst+1;θc,(9)θa⟵θa+α∑t∇logπθast,atAst,at+β∇θaHπθ⋅st,(10)θc⟵θc−α′∑t∇θcAst,at2,where α is the learning rate of the actor network; β is a hyperparameter, and H is the entropy of the policy.In this study, the full-connection layers were used to build the network, in which Agent1 used the six-layer full-connection network, and Agent2 used the four-layer full-connection network. The size of the hidden layer in both agents was 1024. In the training phase, in order to solve the cold start problem of reinforcement learning and accelerate the convergence of the model, the First-Come-First-Service tactic was applied in the early stage for the allocation of virtual machines in the virtual machine cluster and experiences were collected from the results to achieve a better initial status. In the experiences, running_steps, agent1_batch_size, and agent2_batch_size were the control parameters of the training algorithm. The flowchart of the training algorithm is shown in Figure4.Figure 4
The flowchart of model training process.In this study, floating point operations per second (FLOPS) was used to evaluate the complexity of the proposed scheduling algorithm. According to the structure of the full-connection network and the input data shown in Figure3, the complexity of the proposed algorithm was evaluated by(11)Time∼OL∗I2∗K∗N,where K was the ratio of duration of resource utilization T^ to the duration of task scheduling T defined in the model of scheduling time in Section 3.1; N was the maximum number of tasks in time slot t; I was the number of nodes in the hidden layer, and L was the number of hidden layers of the network of Agent1 and Agent2. It hinted that given the A2C-based model above, the performance of the proposed algorithm was highly influenced by K and N. In this study, the complexity of the proposed algorithm with the model trained above was about O6∗220∗K∗N.


## 5. Experiment Study

### 5.1. Dataset

Most previous studies used self-generated datasets in their training work, which was not suitable to validate the applicability of the algorithm in the real production environment. In order to verify the effectiveness of the proposed algorithm in the real production environment, cluster-trace-v2017, the real production dataset published by the Alibaba Cluster Trace Program was used in the experiment study. The data are about the cluster trace from real production environment, which helps the researchers to get better understanding of the characteristics of modern Internet data centers (IDCs) and the workloads [4]. The trace dataset includes the collocation of online services and batch workloads about 1300 machines in a period of 12 hours. The trace dataset contains six kinds of collections: machine_meta.csv, machine_usage.csv, container_meta.csv, container_usage.csv, batch_instance.csv, and batch_task.csv. The task information used in the experiment was from batch_instance.csv collection. In this collection, task id, start time, end time, and other attributes are provided.


### 5.2. Experiment Settings

Here, it was assumed that one virtual machine could not perform multiple tasks at the same time. The virtual machine was equipped with i7-8700k CPU, gtx2080 graphics card, and 32G RAM. The parameters of scheduling system were set as shown in Table2.Table 2
System parameter setting of scheduling experiment.
ParameterValueParametersValueT3 sec.M300∼500T^300 sec.α1e–4μ–1.0α′1e–4η–0.9γ0.9μ^–1.0γ′0.9η^1.0TandT^ were set to the empirical value in scheduling. M was the number of virtual machines in different clouding configurations for comparison. α,α′,γ, and γ′ were set to the empirical value in the A2C algorithm. μ and η were used to control the average priority of tasks and the proportion of active virtual machines. The default value of them was –1. If the goal was to reduce the priority, the ratio of μ/η was increased appropriately. If the goal was to control the cost and reduce the proportion of idle virtual machines, the ratio of μ/η was decreased. The setting of μ^ and η^ was the same.


### 5.3. Model Training

With the trace data from the real production environment, we trained the model with the algorithm introduced in Section4 and recorded the loss value at each training step. The reward values were represented by the average reward of each episode.Figure5 shows the trend of the loss and the reward in training process. Figure 5(a) shows loss trend graph, in which x-axis is the number of training steps and y-axis is the value of loss. It can be seen from the graph that with the increase of training steps, loss gradually decreases until convergence. Figure 5(b) is the reward trend graph, in which the y-axis is reward value and the x-axis is the episode. It shows that with the increase of episode, reward gradually increases and eventually converges at a higher value. It hinted that the performance of the model trained by the algorithm was satisfactory.Figure 5
Trend of the loss and the trend of the reward. (a) Loss trend. (b) Reward trend.
(a)(b)


### 5.4. Comparison with Traditional Scheduling Methods

We compared the proposed A2C scheduling algorithm with classical First-Come-First-Service (FCFS), Shortest-Job-First (SJF), and Fair algorithms in the following two experiments.


#### 5.4.1. Experiment1

The fixed number of virtual machines was set to 300, 350, 400, 450, and 500 in the cluster and ran the different algorithms on the dataset. For the proposed algorithm of this paper, only the task scheduling agent (Agent1) worked in experiment1. The result of experiment 1 shown in Figure6 shows that the average task delay time and the average task priority of the proposed A2C algorithm are less than those of other algorithms with different size of clusters. The results implied that the proposed algorithm worked better in task scheduling than others with different fixed numbers of resources.Figure 6
Results of experiment 1. (a) Comparison of average task delay. (b) Comparison of average task priority.
(a)(b)


#### 5.4.2. Experiment2

In this experiment, Agent 2 worked with Agent1 to schedule the task with dynamic resource allocation. The performance of the proposed algorithm was compared with other algorithms in three dimensions: average delay time of tasks, tasks distribution in different delay time levels, and task congestion degree.The initial size of virtual machine cluster (M) was set the same for FCFS, SJF, and Fair algorithms, and a dynamic size M′ was set for the proposed algorithm. In order to ensure the fair resources supporting for all algorithms, the maximum value of M′ was set up to 1.1×M.(1) Comparison of Average Delay Time of Tasks. The experiment results on different size of virtual machine clusters are shown in Table 3.Table 3
Average delay time of different algorithms on different size of virtual machine clusters (in seconds).
Cluster sizeFairFCFSSJFProposed algorithm (dynamic cluster size)30035.926736.830114.158110.5032 (312)3508.57358.70366.31102.86432 (360)4004.90194.93124.83112.284914 (387)4504.69444.69534.69362.0014 (438)5004.69314.69314.69311.9975 (464)It shows that the proposed algorithm automatically expands the cluster size when the cluster scale is smaller than 400. When the size is set to 300, the cluster size increases by 4% with the task delay decreases by at least 22% compared with those of other algorithms. When the size is set to 350, the cluster size increases by 2.8% with the task delay decreases by at least 28% compared with others. When the cluster size is at a larger level over 400, the proposed algorithm can automatically reduce the cluster size significantly, while the task delay is also considerably smaller than that of Fair, FCFS, and SJF algorithms. In order to show the performance of the proposed algorithm clearly, we defined the relative delay timeτ in equation (12). If τ = 1, it means the performance of the compared algorithm is as good as the proposed algorithm. If τ > 1, it means the performance of the compared algorithm is worse than the proposed algorithm; otherwise, it means the performance of the algorithm is better than the proposed algorithm:(12)τmi=tmitm′∗mm′,where i∈(Fair, FCFS, SJF): (13)M∈300,350,400,450,500,M′∈312,360,387,438,464,tmi was the average delay time of algorithm i with the cluster size m. tm′ was the average delay time of the proposed algorithm with the cluster size M′.According to equation (12), the relative delay time was converted from the data in Table 2 and is shown in Table 4.Table 4
The relative delay time of the compared algorithms.
Cluster sizeFairFCFSSJF3003.3713.3711.2963502.9542.9542.1424002.2312.2312.1854502.4102.4102.4095002.5312.5312.532The results are all greater than 1, which indicates that the task scheduling performance of other compared algorithms with resource utilization is not as good as the proposed algorithm.(2)
Comparison of Task Distribution in Different Delay Time Levels. In this section, the tasks in different delay time intervals were considered. The unit of the delay time interval was T, the duration of task scheduling. Table 5 shows the statistical result.The data in Table5 are about the percentage of tasks whose delay time is less than the delay time interval. The statistical result clearly shows that the proposed algorithm has higher percentage than other algorithms in all delay time intervals. It means, compared with other algorithms, the less the delay time interval, the higher the percentage of undelayed tasks in this delay time interval. Especially, in the 1T level, the percentage of tasks out of all is almost twice as much as that of others.Table 5
The task distribution in different delay time intervals.
Task delay time interval (T)SJF (%)FCFS (%)Fair (%)The proposed algorithm (%)136.67513.04525.68851.781266.73446.83351.02181.115377.77565.54663.93584.691483.22671.03670.79787.173586.45173.11874.60388.7831092.61076.43880.91492.9541594.80778.64283.80394.9052095.94880.76186.01196.017(3) Comparison of Task Congestion Degree. Task congestion degree reflected the number of tasks waiting for execution in the task queue at the end of each time slot. It was measured by the percentage of time slots in which the number of congested tasks was less than a certain benchmark number. Therefore, with a certain benchmark number, the less the congestion degree was, the better the scheduling algorithm worked. The statistical result is illustrated in Table 6 and Figure 7.Table 6
Task congestion degree.
Number of congested tasksSJF (%)FCFS (%)Fair (%)The proposed algorithm (%)033.73931.77831.80282.277565.44462.00561.99083.3201075.05670.96571.10784.3351579.33274.84774.99985.3252081.58476.62276.86786.2482583.20477.80977.95287.0443084.36678.68578.64387.835……………Figure 7
Task congestion degree chart.It can be seen from the data in first row of Table6 that the proposed algorithm makes all tasks executed in over 82% time slots and for other algorithms, all tasks are executed only in about 30% of all time slots. The change of task congestion degree of all algorithms with more benchmark numbers is visualized by the plot chart in Figure 7, which shows that the congestion degree with the proposed algorithm remains relatively stable and better than other algorithms with all benchmark numbers of congested tasks.


## 5.1. Dataset

Most previous studies used self-generated datasets in their training work, which was not suitable to validate the applicability of the algorithm in the real production environment. In order to verify the effectiveness of the proposed algorithm in the real production environment, cluster-trace-v2017, the real production dataset published by the Alibaba Cluster Trace Program was used in the experiment study. The data are about the cluster trace from real production environment, which helps the researchers to get better understanding of the characteristics of modern Internet data centers (IDCs) and the workloads [4]. The trace dataset includes the collocation of online services and batch workloads about 1300 machines in a period of 12 hours. The trace dataset contains six kinds of collections: machine_meta.csv, machine_usage.csv, container_meta.csv, container_usage.csv, batch_instance.csv, and batch_task.csv. The task information used in the experiment was from batch_instance.csv collection. In this collection, task id, start time, end time, and other attributes are provided.


## 5.2. Experiment Settings

Here, it was assumed that one virtual machine could not perform multiple tasks at the same time. The virtual machine was equipped with i7-8700k CPU, gtx2080 graphics card, and 32G RAM. The parameters of scheduling system were set as shown in Table2.Table 2
System parameter setting of scheduling experiment.
ParameterValueParametersValueT3 sec.M300∼500T^300 sec.α1e–4μ–1.0α′1e–4η–0.9γ0.9μ^–1.0γ′0.9η^1.0TandT^ were set to the empirical value in scheduling. M was the number of virtual machines in different clouding configurations for comparison. α,α′,γ, and γ′ were set to the empirical value in the A2C algorithm. μ and η were used to control the average priority of tasks and the proportion of active virtual machines. The default value of them was –1. If the goal was to reduce the priority, the ratio of μ/η was increased appropriately. If the goal was to control the cost and reduce the proportion of idle virtual machines, the ratio of μ/η was decreased. The setting of μ^ and η^ was the same.


## 5.3. Model Training

With the trace data from the real production environment, we trained the model with the algorithm introduced in Section4 and recorded the loss value at each training step. The reward values were represented by the average reward of each episode.Figure5 shows the trend of the loss and the reward in training process. Figure 5(a) shows loss trend graph, in which x-axis is the number of training steps and y-axis is the value of loss. It can be seen from the graph that with the increase of training steps, loss gradually decreases until convergence. Figure 5(b) is the reward trend graph, in which the y-axis is reward value and the x-axis is the episode. It shows that with the increase of episode, reward gradually increases and eventually converges at a higher value. It hinted that the performance of the model trained by the algorithm was satisfactory.Figure 5
Trend of the loss and the trend of the reward. (a) Loss trend. (b) Reward trend.
(a)(b)


## 5.4. Comparison with Traditional Scheduling Methods

We compared the proposed A2C scheduling algorithm with classical First-Come-First-Service (FCFS), Shortest-Job-First (SJF), and Fair algorithms in the following two experiments.


### 5.4.1. Experiment1

The fixed number of virtual machines was set to 300, 350, 400, 450, and 500 in the cluster and ran the different algorithms on the dataset. For the proposed algorithm of this paper, only the task scheduling agent (Agent1) worked in experiment1. The result of experiment 1 shown in Figure6 shows that the average task delay time and the average task priority of the proposed A2C algorithm are less than those of other algorithms with different size of clusters. The results implied that the proposed algorithm worked better in task scheduling than others with different fixed numbers of resources.Figure 6
Results of experiment 1. (a) Comparison of average task delay. (b) Comparison of average task priority.
(a)(b)


### 5.4.2. Experiment2

In this experiment, Agent 2 worked with Agent1 to schedule the task with dynamic resource allocation. The performance of the proposed algorithm was compared with other algorithms in three dimensions: average delay time of tasks, tasks distribution in different delay time levels, and task congestion degree.The initial size of virtual machine cluster (M) was set the same for FCFS, SJF, and Fair algorithms, and a dynamic size M′ was set for the proposed algorithm. In order to ensure the fair resources supporting for all algorithms, the maximum value of M′ was set up to 1.1×M.(1) Comparison of Average Delay Time of Tasks. The experiment results on different size of virtual machine clusters are shown in Table 3.Table 3
Average delay time of different algorithms on different size of virtual machine clusters (in seconds).
Cluster sizeFairFCFSSJFProposed algorithm (dynamic cluster size)30035.926736.830114.158110.5032 (312)3508.57358.70366.31102.86432 (360)4004.90194.93124.83112.284914 (387)4504.69444.69534.69362.0014 (438)5004.69314.69314.69311.9975 (464)It shows that the proposed algorithm automatically expands the cluster size when the cluster scale is smaller than 400. When the size is set to 300, the cluster size increases by 4% with the task delay decreases by at least 22% compared with those of other algorithms. When the size is set to 350, the cluster size increases by 2.8% with the task delay decreases by at least 28% compared with others. When the cluster size is at a larger level over 400, the proposed algorithm can automatically reduce the cluster size significantly, while the task delay is also considerably smaller than that of Fair, FCFS, and SJF algorithms. In order to show the performance of the proposed algorithm clearly, we defined the relative delay timeτ in equation (12). If τ = 1, it means the performance of the compared algorithm is as good as the proposed algorithm. If τ > 1, it means the performance of the compared algorithm is worse than the proposed algorithm; otherwise, it means the performance of the algorithm is better than the proposed algorithm:(12)τmi=tmitm′∗mm′,where i∈(Fair, FCFS, SJF): (13)M∈300,350,400,450,500,M′∈312,360,387,438,464,tmi was the average delay time of algorithm i with the cluster size m. tm′ was the average delay time of the proposed algorithm with the cluster size M′.According to equation (12), the relative delay time was converted from the data in Table 2 and is shown in Table 4.Table 4
The relative delay time of the compared algorithms.
Cluster sizeFairFCFSSJF3003.3713.3711.2963502.9542.9542.1424002.2312.2312.1854502.4102.4102.4095002.5312.5312.532The results are all greater than 1, which indicates that the task scheduling performance of other compared algorithms with resource utilization is not as good as the proposed algorithm.(2)
Comparison of Task Distribution in Different Delay Time Levels. In this section, the tasks in different delay time intervals were considered. The unit of the delay time interval was T, the duration of task scheduling. Table 5 shows the statistical result.The data in Table5 are about the percentage of tasks whose delay time is less than the delay time interval. The statistical result clearly shows that the proposed algorithm has higher percentage than other algorithms in all delay time intervals. It means, compared with other algorithms, the less the delay time interval, the higher the percentage of undelayed tasks in this delay time interval. Especially, in the 1T level, the percentage of tasks out of all is almost twice as much as that of others.Table 5
The task distribution in different delay time intervals.
Task delay time interval (T)SJF (%)FCFS (%)Fair (%)The proposed algorithm (%)136.67513.04525.68851.781266.73446.83351.02181.115377.77565.54663.93584.691483.22671.03670.79787.173586.45173.11874.60388.7831092.61076.43880.91492.9541594.80778.64283.80394.9052095.94880.76186.01196.017(3) Comparison of Task Congestion Degree. Task congestion degree reflected the number of tasks waiting for execution in the task queue at the end of each time slot. It was measured by the percentage of time slots in which the number of congested tasks was less than a certain benchmark number. Therefore, with a certain benchmark number, the less the congestion degree was, the better the scheduling algorithm worked. The statistical result is illustrated in Table 6 and Figure 7.Table 6
Task congestion degree.
Number of congested tasksSJF (%)FCFS (%)Fair (%)The proposed algorithm (%)033.73931.77831.80282.277565.44462.00561.99083.3201075.05670.96571.10784.3351579.33274.84774.99985.3252081.58476.62276.86786.2482583.20477.80977.95287.0443084.36678.68578.64387.835……………Figure 7
Task congestion degree chart.It can be seen from the data in first row of Table6 that the proposed algorithm makes all tasks executed in over 82% time slots and for other algorithms, all tasks are executed only in about 30% of all time slots. The change of task congestion degree of all algorithms with more benchmark numbers is visualized by the plot chart in Figure 7, which shows that the congestion degree with the proposed algorithm remains relatively stable and better than other algorithms with all benchmark numbers of congested tasks.


## 5.4.1. Experiment1

The fixed number of virtual machines was set to 300, 350, 400, 450, and 500 in the cluster and ran the different algorithms on the dataset. For the proposed algorithm of this paper, only the task scheduling agent (Agent1) worked in experiment1. The result of experiment 1 shown in Figure6 shows that the average task delay time and the average task priority of the proposed A2C algorithm are less than those of other algorithms with different size of clusters. The results implied that the proposed algorithm worked better in task scheduling than others with different fixed numbers of resources.Figure 6
Results of experiment 1. (a) Comparison of average task delay. (b) Comparison of average task priority.
(a)(b)


## 5.4.2. Experiment2

In this experiment, Agent 2 worked with Agent1 to schedule the task with dynamic resource allocation. The performance of the proposed algorithm was compared with other algorithms in three dimensions: average delay time of tasks, tasks distribution in different delay time levels, and task congestion degree.The initial size of virtual machine cluster (M) was set the same for FCFS, SJF, and Fair algorithms, and a dynamic size M′ was set for the proposed algorithm. In order to ensure the fair resources supporting for all algorithms, the maximum value of M′ was set up to 1.1×M.(1) Comparison of Average Delay Time of Tasks. The experiment results on different size of virtual machine clusters are shown in Table 3.Table 3
Average delay time of different algorithms on different size of virtual machine clusters (in seconds).
Cluster sizeFairFCFSSJFProposed algorithm (dynamic cluster size)30035.926736.830114.158110.5032 (312)3508.57358.70366.31102.86432 (360)4004.90194.93124.83112.284914 (387)4504.69444.69534.69362.0014 (438)5004.69314.69314.69311.9975 (464)It shows that the proposed algorithm automatically expands the cluster size when the cluster scale is smaller than 400. When the size is set to 300, the cluster size increases by 4% with the task delay decreases by at least 22% compared with those of other algorithms. When the size is set to 350, the cluster size increases by 2.8% with the task delay decreases by at least 28% compared with others. When the cluster size is at a larger level over 400, the proposed algorithm can automatically reduce the cluster size significantly, while the task delay is also considerably smaller than that of Fair, FCFS, and SJF algorithms. In order to show the performance of the proposed algorithm clearly, we defined the relative delay timeτ in equation (12). If τ = 1, it means the performance of the compared algorithm is as good as the proposed algorithm. If τ > 1, it means the performance of the compared algorithm is worse than the proposed algorithm; otherwise, it means the performance of the algorithm is better than the proposed algorithm:(12)τmi=tmitm′∗mm′,where i∈(Fair, FCFS, SJF): (13)M∈300,350,400,450,500,M′∈312,360,387,438,464,tmi was the average delay time of algorithm i with the cluster size m. tm′ was the average delay time of the proposed algorithm with the cluster size M′.According to equation (12), the relative delay time was converted from the data in Table 2 and is shown in Table 4.Table 4
The relative delay time of the compared algorithms.
Cluster sizeFairFCFSSJF3003.3713.3711.2963502.9542.9542.1424002.2312.2312.1854502.4102.4102.4095002.5312.5312.532The results are all greater than 1, which indicates that the task scheduling performance of other compared algorithms with resource utilization is not as good as the proposed algorithm.(2)
Comparison of Task Distribution in Different Delay Time Levels. In this section, the tasks in different delay time intervals were considered. The unit of the delay time interval was T, the duration of task scheduling. Table 5 shows the statistical result.The data in Table5 are about the percentage of tasks whose delay time is less than the delay time interval. The statistical result clearly shows that the proposed algorithm has higher percentage than other algorithms in all delay time intervals. It means, compared with other algorithms, the less the delay time interval, the higher the percentage of undelayed tasks in this delay time interval. Especially, in the 1T level, the percentage of tasks out of all is almost twice as much as that of others.Table 5
The task distribution in different delay time intervals.
Task delay time interval (T)SJF (%)FCFS (%)Fair (%)The proposed algorithm (%)136.67513.04525.68851.781266.73446.83351.02181.115377.77565.54663.93584.691483.22671.03670.79787.173586.45173.11874.60388.7831092.61076.43880.91492.9541594.80778.64283.80394.9052095.94880.76186.01196.017(3) Comparison of Task Congestion Degree. Task congestion degree reflected the number of tasks waiting for execution in the task queue at the end of each time slot. It was measured by the percentage of time slots in which the number of congested tasks was less than a certain benchmark number. Therefore, with a certain benchmark number, the less the congestion degree was, the better the scheduling algorithm worked. The statistical result is illustrated in Table 6 and Figure 7.Table 6
Task congestion degree.
Number of congested tasksSJF (%)FCFS (%)Fair (%)The proposed algorithm (%)033.73931.77831.80282.277565.44462.00561.99083.3201075.05670.96571.10784.3351579.33274.84774.99985.3252081.58476.62276.86786.2482583.20477.80977.95287.0443084.36678.68578.64387.835……………Figure 7
Task congestion degree chart.It can be seen from the data in first row of Table6 that the proposed algorithm makes all tasks executed in over 82% time slots and for other algorithms, all tasks are executed only in about 30% of all time slots. The change of task congestion degree of all algorithms with more benchmark numbers is visualized by the plot chart in Figure 7, which shows that the congestion degree with the proposed algorithm remains relatively stable and better than other algorithms with all benchmark numbers of congested tasks.


## 6. Conclusions and Further Study

With the expansion of online business in data center, task scheduling and resource utilization optimization become more and more pivotal. Large data center operation is facing the proliferation of uncertain factors, which leads to the geometric increase of environmental complexity. The traditional heuristic algorithms are difficult to cope with today’s complex and constantly changing data center environment. However, most of the previous studies focused on one aspect of data center optimization and most of them did not verify their algorithms on the real data center dataset.Based on the previous studies, this paper designed a reasonable deep reinforcement learning model, optimized the task scheduling and resource utilization. Experiments were also performed with the real production dataset to validate the performance of the proposed algorithm. Average delay time of tasks, task distribution in different delay time levels, and task congestion degree as performance indicators were used to measure the scheduling performance of all algorithms applied in the experiments. The experiment results showed that the proposed algorithm worked significantly better than the compared algorithms in all indexes listed in experiments, ensured the efficient task scheduling and dynamically optimized the resource utilization of clusters.It should be noted that reinforcement learning is a kind of time-consuming work. In this study, it took 12 hours to train the model with the sample data from the real production environment containing 1300 virtual machines. We also used other production data (cluster-trace-v2018) from the Alibaba Cluster Trace Program to train the scheduling model. The dataset is about 4000 virtual machines in an 8-day period, which is much bigger than the former dataset. As the dataset’s scale increased, the training time became considerably longer and underfit occurred if the number of layers of the machine learning model was not increased. As shown in equation (11), the performance of the proposed algorithm is determined by the complexity of the full-connection network, time slot ratio, and the number of tasks in a time slot. Considering the trade-off of the training time cost and the performance, it is strongly recommended to prepare the sample dataset to a reasonable scale with sampling technology to reduce the complexity of the scheduling model.In addition, we did not consider other task attributes and constraints of data center environment. Fox example, in this study, it was assumed that the number of virtual machines was not dynamically changed, and the ability of all virtual machines were the same. It was also assumed that one virtual machine cannot perform multiple tasks at the same time. Therefore, we do not imply that the proposed model is available for all kinds of clusters. Notwithstanding its limitation, in the future study, the proposed model should be improved to optimize the task scheduling in the heterogeneous environments of the data center clusters through taking more constraints and attributes of real production environment into account.



---

*Source: 3046769-2020-08-31.xml*