Solving Job Scheduling Problem in Computational Grid Systems Using a Hybrid Algorithm

2. Related Works

Due to various complex characteristics of resources and jobs, the job scheduling in Grid is a NP-complete problem. Meta-heuristic methods have proven to be efficient in solving such problems. Various meta-heuristic algorithms have been designed to schedule the jobs in computational Grid (Thilagavathi et al., 2012). These sorts of approaches make realistic assumptions based on a priori knowledge of the concerning environment and of the system load characteristics. The most commonly used meta-heuristic algorithms are Genetic Algorithms (GA), Particle Swarm Optimization (PSO), Simulated Annealing (SA), Ant Colony Optimization (ACO) and Cuckoo Search Algorithm (CSA). In general, meta-heuristic approaches manage to obtain much better performance, but take a longer execution time (Bianco et al., 2015).

The Genetic algorithm (GA) is a meta-heuristic algorithm that imitates the principle of genetic process in living organisms. GA mimics the evolutionary process by applying selection, crossover, and mutation to generate solution from the search space. The GA is a very popular algorithm to solve various types of combinatorial optimization problems. GAs for the 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). Prakash and Vidyarthi (2015) have proposed a new technique to maximize the availability of resources for job scheduling in computational Grid using GA. Enhanced Genetic-based scheduling for Grid computing is proposed in (Kolodziej and Xhafa, 2011).