APPLICATION OF IMPROVED PARTICLE SWARM OPTIMIZATION ALGORITHM IN JOB SHOP SCHEDULING PROBLEM

Abstract

Job shop scheduling problem(JSSP) is a typical NP-hard combinatorial optimization problem in the field of production management. Many different algorithms have been applied to solve combinatorial optimization problems, such as genetic algorithm(GA), particle swarm optimization(PSO), heuristic algorithm and so on. However, it is difficult to guarantee the optimization of the JSSP even on a small scale. The original particle swarm optimization (PSO) algorithm is generally used to solve the continuous function problem and to help solve the discrete problem. This paper proposes an improved particle swarm optimization algorithm for JSSP. The idea of genetic algorithm is introduced into PSO to perform crossover mutation operation on the particles in solution space to ensure the diversity of particle population. In order to avoid the traditional particle swarm optimization algorithm easy to fall into local optimum when solving JSSP, a nonlinear dynamic weight method is adopted. The experiments show that the improved particle swarm optimization (IPSO) algorithm is more robust and efficient in dealing with the workshop scheduling problem.