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

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

Tarun Kumar Ghosh (Haldia Institute of Technology, India) and Sanjoy Das (Kalyani University, India)
Copyright: © 2019 |Pages: 15
DOI: 10.4018/978-1-5225-5832-3.ch015

Abstract

Grid computing is a high performance distributed computing system that consists of different types of resources such as computing, storage, and communication. The main function of the job scheduling problem is to schedule the resource-intensive user jobs to available grid resources efficiently to achieve high system throughput and to satisfy user requirements. The job scheduling problem has become more challenging with the ever-increasing size of grid systems. The optimal job scheduling is an NP-complete problem which can easily be solved by using meta-heuristic techniques. This chapter 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, flowtime, and job failure rate are minimized. This proposed algorithm combines the advantages of both GA and CSA. The results have been compared with standard GA, CSA, and ant colony optimization (ACO) to show the importance of the proposed algorithm.
Chapter Preview
Top

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

Complete Chapter List

Search this Book:
Reset