SEGMENTED AVERAGE-SUFFERAGE HEURISTIC FOR INDEPENDENT TASK SCHEDULING IN GRID

Abstract

Grid Computing enables the secured, controlled and flexible sharing of resources among various dynamically created virtual organizations. These virtual organizations are setup for collaborative problem solving that requires a great number of processing cycles. In high throughput computing, the grid is used to schedule large number of task, with the aim of putting unused processor cycles to work. Grid computing provides highly scalable, highly secure and utmost high performance mechanisms for discovering and negotiating access to the computing resources among an infinite number of geographically distributed groups to solve complex scientific or technical problems. Scheduling is a fundamental issue in achieving high performance on computational grids. An efficient grid scheduling system is an essential part of the grid. Even though middleware support for grid computing. has been the subject of extensive_ research, scheduling policies for the grid context have not been much- studied. In addition to processor utilization, it is important to consider: the waiting time, throughput, and response times of tasks in - evaluating the, performance of grid scheduling strategies. The task scheduling problem for grid computing has been studied as a combinatorial optimization problem, which can be solved only .using heuristic algorithms. In this thesis, we consider the problem of allocating independent, heterogeneous tasks on grid environment. A heuristic namely, Segmented-Average Sufferage for batch mode independent task scheduling is proposed in this dissertation. The segmentation is done to give better makespan and load balancing. The heuristic is tested in GridSim simulator. The experiment results show that the Segmented Average-Sufferage heuristic gives significantly improvements, in makespan, resource utilization and load balancing than existing Sufferage, Min-Min and Max-Min heuristics.