A similar particle swarm optimization algorithm for job-shop scheduling to minimize makespan

摘要

The job-shop scheduling problem (JSSP) is a branch of production scheduling, and it is well known that this problem is NP-hard. Many different approaches have been applied to JSSP and a rich harvest has been obtained. However, some JSSP, even with moderate size, cannot be solved to guarantee optimality. The standard particle optimization algorithm generally is used to solve continuous optimization problems, and is used rarely to solve discrete problems such as JSSP. This paper presents a similar PSO algorithm to solve JSSP. At the same time, some new valid algorithm operators are proposed in this paper, and through simulation we find out the effectiveness of them. Three representative (Taillard) instances were made by computational experiments, through comparing the SPSO algorithm with standard GA, and we obtained that the SPSOA is more clearly efficacious than standard GA for JSSP to minimize makespan.