Font Size: a A A

Research On Grid Task Scheduling Using Improved Shuffled Frog Leaping Algorithm

Posted on:2012-03-24Degree:MasterType:Thesis
Country:ChinaCandidate:Y S SunFull Text:PDF
GTID:2218330344450921Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
The grid is a new research direction in the filed of distributed computing, will be playing an increasingly vital role in the future, attracting a large number of experts to devote to the grid. Grid is an enviroment that integrates computing and information services, which link geographically distributed computing resources with network and transform them into a convenient, economical and reliable computing power to achieve resource sharing. Owing to the characters of dynamic, heterogeneousness, self-ruling of a grid, how to match grid tasks and resources to achieve the best performance is one of the key research fileds of grid, whic is also the main content of this paper.Grid task scheduling is a kind of combinatorial optimization problem, the grid scholar has done a lot of research. Many classical combinatorial optimization algorithm, such as Genetic algorithm, Particle swarm algorithm, Min_Min algorithm and so on, have successfully applied in solving the grid task scheduling. Shuffled Frog leaping Algorithm (SFLA) is a heuristic algorithm to solve optimization problems, has been successfully applied to solve various scheduling problems.Based on the analysis of SFLA algorithm and the grid task scheduling, in light of the own defects of SFLA, such as easy to fall into local optimum and lack of information sharing, following a few studies: Firstly, consider "like father, like son" the natural evolution, in view of Min-Min algorithm is simple and can get a better result in a short time. So a new initial population strategy combines Min-Min algorithm with the random algorithm, which improves the quality of the initial population and maintain the diversity of population. At the same time, the new stratigey can quickly converge to the global optimal solution. Secondly, based on the dependence of population evolution on local maximum, local minimum added to the genetic operators, expanding the scope of local research and reduce the risk of falling into local optimum. Meanwhile, the particle updates thought in PSO algorithm reference to the worst of SFLA frog algorithm moves the individual steps of formula optimization. Finally, in the shuffle process, local maxima of various ethnic groups to add genetic operators to enhance information sharing between individuals to improve the diversity of population, to accelerate the convergence speed.To evaluate the performance of improved SFLA algorithm, this paper simulates the algorithm with Gridsim simulator and JCreator IDE environment. The experiment results show that the algorithm is feasible and improves the throughout of the grid system.In the paper, from population initialization, individual vector updates and mix processing on the SFLA algorithm is improved, and then simulated by Gridsim simulator. The experiment results show that the reformative SFLA algorithm effective, and will be helpful for the future study of grid task scheduling.
Keywords/Search Tags:Grid, Grid Task Scheduling, Shuffled Frog Leaping Algorithm, Local search, Shuffling Process
PDF Full Text Request
Related items