Managing Deadline-constrained Bag-of-Tasks Jobs on Hybrid Clouds
Bo Wang, Ying Song, Yuzhong Sun, Jun Liu · 2016
Outsourcing jobs to a public cloud is a cost-effective way to address the problem of satisfying the peak resource demand when the local cloud has insufficient resources. In this paper, we study on managing deadline-constrained bag-of-tasks jobs on hybrid clouds. We present a binary nonlinear programming (BNP) problem to model the hybrid cloud management where the utilization of physical machines (PMs) in the local cloud/cluster is maximized when the local resources are enough to satisfy the deadline constraints of jobs, while when not, the rent cost from the public cloud is minimized. To solve the BNP problem in polynomial time, we propose the heuristic algorithm whose main idea is assigning a task to a core of a used PM (in local cloud) or a rented virtual machine (VM) (in public cloud) such that the difference between the finish time of the task and its deadline is minimal in all of assignments. If none of unassigned tasks can be completed within its deadline, the algorithm adds an available PM with most capacity or rents a new VM with highest cost-performance ratio and assigns tasks to the new PM/VM as previous step. Extensive experimental results show that our heuristic algorithm saves 16.2%-76% cost and improves 47.3%-182.8% resource utilizations for finishing jobs within their respective deadlines with comparable overheads, compared with first fit decreasing algorithm.