A GSA based hybrid algorithm for bi-objective workflow scheduling in cloud computing

摘要

Workflow Scheduling in cloud computing has drawn enormous attention due to its wide application in both scientific and business areas. This is particularly an NP-complete problem. Therefore, many researchers have proposed a number of heuristics as well as meta-heuristic techniques by considering several issues, such as energy conservation, cost and makespan. However, it is still an open area of research as most of the heuristics or meta-heuristics may not fulfill certain optimum criterion and produce near optimal solution. In this paper, we propose a meta-heuristic based algorithm for workflow scheduling that considers minimization of makespan and cost. The proposed algorithm is a hybridization of the popular meta-heuristic, Gravitational Search Algorithm (GSA) and equally popular heuristic, Heterogeneous Earliest Finish Time (HEFT) to schedule workflow applications. We introduce a new factor called cost time equivalence to make the bi-objective optimization more realistic. We consider monetary cost ratio (MCR) and schedule length ratio (SLR) as the performance metrics to compare the performance of the proposed algorithm with existing algorithms. With rigorous experiments over different scientific workflows, we show the effectiveness of the proposed algorithm over standard GSA, Hybrid Genetic Algorithm (HGA) and the HEFT. We validate the results by well-known statistical test, Analysis of Variance (ANOVA). In all the cases, simulation results show that the proposed approach outperforms these algorithms.