A two-stage PSO algorithm for job shop scheduling problem

摘要

This paper presents a two-stage particle swarm optimization algorithm for job shop scheduling problems. The algorithm is named 2S-PSO to reflect that two stages with multiple swarms are used. The random key representation is used and the schedules are constructed using a permutation with m-repetitions of job numbers. Performances of the algorithms are tested using benchmark instances for both the single objective and multiobjective cases. For the single objective cases, makespan and weighted tardiness are considered. For the multiobjective cases, three criteria are considered: makespan, weighted carlincss. and weighted tardiness. The solutions are found using the weighted aggregate approach to allow for comparison with published work. In general, the solutions obtained via 2S-PSO dominate those published results in that it provided equal or better solution quality in much shorter computational time.