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

摘要

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.