A Great Deluge Algorithm with Bi-Decay Rate for Efficient Task Scheduling in Grid Computing
- 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.
DOI: https://doi.org/10.3844/jcssp.2019.313.320
Copyright: © 2019 KaiLun Eng, Abdullah Muhammed, Sazlinah Hasan and Mohamad Afendee Mohamed. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
- 4,104 Views
- 2,086 Downloads
- 0 Citations
Download
Keywords
- Heuristic
- Great Deluge
- Extended Great Deluge
- Diversification
- Grid Scheduling Problem