An improved PSO algorithm with genetic and neighborhood-based diversity operators for the job shop scheduling problem

摘要

The job shop scheduling problem (JSSP) is an important NP-hard practical scheduling problem that has various applications in the fields of optimization and production engineering. In this paper an effective scheduling method based on particle swarm optimization (PSO) for the minimum makespan problem of the JSSP is proposed. New variants of the standard PSO operators are introduced to adapt the velocity and position update rules to the discrete solution space of the JSSP. The proposed algorithm is improved by incorporating two neighborhood-based operators to improve population diversity and to avoid early convergence to local optima. First, the diversity enhancement operator tends to improve the population diversity by relocating neighboring particles to avoid premature clustering and to achieve broader exploration of the solution space. This is achieved by enforcing a circular neighboring area around each particle if the population diversity falls beneath the adaptable diversity threshold. The adaptive threshold is utilized to regulate the population diversity throughout the different stages of the search process. Second, the local search operator based on critical path analysis is used to perform local exploitation in the neighboring area of the best particles. Variants of the genetic well-known operators selection and crossover are incorporated to evolve stagnated particles in the swarm. The proposed method is evaluated using a collection of 123 well-studied benchmarks. Experimental results validate the effectiveness of the proposed method in producing excellent solutions that are robust and competitive to recent state-of-the-art heuristic-based algorithms reported in literature for nearly all of the tested instances.