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.
Because the BNP problem is NP-hard, we developed a Heuristic Algorithm (HA) designed for polynomial-time execution. The HA follows several key principles:
- Deadline-First Assignment: Tasks closest to their deadlines are prioritized for scheduling.
- Local Resource Priority: The algorithm attempts to fill every available core on local Physical Machines (PMs) before considering external resources.
- 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.
- 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.
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