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

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

Tarun Kumar Ghosh (Department of Computer Science & Engineering, Haldia Institute of Technology, West Bengal, India) and Sanjoy Das (Department of Engineering & Technological Studies, Kalyani University, West Bengal, India)
Copyright: © 2018 |Pages: 11
DOI: 10.4018/IJAMC.2018010104

Abstract

Computational Grid has been employed for solving complex and large computation-intensive problems with the help of geographically distributed, heterogeneous and dynamic resources. Job scheduling is a vital and challenging function of a computational Grid system. Job scheduler has to deal with many heterogeneous computational resources and to take decisions concerning the dynamic, efficient and effective execution of jobs. Optimization of the Grid performance is directly related with the efficiency of scheduling algorithm. To evaluate the efficiency of a scheduling algorithm, different parameters can be used, the most important of which are makespan and flowtime. In this paper, a very recent evolutionary heuristic algorithm known as Wind Driven Optimization (WDO) is used for efficiently allocating jobs to resources in a computational Grid system so that makespan and flowtime are minimized. In order to measure the efficacy of WDO, Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) are considered for comparison. This study proves that WDO produces best results.
Article Preview

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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): 1 Released, 3 Forthcoming
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
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