A hybrid particle swarm optimization approach for the job-shop scheduling problem

A new approximation algorithm is proposed for the problem of finding the minimum makespan in the job-shop scheduling environment. The new algorithm is based on the principle of particle swarm optimization (PSO). PSO combines local search (by self-experience) and global search (by neighboring experience), and possesses high search efficiency. Simulated annealing (SA) employs certain probability to avoid becoming trapped in a local optimum and the search process can be controlled by the cooling schedule. By reasonably combining these two different search algorithms, we develop a general, fast and easily implemented hybrid optimization algorithm; we called the HPSO. The effectiveness and efficiency of the proposed PSO-based algorithm are demonstrated by applying it to some benchmark job-shop scheduling problems. Comparison with other results in the literature indicates that the PSO-based algorithm is a viable and effective approach for the job-shop scheduling problem .