Nature's heuristics for scheduling jobs on Computational Grids

TLDR

Grid computing unifies geographically distributed resources to meet the growing computational demands of Grand Challenge Applications, yet scheduling remains complex, prompting the use of nature-inspired heuristics that have proven effective for combinatorial optimization. The paper aims to develop a job scheduling strategy for geographically distributed computing resources. The authors introduce computational grids and apply three nature-based heuristics—Genetic Algorithm, Simulated Annealing, and Tabu Search—to the scheduling problem. Experimental results demonstrate that Genetic Algorithm alone performs well, and a hybrid combination of GA, SA, and TS can be effectively applied for job scheduling in computational grids.

Abstract

Computational Grid (Grid Computing) is a new paradigm that will drive the computing arena in the new millennium. Unification of globally remote and diverse resources, coupled with the increasing computational needs for Grand Challenge Applications (GCA) and accelerated growth of the Internet and communication technology will further fuel the development of global computational power grids. In this paper, we attempt to address the scheduling of jobs to the geographically distributed computing resources. Conventional wisdom in the field of scheduling is that scheduling problems exhibit such richness and variety that no single scheduling method is sufficient. Heuristics derived from the nature has demonstrated a surprising degree of effectiveness and generality for handling combinatorial optimization problems. This paper begins with an introduction of computational grids followed by a brief description of the three nature's heuristics namely Genetic Algorithm (GA), Simulated Annealing (SA) and Tabu Search (TS). Experimental results using GA are included. We further demonstrate the hybridized usage of the above algorithms that can be applied in a computational grid environment for job scheduling.