A Hybrid Meta-heuristic Approach for Load Balanced Workflow Scheduling in IaaS Cloud

摘要

Workflow scheduling is one of the most-focused research problems in the field of cloud computing. This is a well known NP-complete problem and therefore finding an optimal solution in respect of various parameters such as makespan, resource utilization, energy, QoS or their combination is computationally very expensive. Nevertheless, load balancing among the virtual machines (VMs) is one of the most important aspects while scheduling tasks of the workflow. In this paper, we propose a hybrid meta-heuristic approach for workflow scheduling for IaaS cloud which is shown to be load balanced. The proposed algorithm is based on hybridization of genetic algorithm (GA) and particle swarm optimization (PSO). The algorithm takes advantages of both the algorithms by avoiding slower convergence rate of GA and local optimum problem in PSO. The objective of the proposed algorithm is to map the tasks of the workflow to the VMs, such that the overall workflow execution time (makespan) is minimized and the assigned load on each VM is also balanced. With the rigorous experiments on scientific workflows, we show that the proposed approach performs better than PSO, GA and MPQGA (multiple priority queues genetic algorithm) based workflow scheduling algorithms. We also validate the better performance through a statistical test, i.e., paired t test with 95% confidence interval.