Particle Swarm Optimization Algorithm And Its Application To The Job-Shop Scheduling Problems

Particle swarm optimization(PSO) is a swarm intelligent algorithm which is base on imitating the bird flock's preying behavior, through group cooperation and competition among individuals to achieve optimization problems. The main virtue of PSO is simple in principle, few in tuning parameters, speedy in convergence and easy in implementation. So, it attracts more and more researchers'attention. Now, PSO is widely used for the optimization of functions, Neural Network Training and multi-target and obtains good effect. But the PSO algorithm is Difficult to meet the actual needs for the characteristics of the practical engineering problems always is complexity, onstraint and difficulty etc, there are many issues need to study and improvement.This paper mainly studies the PSO algorithm. First examine the basic algorithm of PSO, analysis the theory and the algorithm flow, summarized the parameters'set. Discuss a variety of improved methods. Especially improved from the specific parameters of PSO algorithm to set and adjust tactics, PSO algorithm topology, combined with three other intelligent algorithms three aspects. Then, as a strategy to improve particle swarm optimization, based on simulated annealing particle swarm algorithm to compare the basic particle swarm algorithm computational efficiency. Focusing on the two kinds of particle swarm algorithm convergence speed, can effectively avoid precocious, get the optimal solution characteristics such as degree. Experiment'by testing function to verify the superiority of the algorithm. Finally, based on simulated annealing particle swarm algorithm is applied to job shop scheduling (JSP) to solve the problem, Minimize the maximum completion time for the JSP, is given based on random keys and disjunctive graph encoding and decoding method, using the critical path method scheduling and particles generated to evaluate, at the same time of the use of particle swarm optimization algorithm operating, designing a critical path-based neighborhood structure, strategy based on simulated annealing local search algorithm to improve the overall performance. The experiment tested PSO algorithm based on simulated annealing have access to the various examples the optimal solution, there is a very good search quality. Meanwhile, the algorithm is run independently many times and the worst solution of the average income is very close to, or even the same, so the initial cluster algorithm has good robustness. And the improved algorithm is superior to a variety of PSO have achieved good results.