Managing Deadline-constrained Bag-of-Tasks Jobs on Hybrid Clouds

Bo Wang, Ying Song, Yuzhong Sun, Jun Liu

Abstract

Outsourcing jobs to a public cloud is a cost-effective way to address the problem of satisfying peak resource demand when a local cloud has insufficient resources. In this paper, we study the management of deadline-constrained bag-of-tasks (BoT) jobs on hybrid clouds. We present a binary nonlinear programming (BNP) problem to model hybrid cloud management where the utilization of physical machines (PMs) in the local cloud is maximized when local resources are sufficient to satisfy job deadlines; otherwise, the rental cost from the public cloud is minimized. To solve this BNP problem in polynomial time, we proposed a heuristic algorithm (HA). Extensive experimental results show that our heuristic algorithm saves 16.2%–76% in rental costs and improves resource utilization by 47.3%–182.8% while satisfying deadline constraints, compared to the standard first-fit decreasing (FFD) algorithm.

Introduction

Many organizations operate on a hybrid cloud model, maintaining a private local cloud for steady-state workloads while "bursting" into public clouds (e.g., AWS, Azure) to handle demand spikes. A common workload in these environments is the Bag-of-Tasks (BoT) job—a collection of independent, computationally intensive tasks that must be completed by a specific deadline. Examples include large-scale image rendering, software testing, and data analysis.

Managing these jobs effectively requires balancing two competing goals: minimizing the high cost of public cloud resources and ensuring all tasks meet their temporal constraints. Existing scheduling solutions often fail to account for the heterogeneity of local hardware or the specific cost-performance ratios of public cloud instances, leading to either missed deadlines or excessive spending.

System Model and Methodology

To address these challenges, we formalize the scheduling problem as a Binary Nonlinear Programming (BNP) model. The objective is to prioritize local resource usage (treated as a sunk cost) and only rent public Virtual Machines (VMs) when local capacity is exhausted.

System architecture for mapping BoT jobs to local physical machines (PMs) or public cloud virtual machines (VMs).

Because the BNP problem is NP-hard, we developed a Heuristic Algorithm (HA) designed for polynomial-time execution. The HA follows several key principles:

  1. Deadline-First Assignment: Tasks closest to their deadlines are prioritized for scheduling.
  2. Local Resource Priority: The algorithm attempts to fill every available core on local Physical Machines (PMs) before considering external resources.
  3. Cost-Performance Optimization: When public cloud rental is unavoidable, the algorithm selects VM instances based on the best cost-performance ratio rather than simple price points.
  4. Sequential Packing: Tasks assigned to the same core are executed in order of their deadlines to maximize throughput without violations.

Experimental Evaluation

We evaluated the HA using real-world traces from the Parallel Workloads Archive: the UniLu Gaia log (a 3-month trace from the University of Luxembourg) and the NASA Ames iPSC/860 log (a 2-month trace). The simulation environment consisted of 15 heterogeneous local PMs and public cloud instances modeled after Amazon EC2 c3.large instances.

Key Results and Discussion

The HA significantly outperformed the industry-standard First Fit Decreasing (FFD) algorithm across all tested scenarios. FFD typically schedules the longest tasks first, which often leaves a "tail" of small tasks that force the system to rent expensive, underutilized public VMs to meet final deadlines. In contrast, the HA’s deadline-centric packing ensures higher density and delayed rental.

Comparison of rental costs between FFD and HA for Gaia and NASA datasets across varying deadline constraints (alpha).

As shown in the experimental results, the HA achieved:

  • Significant Cost Savings: Rental costs were reduced by 16.2% to 76% compared to FFD.
  • Improved Utilization: Local and rented resource utilization improved by 47.3% to 182.8%.
  • Scalability: The algorithm's time complexity increases quadratically with the number of tasks, making it suitable for large-scale industrial applications.

While the HA resulted in longer total "makespans" (total completion time) than FFD, this is an acceptable trade-off because all tasks still successfully met their required deadlines. The primary goal of cost-conscious hybrid cloud management is meeting constraints at minimum cost, rather than finishing as early as possible at any expense.

Conclusion

This research demonstrates that a deadline-aware heuristic can drastically improve the economic efficiency of hybrid cloud environments. By prioritizing local resources and selecting public VMs based on cost-performance ratios, organizations can handle peak BoT workloads without breaking their budgets. Future work will explore more complex workflows with task dependencies and the impact of data transfer costs in data-heavy applications.

Summary updated

Abstract

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 this BNP problem in polynomial time, we proposed a heuristic algorithm. Its main idea is assigning the task closest to its deadline to current core until the core cannot finish any task within its deadline. When there is no available core, the algorithm adds an available PM with most capacity or rents a new VM with highest cost-performance ratio. Extensive experimental results show that our heuristic algorithm saves 16.2%-76% rent cost and improves 47.3%-182.8% resource utilizations satisfying deadline constraints, compared with first fit decreasing algorithm.
BibTeX
@inproceedings{wang2016managing,
  author = {Bo Wang and Ying Song and Yuzhong Sun and Jun Liu},
  title = {{Managing Deadline-constrained Bag-of-Tasks Jobs on Hybrid Clouds}},
  booktitle = {SpringSim (HPS)},
  year = {2016},
  url = {https://openreview.net/forum?id=tNLu8wn53jsN},
}
Figure