Balanced Job Scheduling Based on Ant Algorithm for Grid Network

Balanced Job Scheduling Based on Ant Algorithm for Grid Network

Nikolaos Preve (National Technical University of Athens, Greece)
Copyright: © 2010 |Pages: 17
DOI: 10.4018/jghpc.2010092803
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Job scheduling in grid computing is a very important problem. To utilize grids efficiently, we need a good job scheduling algorithm to assign jobs to resources in grids. The main scope of this article is to propose a new Ant Colony Optimization (ACO) algorithm for balanced job scheduling in the Grid environment. To achieve the above goal, we will indicate a way to balance the entire system load while minimizing the makespan of a given set of jobs. Based on the experimental results, the proposed algorithm confidently demonstrates its practicability and competitiveness compared with other job scheduling algorithms.
Article Preview

Introduction

The early efforts in Grid computing started as a project to link supercomputing sites, but have now grown far beyond the original intent. The popularity of the Internet, the availability of powerful computers and the high-speed network technologies as well as low cost commodity components, are changing the way we use computers today. These technology opportunities have led to the possibility of using distributed computers as a single, unified computing resource, leading to what is popularly known as Grid computing.

Today’s scientific problems are very complex and need huge computing power and storage capability. Computational Grids are emerging as a new paradigm for solving large scale problems in science and engineering. A Grid scheduler acts as an interface between the user and the distributed resources hiding the complexities of Grid computing (Abramson, Giddy, & Kotler, 2000; Buyya, Abramson, & Giddy, 2000). It is also responsible for monitoring and tracking the progress of application execution along with adapting to the changes in the runtime environment of the Grid, variation in resource share availability and failures. A Grid scheduler balances the entire system load while completing all the jobs at hand as soon as possible according to the environment status. The existing job scheduling algorithm such as First Come First Serve (FCFS), Shortest Job First (SJF) may not be suitable for the grid environment. These algorithms seize a lot of computational time due to soar waiting time of jobs in job queue reducing the entire system performance (Somasundaram & Radhakrishnan, 2009; Yan, Wang, Wang, & Chang, 2009).

The users who interact with the Grid can manually assign jobs to computing resources in grids. Thus, grid job scheduling is a very important issue in Grid computing. Referring to the Berkeley Open Infrastructure for Network Computing (BOINC, 2009) project, we will find out an open source platform for volunteer computing and grid computing. Here, job scheduling is one of the most important key factors for achieving Teraflops performance (Kondo, Anderson, & McLeod, 2007). We can also notice that grid scheduling concentrates in improving response times in an environment containing autonomous resources whose availability dynamically varies with time. The Grid scheduler has to interact with the local schedulers managing computational resources and adapt its behavior to changing resource loads. Thus, the scheduling is conducted from the perspective of the user rather than that of the system. Because of its significant importance many job scheduling algorithms for Grids have been proposed in order to obtain a load balancing distribution of processes to computational resources, but open issues still exist (Boyera & Hura, 2005; Buyya, Cortes, & Jin, 2001; Collins & George, 2001; De Ronde, Schoneveld, & Sloot, 1997; Dong & Akl, 2004; Dorigo & Gambardella, 1997; Foster & Kesselman, 2003; Maghraoui, 2006; Nabrzyski, Schopf & Weglarz, 2004; Salari & Eshghi, 2005; Karatza & Hilzer, 2003; Sonmez & Gursoy, 2007). When things come to practice it is impossible to find a tool for the automatic load balancing of a parallel distributed application.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing