Title: Level-based batch scheduling strategies for computational grid
Authors: Mohammad Shahid; Zahid Raza
Addresses: School of Computer & Systems Sciences, Jawaharlal Nehru University, New Delhi 110067, India ' School of Computer & Systems Sciences, Jawaharlal Nehru University, New Delhi 110067, India
Abstract: Grid computing is a high performance computing environment that allows sharing of geographically distributed resources across multiple administrative domains serving the ever growing demand for computational power. Scheduling m jobs to n resources to optimise the QoS for the given objective parameters has been proven to be NP-complete. This work presents two centralised level based batch scheduling strategies for a computational grid with the objective of minimising the turnaround time. The scheduler evaluates various computational nodes to schedule the batch of jobs consisting of a number of sub-jobs/modules having precedence and dependence constraints along with inter module communication requirements. Minimum Completion Time (MCT) and Minimum Execution Time (MET) heuristics have been used to decide the most suitable node for the given sub-job in terms of the turnaround time offered. A comparative analysis of the strategies with a model with similar objective has been performed to evaluate their place in the middleware.
Keywords: batch scheduling; computational grid; DAG; directed acyclic graph; level-based scheduler; NP hard problems; turnaround time; utilisation; scheduling strategies; grid computing; QoS; quality of service; middleware; minimum completion time; minimum execution time.
International Journal of Grid and Utility Computing, 2014 Vol.5 No.2, pp.135 - 148
Received: 04 Oct 2012
Accepted: 07 Nov 2013
Published online: 29 Oct 2014 *