Research Article Open Access

A Great Deluge Algorithm with Bi-Decay Rate for Efficient Task Scheduling in Grid Computing

KaiLun Eng1, Abdullah Muhammed1, Sazlinah Hasan1 and Mohamad Afendee Mohamed2
  • 1 Universiti Putra Malaysia, Malaysia
  • 2 Universiti Sultan Zainal Abidin, Malaysia

Abstract

To realise the utmost idea of global collaborative resource sharing with Grid computing, the fundamental scheduling process is playing a critical role. However, scheduling in Grid computing environment is a well-known NP-complete problem. In this study, we propose a new extension of Great Deluge algorithm with an effective diversification strategy for the Grid scheduling problem. The proposed approach, namely BiGD, exploits two different decay rates (a linear and a non-linear decay rate of water level) to provide a better diversification strategy for exploring the solution space. The performance of the proposed algorithm has been evaluated and compared with the standard Great Deluge and Extended Great Deluge algorithm, through the GridSim simulation toolkit. Four different scheduling scenarios or cases which comprise different combination of task heterogeneity and resource heterogeneity are considered for the performance evaluation. Moreover, we have adapted all the algorithms to have same total number of evaluation for solution searching in order to ensure a fair comparison is established in the performance evaluation. The experimental simulation results show that the proposed algorithm is superior and able to produce good quality solutions compared to the other algorithms in all the problem instances.

Journal of Computer Science
Volume 15 No. 3, 2019, 313-320

DOI: https://doi.org/10.3844/jcssp.2019.313.320

Submitted On: 6 July 2017 Published On: 7 March 2019

How to Cite: Eng, K., Muhammed, A., Hasan, S. & Mohamed, M. A. (2019). A Great Deluge Algorithm with Bi-Decay Rate for Efficient Task Scheduling in Grid Computing. Journal of Computer Science, 15(3), 313-320. https://doi.org/10.3844/jcssp.2019.313.320

  • 3,285 Views
  • 1,682 Downloads
  • 0 Citations

Download

Keywords

  • Heuristic
  • Great Deluge
  • Extended Great Deluge
  • Diversification
  • Grid Scheduling Problem