Research And Application Of Improved Particle Swarm Optimization In Flow Shop Scheduling Problem

With the globalization of the economy and configuration,the need of customer is becoming more diversified.As a result,the competition of enterprise is becoming more and more intense,especially in the field of manufacturing.In order to survive and get the right of speech in the competition,the enterprises pay more and more attention to the management of production.Flow Shop is now the most widely used form in production.It is very important to study the effect of Flow Shop on the production of enterprises.Based on the actual production status,the Flow Shop scheduling aims to enabling enterprises to achieve the set target and maximize profits.According to literature,we can find that Flow Shop scheduling is a typical NP-Hard which is difficult to solve by traditional methods.Researchers have been trying to find an efficient algorithm to solve this problem,aiming to put it to the actual process of production.Thus the permutation Flow Shop and No-Wait Flow Shop are analyzed and studied in this paper.PSO is an intelligent and optimized algorithm.Its velocity and position can be updated by the best previous position achieved by the individual particle and the global best particle found by all particles.It can quickly search the optimal solution.Therefore,it has been successfully applied to solve the problem of production scheduling.However,the original PSO is mainly applied to solving the consecutive problems while the optimal solution of Flow Shop Scheduling is discrete.Therefore the original PSO often leads to local optimal solution when it is applied to solve the more complex problems.In order to solve this problem,this paper makes some improvement on the original PSO,introducing Simulated Annealing-Particle Swarm Optimization(SPSO)and Crisscross Search-Particle Swarm Optimization(CPSO).SPSO and CPSO are applied to solve Permutation Flow Shop Scheduling Problem(PFSP)and No-Wait Flow Shop Problem(NWFSP).The basic innovations are as follows:.(1)For a Permutation Flow Shop Scheduling Problem,the simulated annealing will be embedded into the updating process of particle swarm particle because of its strong local search ability to escape from local optima.It is named as simulated annealing particle swarm Optimization(SPSO).Through the optimization global best particle found by all particles,it can get rid of entrapment in local optima.In the process of optimization,three kinds of different local searches which are based on swap,insertion and inverse,select the solution by Metropolis acceptance criteria.Then the modified algorithm is applied to solve typical PFSP,through computational testing and results comparing.Thus the effectiveness of SPSO can be proved.(2)For a No-Wait Flow Shop Problem,this paper introduces a novel crisscross search to optimize PSO.It is CPSO.CSO enhances PSO by two search operators,namely horizontal crossover and vertical crossover.The horizontal crossover can enhance information conversion between the particles,improving global convergence ability.Meanwhile,the vertical crossover can enhance the ability of escaping from local optima,adopting embedded and serial way to optimize best previous position achieved by the individual particle.The modified algorithm is applied to solve typical NWFSP.Compared with CPSO-S and original PSO,the simulation shows the proposed CPSO-E is better in the effectiveness and efficiency.