Research On Permutation Flow-shop Scheduling Based On Improved Particle Swarm Optimization

Permutation Flow-shop Scheduling Problem(PFSP)is a typical combinatorial optimization problem and a common scheduling problem in real production.It widely exists in various manufacturing industries.The essence of the scheduling problem is to reasonably allocate resources,arrange processes or other operations under the condition of satisfying constraints and production needs,so as to optimize one or more indicators.Production scheduling is the foundation for enterprises to carry out various production activities.A good scheduling plan can improve production efficiency,shorten the completion cycle and reduce manufacturing costs,so that enterprises are in a favorable position in the market.Theoretically,most of the job-shop scheduling problems are NP-hard problems,and their solutions involve many fields such as operations research,mathematics,computer science and industrial engineering.The in-depth study of this problem will help promote the intersection of scheduling theory and other disciplines,and provide reference for other combinatorial optimization problems.With the expansion of the scale of scheduling problems and the deepening of scientific research,the requirements for the complexity and efficiency of solving algorithms are getting higher and higher.How to design efficient intelligent algorithms to solve such problems has become an important issue in the field of production scheduling.This paper mainly studies the improved Particle Swarm Optimization(PSO)to solve permutation flow-shop scheduling problem and No Wait Permutation Flow-shop Scheduling Problem(NWPFSP).Aiming at the permutation flow-shop scheduling problem,the problem characteristics and model are analyzed,and a Genetic Algorithm-Particle Swarm Optimization(GA-PSO)is proposed.For the discrete shop scheduling problem,the algorithm uses an encoding method based on the Ranked Order Value(ROV)rule to realize the mapping from the particle position to the job sequence.The traditional particle swarm optimization is improved by randomly generating initial particles.The initial population is generated by random + NEH initialization,and it is compared with other initialization methods.Aiming at the shortcomings of the traditional particle swarm optimization in parameter setting,which is easy to fall into local extremum,an adaptive strategy is introduced to dynamically adjust the size of the parameters to better match the search process,and two different adaptive inertia weights are verified.Through the test and analysis of different crossover and mutation operators,the optimal crossover and mutation operators are determined,and the adaptive crossover and mutation probability is designed to make the algorithm have better convergence and higher search efficiency.Finally,the values of each parameter of the algorithm are determined by orthogonal test,and then tested by Carlier example,Reeves example and Taillard example,and compared with other algorithms to verify the effectiveness of the algorithm.Aiming at the no wait permutation flow-shop scheduling problem,the characteristics and models of the problem are analyzed.Based on the genetic algorithm-particle swarm optimization,the Profile-Fitting population initialization method and the new particle acceptance mechanism based on the Metropolis criterion are introduced.A Hybrid Particle Swarm Optimization(HPSO)is proposed.Finally,the values of the parameters of the algorithm are determined by orthogonal test,and then tested by Carlier example and Reeves example,and compared with other algorithms to verify the effectiveness of the hybrid particle swarm optimization.