Research On Task Scheduling Algorithms For Grid Computing By Dynamic Genetic Algorithms

The problem of scheduling heterogeneous tasks onto heterogeneous resources, otherwise known as the task allocation problem, is an NP-hard problem for the general case. Many heuristic algorithms exist for specific instances of the task scheduling problem, but are inefficient for a more general case. The use of Holland's genetic algorithms in scheduling, allows good solutions to be found quickly and for the scheduler to be applied to more general problem. Many researchers have investigated the use of GAs to schedule tasks in homogeneous and heterogeneous multi-processor systems with notable success.Unfortunately, assumptions are often made which reduce the generality of these solutions, such that scheduling can be calculated off-line in advance and cannot change, all communications times are known in advance, all processors have equal capabilities and are dedicated to processing tasks from the scheduler. These assumptions limit the generality of these scheduling strategies in real-world distributed systems. The main characters of grid are dynamic and heterogeneous, so these strategies are not appropriate for grid computing.Desirable goals for grid task scheduling algorithms would shorten average delays, maximize system utilization and fulfill user constraints. In this paper a scheduling strategy is presented which uses a Dynamic GA (DGA) to schedule heterogeneous tasks onto heterogeneous hosts, allowing for tasks to arrive for processing continuously, and considers variable system resources, which has not been considered by other schedulers. In DGA we develop a new coding system and fitness function for local grid computing, and design new operators of selection, crossover and mutation.A local grid simulation model is constructed by OPNET. We realize the DGA algorithm in this simulation, and compare with other grid task scheduling algorithms (such as Min-min, Max-min, FCFS). The simulation results show that the DGA scheduling algorithm has good ability of optimization, and provide good quality of service.