Research On Task Scheduling Strageties For Grid By Intelligent Optimization Algorithms

The problem of scheduling tasks onto 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. We have investigated some intelligent optimization algorithms, such as Mean Field Annealing Algorithm (MFA), Microcanonical Annealing Algorithm (MA), Genetic Algorithm (GA), etc. And we have applied these algorithms to task scheduling in grid.Firstly, Mean Field Annealing algorithm is applied to the grid task scheduling. We construct the energy function and status-updating function, which meet a variety of restrictive conditions. And simulation experiments show the good ability of optimization.Then we improve the Microcanonical Annealing Algorithm, and applied to the task scheduling. Two strategies are proposed, which are energy incentives strategy with subsection and hybrid energy compensation strategy. And we adopt the he energy function and status-updating function of MFA algorithm in the MA algorithm, which formed a new algorithm---Microcanonical Mean Field Annealing Algorithm (MMFA). This new algorithm ensures that the energy of new state is reduced, so speeds up the search speed and improves performance of the algorithm.Finally, Fuzzy Dynamic Genetic Algorithm (FDGA) is proposed for grid task scheduling. In FDGA, we develop a new coding system considering the dynamics of the grid, and design new operators of selection, crossover and mutation. The fitness function is constructed based on fuzzy evaluation mechanisms, taking into account the makespan, the idle time of hosts and the deadline requirements of tasks. According to the computing power of hosts and load states of network, dynamic scheduling algorithm is carried out to provide users with optimum performance. A local grid simulation model is constructed by OPNET. We realize the FDGA algorithm in this simulation, and compare with other grid task scheduling algorithms (such as Min-min, Max-min, etc.). The simulation results show that the FDGA scheduling algorithm has good ability of optimization, and provide good quality of service.