Grid Task Scheduling Algorithm under the Improved PSO Algorithm
|School||Central South University|
|Course||Computer Science and Technology|
|Keywords||task scheduling PSO Chaos optimization optimum makespan load balancing|
Grid is currently the most active part of distributed computing research field, organizes the heterogeneous resources in different administrative domains flexibly and effectively in the form of VO(virtual organization) and coordinates the completion of large computing tasks. Task scheduling is the key issue of grid environment, and directly affects the performance of grid. Taking account to the individual needs of scheduling tasks, how to effectively allocate the tasks to the computing resources rationally, it’s the main content of task scheduling in grid. In addition, as the grid is characterized by dynamic, herogeneous, distributed and so on, the issue of task scheduling in grid is becoming particularly complicated and it has become a hot issue of current grid research and also been proved to be a NP complete problem. So it is of great importance to find a better scheduling strategy which can shorten the completion time as much as possible and efficiently balance the workload of system resources.In recent years, employing the heuristic algorithms in the field of task scheduling is on the rise, and the research results are much better. As a new one, Particle swarm optimization, PSO, is widely used for tasks scheduling which has quick search speed, simple operation, high efficiency, and can efficency resolve the NP complete problem. Some simulation results show that:compared to other heruristic algorithms, PSO algorithm has more advantages in the tasks scheduling. But it is easy to fall into local optimal solution, and the accuracy is not high when solving problems as some defects.Aimming at the shortage of the PSO algorithm, the problem of independent task scheduling under the restraint of time QoS is studied, and a grid task scheduling algorithm based on an improved PSO algorithm is proposed(An improved PSO of grid scheduling algorithm under the meta task). The main idea of this algorithm is, it firstly initializes a large number of particles using chaotic sequences, and then selects the best particles from the generated particles as the initial population; Secondly, it introduces the chaos search while updating the particles, randomly generates several chaos sequences and selects the best one to compare with the best position of current particle. If it is better than the current, then updates the current particle’s best position with it to guide the particle to jump out of the current local optimum and find the best solution quickly.Experiments show that this algorithm can improves the problem which the PSO algorithm is easily to be trapped into local optimum. At the same time, it also can takes better makespan and the performation of load balance into account, and improve the performation of grid system.