Efficient Job Scheduling in Computational Grid Systems Using Wind Driven Optimization Technique

2. Related Works

Computational Grid is composed of a large number of heterogeneous resources and jobs, which are executing concurrently and are changing dynamically. Due to such environment characteristics, the job scheduling in Grid is an NP-complete problem. New approaches, particularly those based in heuristic algorithms, have been proposed to solve the Grid scheduling problems. These sorts of approaches make realistic assumptions based on a priori knowledge of the concerning environment and of the system load characteristics. The most frequently used heuristic algorithms are Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Simulated Annealing (SA), Ant Colony Optimization (ACO) and Cuckoo Search Algorithm (CSA). Genetic Algorithms (GAs) for Grid scheduling problems have been addressed by Abraham et al. (2000), Braun et al. (2001), Zomaya and Teh (2001), Martino and Mililotti (2004), Page and Naughton (2005), Gao et al. (2005), Xhafa et al. (2008) and Aggarwal et al. (2005). Zhang et al. (2008) have applied Particle Swarm Optimization (PSO) algorithm for Grid scheduling and showed that PSO gives better results compared to GA. A fuzzy PSO algorithm for scheduling has been proposed by Abraham et al. (2010). Simulated Annealing (SA) is more powerful than simple local search by accepting poorer solutions with certain probability. Abraham et al. (2000), Goswami et al. (2011), and Yarkhan and Dongarra (2002) have studied SA technique for Grid scheduling. An Ant Colony Optimization (ACO) implementation for the scheduling problem under the ETC model has been addressed by Ritchie (2003). An ACO algorithm for dynamic job scheduling in Grid environment has also been investigated by Lorpunmanee et al. (2007). Prakash et al. (2012), and Rabiee and Sajedi (2013) have proposed a job scheduling in Grid using Cuckoo Search Algorithm (CSA). A large number of researches have been carried out using hybrid approaches. For example, Abraham et al. (2000) have proposed the hybridization of GA, SA and TS heuristics. Another hybrid method for the problem has been addressed by Ritchie and Levine (2004) who combine an ACO algorithm with a TS algorithm for the problem. Sajedi and Rabiee (2014) have combined CSA with GA for job scheduling in Grids. Pooranian et al. (2013) have proposed a new hybrid scheduling algorithm that combines GA and the Gravitational Emulation Local Search (GELS) algorithm.