Research On Job-shop Scheduling Problem Based On Improved Particle Swarm Optimization

Job-shop scheduling problem is a simplified model of the actual production scheduling problem, is a core of production management and control for enterprise. Effective scheduling method and optimization technology research and application have important theoretical significance and practical value.Particle swarm optimization is an evolutionary algorithms that based on swarm intelligence and developed in recent years,owing to its simple operation and easy to implement such features, however, as the algorithm proposed by a relatively short time, it still has some problems,such as easy to premature convergence, easy to fall into local minimum, etc. Therefore, this article has improved the algorithm, and applied the improved algorithm to job shop scheduling problem.This article first described job-shop scheduling problem, including job-shop scheduling problem model, features, research state at home and abroad and the optimization method of solving shop scheduling problem. Second, introducing the origin of the particle swarm optimization algorithm, the basic idea, mathematical description,algorithms processes and improvements, as well as defects in particle swarm optimization. Again, according to the optimization theory base that has been existed and the characteristics of the parameters of particle swarm optimization algorithm, this article propose an improved particle swarm optimization which inertia weight dynamic non-linear changing with the increase of iterative generation and immune particle swarm optimization.By selecting a few representative function to test, found that the improved particle swarm algorithm have improved in convergence accuracy and convergence speed.Finally, according to the characteristics of job-shop scheduling problem, this article established a mathematical model of solving job-shop scheduling problem. Through researching encoding method of job-shop scheduling problem and referencing the particle encoding method of the genetic algorithm, this article use encoding methods that based on processes and use the minimum of maximum completion as target, constructed solving method for job-shop scheduling problem based on improved particle swarm algorithm, and simulation results show that improved algorithms have progresses on property and certify effectiveness and feasibility of improved algorithm.