An Improved Min-Mean Heuristic Scheduling Algorithm for Mapping Independent Tasks on Heterogenous Computing Environment

摘要

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 independent jobs, 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. The job scheduling problem for grid computing has been studied as a combinatorial optimization problem. The combinatorial problem can be solved only using heuristic algorithms. In this paper, we consider the problem of allocating independent, heterogeneous jobs on grid environment. A heuristic job scheduling algorithm with resource load balance is presented. Improved Min-mean heuristic scheduling algorithm schedules jobs by employing the mean completion time of the machines, which reflects the overall performance of all available machines, and it is a high efficient algorithm. The experiment results show that the Improved Min-mcan heuristic scheduling algorithm performs significantly to ensure high throughput, reduced makespan and reduced idle time of the machines.