Research On Multiprocessors Scheduling Algorithm In Distributed System

As a typical distributed application system, grid is composed of plenty of heterogeneous distributed shared resources, which collaboratively provide tremendous computing power. The resources feature wide distribution, self-management, heterogeneous in nature, and changing load in grid computing, which makes the task scheduling in the grid environment is much more complicated than that in traditional distributed environment. It has been proved that the task scheduling in grid environment is a NP complete problem (except in rare special conditions). Being the research focus of computer learners and core technology of grid, scheduling can be described as a reasonable solution computing tasks in the geographical distribution of resources between the dynamic scheduling. Generally speaking, a satisfying task scheduling method whose key technical parameter is to achieve optimal allocation strategy in the shortest time, can improve the utilization of the system resources and maintain excellent load balancing of the system.Based on in-depth study of the intelligence algorithm——ant colony algorithm and genetic algorithm, this paper brings them into grid task scheduling. In this paper, the technologies of grid task scheduling have been put forward based on the improved ant colony algorithm and the mixture of ant colony and genetic algorithms.The technology of grid task scheduling based on the improved ant colony algorithm, mainly aims at the shortcoming of makespan, utilization and load balancing. The crucial problem of the technology is how to determine the load, which makes the balance of every crunode's load, so as to realize the shortest execution time and highest utilization that the grid task scheduling requires. The positive feedback results the search easily lead to a local optimal. The improved ant colony algorithm provides a series of improving measurements against this problem: increasing pheromone weight, increasing volatile balance factor, bring into transition probabilities rule and putting limit on the total amount of pheromone.For its random search, the ant colony algorithm work out the answers according to the enlightening information in the first stage at rather low convergence speed. After research of the genetic algorithm, this paper comes up with the mixture of ant colony and genetic algorithm with simulation time as optimal target, which applies both the two algorithms into the grid task scheduling, combining their advantages and removing their disadvantages, therefore the new algorithm is better than them in terms of time efficiency. The new algorithm, before meeting the scheduling requirements, adopts the genetic algorithm, which making full use of the group characteristic and quick search of the genetic algorithm, and then adopts the ant colony algorithm based on encouragement factor, maximizes the use of the positive feedback to solve the optimal solution of tasks quickly.The above algorithms have been proved by the grid resource scheduling simulation tool kits of GridSim and got good results.