Title: An efficient greedy task scheduling algorithm for heterogeneous inter-dependent tasks on computational grids

Authors: D.B. Srinivas; Sujay N. Hegde; M.A. Rajan; H.K. Krishnappa

Addresses: Nitte Meenakshi Institute of Technology, Bangalore, India ' Nitte Meenakshi Institute of Technology, Bangalore, India ' TCS Research and Innovation, Bangalore, India ' R.V. College of Engineering, Bangalore, India

Abstract: Designing a task scheduling algorithm for precedence constrained task graphs is still a challenge due to its complexity (NP-complete). Hence the majority of the research in this area is devoted to designing optimal scheduler based on a plethora of techniques such as heuristic, greedy, genetic, game theory, bio-inspired, machine learning etc. for fully dependent or independent task graphs. Motivated by these works, we propose an efficient greedy task scheduling algorithm for precedence constrained task graphs with varied dependencies (no, partial and fully) on computational grids. Performance of the proposed task scheduling algorithm is compared with respect to Turn Around Time (TAT) and grid utilisation against Hungarian, Partial Precedence Constrained (P_PCS) and AND scheduling algorithms. Simulation results shows that the performance of the proposed scheduling algorithm is on a par with Hungarian, P_PCS and AND scheduling algorithms and the running time of proposed algorithm is better than Hungarian and is on a par with P_PCS algorithm.

Keywords: task scheduling; computational grids; partial dependency; turnaround time; grid utilisation; standard task graphs; greedy task scheduling algorithm; brute force scheduling algorithm; fragmentation; random task graph.

DOI: 10.1504/IJGUC.2020.110059

International Journal of Grid and Utility Computing, 2020 Vol.11 No.5, pp.587 - 601

Received: 26 Sep 2019
Accepted: 04 Oct 2019
Published online: 02 Oct 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article