A Novel Heuristic for a Class of Independent Tasks in Computational Grids

Abstract

Scheduling is an essential layer in grid environment. Now-a-days, the computational grids are the important platform for job scheduling. The performance of the computational grids can be improved using an ecient scheduling heuristic. A user submits a job to grid resource broker. The broker is responsible for dividing a job into a number of tasks. It maps the task and the resource to nd a perfect match. The main goal is to minimize the processing time and maximize the resource utilization. Mode of scheduling plays the key role in Grid Scheduling. In Grid, mode of scheduling is of two types: immediate and batch mode. Immediate mode takes one after another task in a serial sequence. But, batch mode takes in a random sequence. Task assignment is mainly based on the mode selection. Task may be assigned to the resource in a batch or as soon as it arrives. In this thesis, we have introduced three immediate mode heuristics such as First-DualMake, Best- DualMake and Worst-DualMake (dened as X-DualMake) and a new mode of heuristic called as intermediate mode (or Multi- batch mode). In our immediate mode scheduling heuristics, jobs are scheduled based on resource idle time. Intermediate mode considers random arrival of task in a multi-batch sequence. Alternatively, arrival of tasks are unknown in this mode. Here, we have taken a range of task arrival for simplicity. This mode is introduced to be a part of the real life aspects. The eight immediate mode heuristics are simulated and the experimental results are discussed. The two existing approaches: Min-Min and Max-Min are experimented with intermediate mode scheduling. We have taken two performance measures: makespan and resource utilization to evaluate the performance.