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

2. Related Works

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).