Job-Shop Scheduling Method Based On Particle Swarm Optimization Algorithm

As an important part of CIMS, the job shop scheduling system is combinatorial optimization problem, which belongs to NP problems and is difficult to solve by regular methods. While the study of algorithms is an important aspect of solving scheduling problem, in recent years, some intelligent algorithms have been used for it such as GA (Genetic algorithm) and SA (Simulated Annealing algorithm).etc. Particle swarm optimization (PSO) with the typical characteristic of swarm intelligence is a kind of novel evolution algorithm after ant colony algorithm. As one of novel evolution algorithm, PSO theory recently is recognized in the control field and the computer field broadly. In this case, this paper makes a deep study on the particle swarm algorithm which used on job shop scheduling problem.Firstly, the paper discusses the design of standard particle swarm algorithm for solving the classical job shop scheduling problem in the aspect of engineering. Through the operation-based encoding and speed-location update strategy, the PSO can be used to solve classical job shop scheduling problem effectively. Simulation results show that this PSO algorithm can effectively solve the classical job shop scheduling problem.Secondly, Aim at the traditional particle swarm optimization algorithm for shop scheduling problem with slow convergence and easy to fall into local optimum and other shortcomings, two hybrid algorithms (namely GPSO and PTS) were put forward by combing the PSO and TS. In order to enhance the global search ability the new algorithmes use the preference list-based encoding and embed key operation-based exchange of tabu-search module in different stages. The simulation results show that the two hybrid algorithms for solving job shop scheduling is feasible and efficient.Finally, the particle swarm algorithm for solving flexible job shop scheduling problem is discussed for the flexible job shop scheduling problems is closer to the actual production environment than the classical job shop scheduling problem. In order to speed up the particle to the global optimal convergence and early jump out of local optimum the new algorithm addes mutation to the particles. Simulation results show that this algorithm can effectively solve the flexible job shop scheduling problem.