UPM Institutional Repository

A hybrid heuristic of variable neighbourhood descent and great deluge algorithm for efficient task scheduling in grid computing


Muhammed, Abdullah and Mohamed, Mohamad Afendee and Hasan, Sazlinah and Eng, Kailun (2019) A hybrid heuristic of variable neighbourhood descent and great deluge algorithm for efficient task scheduling in grid computing. European Journal of Operational Research, 284. pp. 75-86. ISSN 0377-2217


To achieve the ultimate success of global collaborative resource sharing in Grid computing, an effective and efficient Grid resource management system is necessary and it is only possible if its core component, the scheduler, can perform scheduling in an efficient manner. Scheduling tasks to resources in Grid computing is a challenging task and known as a NP hard problem. In this paper, we propose a novel hybrid heuristic-based algorithm, which synergised the excellent diversification capability of Great Deluge (GD) algorithm with the powerful systematic multi-neighbourhood search strategy captured in Variable Neighbourhood Descent (VND) algorithm, to efficiently schedule independent tasks in Grid computing environment with an objective of minimising the makespan. Simulation experiments have been conducted to examine the impact of hybridising GD and VND. In addition, the performance of the proposed algorithm has been evaluated and compared with some other recent meta-heuristics in the literature. The experimental simulation results show that our proposed algorithm outperforms the other algorithms in the literature and the performance improvement achieved by this hybrid strategy is effective and efficient with respect to makespan and computational time as it can obtain good quality (makespan) of solutions while obviating the drawback of requiring high computational cost from the VND.

Download File

[img] Text (Abstract)

Download (6kB)

Additional Metadata

Item Type: Article
Divisions: Faculty of Computer Science and Information Technology
DOI Number: https://doi.org/10.1016/j.ejor.2019.12.006
Publisher: Elsevier
Keywords: Scheduling; Hybrid heuristic; Variable Neighbourhood Descent (VND); Great Deluge (GD); Grid scheduling problem
Depositing User: Ms. Nuraida Ibrahim
Date Deposited: 09 Nov 2020 14:55
Last Modified: 09 Nov 2020 14:55
Altmetrics: http://www.altmetric.com/details.php?domain=psasir.upm.edu.my&doi=10.1016/j.ejor.2019.12.006
URI: http://psasir.upm.edu.my/id/eprint/80426
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item