An Heuristic for Bag-of-Tasks Scheduling Problems with Resource Demands and Budget Constraints to Minimize Makespan on Hybrid Clouds
Yi Zhang, Jin Yuan Sun, Zebin Wu · 2017
Bag-of-Tasks (BoT) applications consisting of multiple tasks widely exist in numerous fields. As customers use cloud resources in a pay-as-you-go way, they are willing to execute BoT applications on clouds. When the private cloud has insufficient available resources to afford all tasks, the cloud provider has to outsource some tasks to public clouds with resource-used costs. The key challenge here is how to schedule tasks on hybrid clouds to minimize makespan given a limited budget. We study and formulate this problem as an Integer Programming problem. Accordingly, we propose an effective heuristic (EH) including two phases (task sequencing and task scheduling). EH uses a Longest Task First method (LTF) to generate a task sequence. A Task Assignment method (TA) is established to schedule all tasks in the obtained sequence one by one. Experimental results demonstrate that the proposed EH outperforms the baseline (RoundRobin) significantly.