A modified particle swarm optimization algorithm for a single-machine scheduling problem with periodic maintenance

摘要

In this paper, a particle swarm optimization (PSO) algorithm is presented to solve the single-machine scheduling problem with periodic maintenance activities. The most important issue for applying PSO algorithm successfully to the addressed scheduling problem is how to develop an effective ‘problem mapping’ and ‘construction of a particle sequence’ mechanism. For the problem mapping aspect, we apply the “job-to-position” representation for the particles. For the construction of a particle sequence aspect, we use the largest position value (LPV) rule. Besides, to enhance the effective of the proposed PSO algorithm, we embedded a restarting strategy and three stopping criteria. The objective is to find a schedule that minimizes the makespan. The addressed problem is shown to be NP-hard in the strong sense by transforming to the 3-partition problem. Computational results show that the proposed PSO-M algorithm is quite satisfactory on both solution accuracy and efficiency to solve the addressed problem.