A heuristic-based task scheduling algorithm for scientific workflows in heterogeneous cloud computing platforms

Abstract

Task scheduling problem in a cloud computing environment is one of the most important issues in this field. Because task schedulers should be aware of underlying platform heterogeneity, task interdependencies, and virtual machine (VM) variable configurations. An efficient task scheduling algorithm can potentially increase the efficiency of cloud computing, by choosing the appropriate virtual machine to do a specific task-scheduling problem, for dependent tasks on heterogeneous resources which is a well-known NP-Hard problem. To reduce minimum total execution time, makespan, in cloud computing many heuristics were presented in literature but lots of them suffer from low efficiency. In this article, a new task priority strategy and applying task duplication methods are proposed, for solving the task scheduling problem of the dependent tasks in heterogeneous cloud computing systems. The novelty of the current paper is to present a new list scheduling algorithm with a new task priority strategy and applying pertinent task duplication techniques. This paper uses optimistic cost table downward (OCTd) and optimistic cost table upward (OCTu) procedures to prioritize tasks in an efficient ordered list; then, it utilizes Heterogeneous Earliest Finish Time (HEFT)-duplication method for performing task duplication technique which significantly reduces makespan. To validate the proposal, we experimentally analyzed the proposed scheduling algorithm with different scientific workflows such as Molecular, LU-Like, FFT, and Montage datasets. The performance comparison of the novel heuristic scheduling algorithm against other existing approaches proved the superiority of proposed algorithm in terms of makespan, speedup, SLR, and efficiency which are prominent scheduling evaluation metrics.

Keywords

• Heuristic list-scheduling
• Cloud computing
• Heterogeneous systems
• Task duplication