Application of PSO with Different Typical Neighbor Structure to Complex Job Shop Scheduling Problem

Abstract: Job shop scheduling is to schedule a set of jobs on a set of machines, which is subject to the constraint that each machine can process at most one job at a given time and the fact that each job has a specified processing order through the machines. It is not only a NP-hard problems, it also has the well-earned reputation of being one of the strong combinatorial problems in manufacturing systems. In this paper, the job-shop scheduling problem (JSSP), with the optimization goal of the scheduling problem is minimum of total process time Cmax, was modeled. An improved particle swarm optimization with acceleration factor (AFPSO) is proposed to improve the ability of particles to explore the global and local optimization solutions, and to reduce the probability of being trapped into the local optima. The neighbor structure of different particle candidate was studied to improve the information exchange speed in optimizing process. Simulation results show that the proposed model and algorithm are effective to task evaluation and implementation