A particle swarm optimization algorithm based on the reverse operator for the job shop scheduling problem

摘要

In this paper, we propose a meta-heuristic algorithm for the job shop scheduling problem (JSSP) with total weighted tardiness criterion. First, we focus on the mathematical programming model and discuss its duality when the processing sequences on each machine are fixed. Then, a reverse-based neighborhood structure is defined and its important properties are shown. Finally, a particle swarm optimization algorithm is presented, which utilizes the neighborhood properties to promote the optimization efficiency. According to the computational results, the new neighborhood considerably promotes the searching capability of particle swarm optimization and accelerates its convergence to high-quality solutions.