Predictive Job Scheduling under Uncertain Constraints in Cloud Computing

Capacity management has always been a great challenge for cloud platforms due to massive, heterogeneous on-demand instances running at different times. To better plan the capacity for the whole platform, a class of cloud computing instances have been released to collect computing demands beforehand. To use such instances, users are allowed to submit jobs to run for a pre-specified uninterrupted duration in a flexible range of time in the future with a discount compared to the normal on-demand instances. Proactively scheduling those pre-collected job requests considering the capacity status over the platform can greatly help balance the computing workloads along time. In this work, we formulate the scheduling problem for these pre-collected job requests under uncertain available capacity as a Prediction + Optimization problem with uncertainty in constraints, and propose an effective algorithm called Controlling under Uncertain Constraints (CUC), where the predicted capacity guides the optimization of job scheduling and job scheduling results are leveraged to improve the prediction of capacity through Bayesian optimization. The proposed formulation and solution are commonly applicable for proactively scheduling problems in cloud computing. Our extensive experiments on three public, industrial datasets shows that CUC has great potential for supporting high reliability in cloud platforms.

Authors

• Hang Dong
• Boshi Wang
• Bo Qiao
• Wenqian Xing Stanford University
• Chuan Luo Beihang University
• Si Qin
• Qingwei Lin Microsoft Research
• Dongmei Zhang Peking University
• Gurpreet Virdi
• Thomas Moscibroda

Keywords

• Heuristic Search and Game Playing: Heuristic Search and Machine Learning
• Multidisciplinary Topics and Applications: Autonomic Computing