Predictive Job Scheduling under Uncertain Constraints in Cloud Computing

1 Introduction

The cloud computing paradigm manages resources as a shared pool of configurable virtual machines (VMs), and offers an opportunity for users to allocate or release VMs whenever necessary. Deploying workloads on large-scale cloud platforms, such as Amazon Web Service, Microsoft Azure, Google Cloud, has thus gained significant popularity in recent years. The total market of worldwide public cloud will grow to $364B in 2022 based on Gartner forecasts 1 .

∗Corresponding authors

For cloud platforms, it remains a huge challenge to properly allocate the computing resources with a high utilization rate and with a high reliability level at the same time due to the plug-and-play and pay-as-you-go styles in cloud computing [Mesbahi et al., 2018; Gawali and Shinde, 2018]. From an operational perspective, the total demand in a public cloud is in the order of millions of VMs per day. This high request rate must be satisfied by the platform while maintaining fast response time, and therefore would result in a waste of resources along the fluctuations between peaks and valleys of customers' demands.

To reduce the resource waste due to demand fluctuations, a stream of VM products with pre-collected demands has been released by major cloud platforms, where customers can book resources in a coming time window by specifying the required VM type, the duration in hours, as well as the earliest and latest time for the job to start. Collecting the demands for these VMs and scheduling these jobs properly can greatly shave peaks and fill valleys of resource utilization along time, and can therefore achieve a higher utilization rate and higher overall revenue for the platform.

However, it is challenging to intelligently schedule these pre-collected job requests due to the uncertain available resources (normally referred to as capacity in cloud computing) in the future and not affect the system's high reliability level at the same time. More specifically, deploying jobs violating the capacity will largely reduce system reliability in cloud computing. To this end, we resort to a Prediction + Optimization framework to tackle this difficulty in this paper. More specifically, we provide a general formulation for the scheduling problem on the pre-collected job requests under uncertain capacity, and propose a solution called Controlling under Uncertain Constraints (CUC) for this Prediction + Optimization problem. With CUC, we can flexibly control the violation level on capacity constraints in the application, and maximize the overall utilization for the pre-collected job requests under the pre-specified violation level. Extensive experiments on three public datasets from Microsoft Azure show that CUC can strictly control the violation level to the available capacity and outperforms existing state-of-the-art methods . We list the main contributions of this work as follows:

1 https://www.gartner.com/en/newsroom/press-releases/202007-23-gartner-forecasts-worldwide-public-cloud-revenue-to-grow6point3-percent-in-2020

• We provide an effective formulation for a class of scheduling problems with uncertain constraints to be predicted, and furthermore introduce a violation level on the constraints to be controlled.
• We propose CUC, a novel approach for solving the job scheduling problem under uncertain constraints, and can flexibly control the violation level on uncertain constraints to fulfill system requirements.
• CUC is demonstrated to be able to strictly control the violation level on the uncertain constraints with industrial datasets on extensive experiments and meet rigorous reliability requirements in cloud computing.

2 RelatedWork

The pre-collected job scheduling problem in cloud computing can be treated as a variant of the general machine scheduling problem [Chen et al., 1998]. Even when the future capacity is known, this problem is known to be an NP-hard problem and usually formulated as a mixed integer programming (MIP) problem [Fanjul-Peyro et al., 2017]. Solving this type of problems often needs to resort to heuristics or other approximation algorithms [Fleszar and Hindi, 2018].

Another type of problem related to the pre-collected job scheduling problem in cloud computing is the general resource allocation problem. Most of the works on resource allocation focus on considering demand or workload uncertainty with known capacity [Calzarossa et al., 2019]. However, in many application scenarios, the capacity itself may suffer from uncertainty, such as the case in appointment scheduling and room allocation in health-care systems [Gupta and Denton, 2008; Zhou et al., 2020]. Rather than just assuming the future available capacity to be known, resource (capacity) prediction based planning methods have been explored both by academia [Huang et al., 2018] and industry. Further more, the uncertainty considered in these works is in the form of a fixed probability distribution, which we can hardly well capture in reality. Instead, we usually need to develop a statistical distribution of the unknown value from historical data. Therefore, the actual performance of the optimization problems under this 'uncertain uncertainty' would largely depend on the prediction performance on the uncertain value.

The literature [Verderame et al., 2010] has reviewed several ways to take into parameter uncertainty in an explicit manner, including two-stage stochastic programming, parametric programming, fuzzy programming, chance constraint programming, robust optimization, and conditional valueat-risk frameworks. Moreover, a group of methods have been raised recently dealing with the Prediction + Optimization problem [Demirovic et al., 2019; Luo et al., 2020; Mandi et al., 2020], where the optimization objective contains unknown parameters that needs to be predicted before optimization. Currently, these works have not considered the uncertainty in constraints and are therefore not applicable for the pre-collected job scheduling problem under uncertain capacity constraints considered in this work.

3 ProblemFormulation

In this section, we formally formulate the job scheduling problem under uncertain capacity constraints as follows.

Definitions on job requests. Given a set of pre-collected job requests B = {b1, . . . , bN}, each job request includes basic requirements for the job to run. Specifically, for a job request bi ∈ B, i ∈ {1, . . . , N}, it can be represented as bi = (ci, di, ei, li), where ci is the requested resource capacity for job i, di is the duration for the job, ei and li are the earliest start time and latest start time for the job, respectively. In practice, the most valuable computing resource is the CPU cores in cloud computing [Luo et al., 2020], and it can be any other type of resources according to the specific application. Here di is restricted to be an integer hours of duration, ei and li are restricted to be the beginning of each hour, and ei < li for i ∈ {1, . . . ,N}. For each of the job requests, it is only valid between its earliest start time and latest start time and should be deployed during this period, or it is treated as failed otherwise.

Definitions on predicted capacity. From the view of the supply side, the cloud platform can only deploy these precollected job requests on the remaining capacity, which is obtained by subtracting the capacity occupied by on-demand job requests from the whole available resource pool in the cloud platform. Therefore, due to the uncertainty on the on-demand workloads, the available capacity for deployment of these pre-collected jobs also suffers from the uncertainty, and needs to be predicted at a regular basis for scheduling these precollected jobs. For each scheduling scope containing T hours, the predicted capacity is a time series ˆ A = {ˆa1, ˆa2, ..., ˆaT } where ˆai, i ∈ {1, ..., T} is the predicted distribution of available capacity for job requests measured in the unit of CPU cores.

Problem formulation. The job scheduling process is running in a regular basis, covering the time period of T time units (e.g., T = 24 hours in the application scenario considered in this work). Each scheduling run needs to determine for the following T time units, which job requests should start at the beginning of each time unit. The process can be formally formulated as a combinatorial optimization problem. The decision variables are {Xit}, i = 1, ...,N, t = 1, ..., T , where Xit = 1 if job request i is scheduled to start at time t, and Xit = 0 otherwise. The goal of the job scheduling practice is to maximize the overall computing resources multiplied by the duration time for the deployed job requests and try not to affect the on-demand workloads. This combinatorial optimization problem formulation is as follows:

Awhere ˆ

A is the output of a specific

where at is the real available capacity for the pre-collected jobs at time t, t ∈ {1, ..., T}. Note that A = {a1, ..., aT} remains unknown when solving this scheduling problem, we can only estimateAwith ˆ time series prediction method using historical capacity data.

In essence, the above combinatorial optimization problem

A would be the

cannot be directly solved since A is unknown. In this case of not knowing the real available capacity, we cannot guarantee any scheduled plan would not affect the on-demand workloads unless no request for the pre-collected jobs is actually deployed. Therefore, we propose a new formulation (2) which allows a specific low level of impact on the normal ondemand workloads, and tries to control the impact so that it is below this specific level. The goal has thus turned to maximizing the benefits from these scheduled pre-collected jobs on the condition that the violation frequency for on-demand capacity is controlled under a pre-specified level p by adjusting the capacity constraints in the optimization problem. In an ideal situation, the predicted distribution ˆ true distribution of A, then the following optimization problem would be sufficient to achieve our goal:

Maximize u =

However, there is always error between our predicted distribution ˆ A and the true distribution of A. Therefore, we still need to improve our prediction based on the result from the optimization step to achieve better performance. Formally, we use a two-layer optimization formulation for this scheduling problem with predicted uncertainty:

where p is the pre-specified violation level, and v is the actual violation rate comparing the scheduled capacity with the true capacity:

In this formulation (3), the objective is to 1) achieve the highest utilization under the capacity constraints that is predicted to meet the pre-specified violation level p; 2) improve the predictive performance on future capacity according to the performance of the optimization result in the training stage, which will be further explained in Section 4.

4 Controlling under Uncertain Constraints

In this section, we introduce Controlling under Uncertain Constraints (CUC), our scheduling algorithm under uncertain constraints for the Prediction + Optimization problem for precollected job requests.

4.1 Overall Design of CUC

The illustration of the overall design of CUC is shown in Figure 1. As stated before, we try to schedule the pre-collected job requests in a coming period under unknown capacity. To deal with this uncertainty, the capacity is predicted using historical capacity so as to get an estimation on the constraints under which the job requests should be scheduled. Then the predicted distribution of future capacity is used to determine the capacity constraints according to the pre-specified violation level for the inner level optimization in (3), which gives a scheduled plan for the job requests. To improve the prediction as well as the scheduling performance, the actual violation rate and the error between that and the pre-specified violation level are calculated and sent to the Bayesian optimization module to update parameters for the prediction model. After several iterations when the violation error is well controlled, we get the optimized scheduling plan as well as the improved parameters for the prediction model in the specific dataset.

4.2 Technical Details of CUC

More specifically, the use of the proposed CUC can be divided into the training stage and the testing stage. In the training stage of CUC, the major objective is to learn better prediction model parameters for real prediction applications. The training procedures of CUC are summarized in Algorithm 1.

To obtain the predicted distribution for the capacity in the next T time units, we adopt the time series prediction model based on sliding windows [Box and Jenkins, 1976] and fit

Algorithm 1: Training Procedures of CUC

• Input: Historical capacity A-, Requests B = {bi}i∈{1,...,N}, Violation level p, Converge threshold γ, Max iteration steps k; Output: Schedule {Xit}i∈{1,...,N},t∈{1,...,T}, Prediction parameters θ; 1 Set iter num = 1, initialize parameters θ = θ0 for the prediction model; 2 while max (v - p, 0) > γ or iter num ≤ k do 3 Get predicted distribution ˆ A with θ and historical capacity A- using Algorithm 2; 4 ˜ A ← Φ-1 ˆ A (p); 5 Conduct the greedy constructive algorithmwith capacity constraints ˜ A, get {X(0) it }i∈{1,...,N},t∈{1,...,T}; 6 Calculate the violation rates according to (4); 7 Update the parameters θ in the prediction through
• BO according to max (v - p, 0); 8 iter num← iter num+1;
• 9 return X, θ;

the distribution of prediction error similar to the prediction component in [Luo et al., 2020]. The detail of the prediction method is shown in Algorithm 2. We first construct prediction samples using a sliding window, and then calculate the prediction errors on the samples and fit the distribution of prediction uncertainty using Gaussian mixture model (GMM) [Luo et al., 2020] with these calculated prediction errors. Although CUC can work with any parametric time series prediction model since it treats the prediction function as a black box, in this work we use a time series decomposition based forecasting approach [Hyndman and Athanasopoulos, 2018] considering its performance and computational efficiency for the experiments in this work.

The predicted distributions for future capacity in T consecutive time units are then used to calculate the expected capacity constraints ˜ A = Φ-1 ˆ A (p) where Φ-1 ˆ A (·) is the inverse cumulative distribution function (CDF) for distribution ˆ A. Ideally, the predicted distribution ˆ A is close enough to the true distribution, and then setting the constraints ˜ A according to this formula would better control the violation rate.

For our imperfect prediction results, the model parameters θ for the prediction model are then iteratively updated in the training stage so as to achieve the optimization goal in (3), which is to control the actual violation rate v of capacity at a specific low level and maximize the utilization of all deployed jobs. A greedy constructive method described in Algorithm 3 is designed to tackle with the inner-level optimization problem with high computational efficiency under the capacity constraints ˜ A.

Note that in (3) the inner layer optimization problem is a standard MIP problem which is known to be NP-hard, and therefore we propose a new, greedy constructive method to meet the requirement on computational cost in our schedul-

Algorithm 2: Prediction Method in CUC

Input: Prediction parameters θ, Historical capacity A- = {a-1 , ..., a-L } ; Output: Predicted capacity distribution ˆ A = {ˆa1, ..., ˆaT }; 1 for t ← 1 to L-2T +1 do 2 Get prediction ˙a-t+T , ... ˙a-t+2T-1 trained on previous L - l capacity values ; 3 Calculate δi ← a-i - ˙a-i for i ∈ {t + T, ..., t + 2T - 1}; 4 ˙A = { ˙ a1, ... ˙ aT } ← predict with previous capacities {a-L-T+1 , ..., a-L }; 5 ϵ = {ϵ1, ..., ϵT} ← fit the error distribution by GMM using {δL-T+1, ..., δL-1}; 6 ˆ A = ˙A+ ϵ; 7 return ˆ A

ing application. It has been demonstrated both theoretically [Du and Pardalos, 1998] and practically [Cai et al., 2017] that greedy strategy is a major way of designing algorithms for NP-hard optimization problems. Moreover, experiments in Section 5 also demonstrate the effectiveness of our greedy constructive algorithm.

The violation error, i.e., the difference between the actual violation rate v and the pre-specified level p when v is larger than p, is then calculated as the objective for choosing prediction model parameters. In practice, there are usually many samples in the training set, and in this case the error on the violation level is calculated by: ∑Ss=1 max (vs -p, 0) /S, where S is the number of samples in the training set. The violation error is then sent to the Bayesian optimization (BO) [Mockus and Mockus, 1991] module which basically builds and maintains a surrogate model to select better parameters for reducing the violation error. The prediction and optimization steps conducted in an iterative manner until the actual violation rate ¯ v is still smaller but close enough to the prespecified violation level p, or the number of iteration steps is large enough with regard to the system requirements. The schedule X for the final optimization step is then output as the scheduled plan, and the parameters θ is output as the prediction model parameters to be adopted in the testing stage or in production environment.

For the testing stage, the prediction model is run with the learned parameters and then the corresponding optimization problem is solved only once for each sample in the testing set with Algorithm 3. The output scheduled plan X is then output as the actual deployment plan for the jobs in application. The testing procedures of CUC are concluded in Algorithm 4.

5 Experiments

To evaluate the performance of our proposed scheduling algorithm CUC, we conduct extensive experiments on three public datasets and one synthetic dataset. Then we illustrate the effects of both the BO module and the uncertainty prediction

Algorithm 3: Greedy Construction Method in CUC

Input: Capacity Constraints ˜ A = {˜at}t∈{1,...,T }; Requests B = {bi}i∈{1,...,N}; Output: Schedule {Xit}i∈{1,...,N},t∈{1,...,T}; 1 Sort the set of request by descending order of ci/di; 2 for i ← 1 to N do 3 ∆← initialize an empty list of capacity gaps; 4 STi ←min(li, T -di +1), the latest start time; 5 for t ← ei to STi do 6 δt ← min ˜ t∈{t,t+di} (ˆa˜ t - ci - i-1 ∑ j=1 cj ˜ t∑ u=˜ t-dj+1 Xju); 7 add element δt to the list ∆; 8 δt∗ ← find the largest δt ∈ ∆; 9 if δt∗ > 0 then 10 Xit∗ ←1, deploy job i at time t∗ ; 11 else 12 continue, skip job i; 13 return {Xit}i∈{1,...,N},t∈{1,...,T};

module, as well as the power of controlling violation level in our proposed formulation for the pre-collected jobs.

5.1 Datasets

The experiments in this work are conducted on three public datasets, which are all collected from Microsoft Azure. In particular, two public datasets are introduced in the literature [Cortez et al., 2017] and each of both contains the representative VM workload of Microsoft Azure across 30 consecutive days; the other dataset is described in [Hadary et al., 2020] and includes the representative VM workload of Microsoft Azure across 14 consecutive days. To make these datasets applicable with our algorithm and consistent for evaluation, we extract the job requests and the corresponding available capacity for each hour to obtain three datasets with 14 days of data for each dataset. The job requests in these datasets are the jobs with duration from 1 to 6 hours. The pre-processed dataset will also be publicly available in order to provide benchmarking datasets for this type of scheduling problems.

Each of the three datasets is divided into a training set and a testing set. For the first 5 days out of the 14 days, we only use the hourly available capacity for fitting our prediction model. Then a sliding window is adopted to generate samples, with each sample containing past hourly capacity for 5 days (i.e., 120 data points for prediction), future capacity for T = 24 hours, and the job requests in the next 24 hours. The last 2 days are left as the testing set, and therefore there are altogether 144 samples for Day 6 to Day 11. Job requests in Day 12 are left out to avoid data leakage in constructing the dataset.

5.2 State-of-the-art Competitors and Setup

We consider the following methods as our state-of-the-art competitors. The first one is the classical two-stage method where we use several classical time series prediction models

Algorithm 4: Testing Procedures of CUC

Input: Requests {bi}i∈{1,...,N}, Prediction parameters θ, Feasibility level p;

• Output: Schedule {Xit}i∈{1,...,N},t∈{1,...,T}; 1 Get predicted distribution ˆ A according to θ; 2 Calculate the corresponding capacity constraints ˜ A according to the inverse cdf of ˆ A; 3 Solve the optimization problem (2) with Algorithm 3, get {Xit}i∈{1,...,N},t∈{1,...,T}; 4 return X

to predict the future capacity at once and then solve the correspondent MIP problem with Gurobi, a professional solver for linear and non-linear optimization problems. The prediction methods in our experiments include linear regression (LR), time series decomposition based forecasting approach (TSDec) [Hyndman and Athanasopoulos, 2018], automatic autoregressive integrated moving average (AutoARIMA) [Hyndman and Athanasopoulos, 2018], long short-term memory (LSTM) [Luo et al., 2019], un-observed component model (UCM) [Durbin and Koopman, 2012] and Prophet [Taylor and Letham, 2018]. Besides, we also compare our scheduling algorithm with OptNet [Amos and Kolter, 2017] who solves differentiable optimization problems through a layer in neural networks. Note that it has been claimed in [Amos and Kolter, 2017] that OptNet is not practical with a too heavy computational burden when the number of hidden variables in an OptNet layer is larger than 1000, and our preliminary experiments also confirm that OptNet is not applicable for the data of 100k-scale decision variables in the three datasets we use. Therefore, we have down-sampled the job requests and capacity correspondingly in the Azure 2020 dataset with a factor of 0.01 to make a fourth synthetic data for incorporating OptNet as a competitor of our algorithm.

In this work, all experiments were conducted on a machine with Intel Xeon E5-2690 v4 CPU, 112GB memory and NVIDIA Tesla P100 GPU. In CUC, we set the number of BO steps as k = 50 as suggested in [Wu et al., 2019] if not explicitly presented in the table.

5.3 Experiment Results

Scheduling Performance against Competitors

The experiment results for comparing the proposed CUC method with the other 7 state-of-the-art scheduling methods are shown in Table 1. We record the utility ratio on the testing set (denoted by 'Util'), which is calculated as follows:

where X∗ it is the optimal schedule obtained by actually solving the MIP problem with all the capacity known by Gurobi solver on the testing set. Besides, the actual violation rate on the testing set (denoted by 'Vio') is also computed by Vio = ∑Ss=1 vs/S × 100%, where S is the number of samples in the testing set. Note that, when a scheduling plan violates the capacity constraints (i.e., Vio is greater than 0), the resulted utility ratio might be larger than 1.

Considering the cloud computing application scenario of CUC, the violation rate should be well controlled at a low level (we set p = 0.1% here according to the common reliability requirements in cloud computing) in order to avoid severe impact for on-demand workloads. Therefore, all the scheduling methods compared in this experiment should be able to stably achieve a low violation rate on testing set and provide a satisfactory utility ratio as well.

The comparison results are shown in Table 1, from which we can obtain the following observations. First, CUC provides the best performance in controlling the violation rate, and at the same time does not sacrifice much on the utility ratio. According to [Luo et al., 2020], achieving the utility ratio around 80% is already favorable in production. Moreover, CUC performs around 100 times faster than any other compared method in the computational time for scheduling.

Discussion. We note that, a production cloud platformmust achieve a high reliability, so a scheduling plan with high violation rate is not applicable. As demonstrated in Table 1, all our competitors exhibit high violation rates, while CUC can achieve high utilization rate (> 90%) while keep low violation rate (< 0.1%), indicating that the superiority of CUC over all competitors in real-world applications.

Ablation Analysis

To demonstrate the effectiveness of the uncertainty modeling and the Bayesian optimization module in CUC, an ablation analysis is conducted. Here we compare our proposed CUC algorithm with its two variants: in the first variant we conduct prediction on the capacity value without error distribution considered, and thus just set constraints as the predicted capacity; for the second variant, we set the iteration times of BO as k = 1 to avoid iterated update on the prediction model parameters, and set the violation level parameter as p = 0.1% to keep consistent with the setting of CUC. The related results are reported in Table 2, and clearly show that both the uncertainty modeling and the BO module contributed to the good performance of CUC on reducing the violation rate.

Controlling Violation Level by p

Another appealing property of CUC is that the violation rate can be flexibly controlled according to the required system reliability level. We have compared the violation rate under different pre-specified violation levels p in Table 3. The results demonstrate that by setting different p values in CUC, the actual violation rate can be well controlled under p and the utility ratio can still be satisfactory. This study further demonstrates that CUC can be flexibly and efficiently applied in a wide range of job scheduling applications with different reliability requirements.

6 Application in Practice

Microsoft Azure has been continuously evolving to provide products and services to meet emerging demands from customers. The feature of pre-collecting VM requests with a discount is such an example. In practice, we allow customers to submit jobs in advance which will run continuously for 1-6 hours. The proposed method has supported the scheduling plan for this type of pre-collected VM requests in Microsoft Azure. According to the evaluation result during a pilot study, we observe a 65% increase in utilization ratio with the proposed scheduling method compared to the traditional first-infirst-out fashion, with the average waiting time for the VM

requests not significantly prolonged.

7 Conclusion

To utilize the computing resources more effectively and efficiently, it is of critical importance for cloud platforms to develop intelligent scheduling methods for pre-collected demands under uncertain available capacity in the near future, such as the job format considered in this work. We formally formulate the job scheduling problem under uncertain capacity constraints as a Prediction + Optimization problem , and propose a novel and effective algorithm CUC for solving this type of scheduling problem. Our proposed algorithm CUC can effectively control the violation level according to specific requirements of the whole resource management system and maximize the resource utilization at the same time. The effectiveness of CUC has been validated through extensive experiments on three public, real-world application datasets.

For future work, we plan to consider the optimization problem with uncertainty in both constraints and objective functions, which can be applied in a broader range of real-world scenarios. Moreover, although currently reinforcement learning techniques cannot be directly applied to the predictive job scheduling problem, it is still a promising direction to explore how to adopt advanced models on reinforcement learning on this problem.

Acknowledgements

We would like to thank Yunus Mohammed, Marcus Fontoura, Girish Bablani, Lidong Zhou, and Hsiao-Wuen Hon for their great support and sponsorship. We would also like to thank Shandan Zhou, Kevin Yang, Harrison Zhao, Karthikeyan Subramanian, Marko Lalic, and Rajeesh Ramachandran for the collaboration on the application of the scheduling algorithm into Microsoft Azure.