A Hybrid Algorithm Using Genetic Algorithm and Cuckoo Search Algorithm to Solve Job Scheduling Problem in Computational Grid Systems

A Hybrid Algorithm Using Genetic Algorithm and Cuckoo Search Algorithm to Solve Job Scheduling Problem in Computational Grid Systems

Tarun Kumar Ghosh (Department of Computer Science and Engineering, Haldia Institute of Technology, West Bengal, India) and Sanjoy Das (Department of Engineering and Technological Studies, Kalyani University, West Bengal, India)
Copyright: © 2016 |Pages: 11
DOI: 10.4018/IJAEC.2016040101
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Job scheduling is one of the major challenges in Grid computing systems to efficiently exploit the capabilities of dynamic, autonomous, heterogeneous and distributed resources for execution of different types of jobs. Thus optimal job scheduling is an NP-complete problem which can easily be solved by using heuristic techniques. This paper presents a hybrid algorithm for job scheduling using Genetic Algorithm (GA) and Cuckoo Search Algorithm (CSA) for efficiently allocating jobs to resources in a Grid system so that makespan and flowtime are minimized. This proposed algorithm combines the advantages of both GA and CSA. The authors' results have been compared with standard GA, CSA and Ant Colony Optimization (ACO) to show the importance of the proposed algorithm.
Article Preview

The job scheduling in Grid is a NP-complete problem. Heuristic methods have proven to be efficient in solving such problems. Various heuristic algorithms have been designed to schedule the jobs in computational Grid (Thilagavathi et al., 2012). The most commonly used heuristic algorithms are Genetic Algorithms (GA), Particle Swarm Optimization (PSO), Simulated Annealing (SA), Ant Colony Optimization (ACO) and Cuckoo Search Algorithm (CSA). In general, heuristic approaches manage to obtain much better performance, but take a longer execution time.

Genetic Algorithms (GAs) for Grid scheduling problems have been studied by Abraham et al. (2000); Kolodziej et al. (2012); Braun et al. (2001); Zomaya and The (2001); Di Martino and Mililotti (2004); Moghaddam et al. (2012); Page and Naughton (2005); Gao et al. (2005); Xhafa et al. (2008); Aggarwal et al. (2005). Particle Swarm Optimization (PSO) algorithm is proved to be a good mechanism to apply for Grid scheduling (Zhang et al., 2008; Karimi, 2014). Liu et al. (2009) proposed an approach for scheduling using a fuzzy PSO algorithm. Simulated Annealing (SA) is more powerful than simple local search by accepting also poorer solutions with certain probability. Such heuristic has been studied for Grid scheduling by Abraham et al. (2000); Goswami et al. (2011); Yarkhan and Dongarra (2002). An ACO implementation for the scheduling problem under the ETC model has been investigated by Ritchie (2003) and Molaiy et al. (2014). Siriluck et al. (2007) have also applied an ACO method for dynamic job scheduling in Grid environment. Prakash et al. (2012); Rabiee et al. (2013) have proposed a job scheduling in Grid using Cuckoo Search Algorithm (CSA).

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2017): 3 Released, 1 Forthcoming
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing