A new hybrid optimization algorithm for the job-shop scheduling problem

A new hybrid optimization 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 employs a collaborative population-based search, which combines local search (by self experience) and global search (by neighboring experience), possessing high search efficiency. Simulated annealing (SA) employs certain probability to avoid becoming trapped in a local optimum. By reasonably combining these two different search algorithms, we develop a general, fast and easily implemented hybrid optimization algorithm, named HPSO. The effectiveness and efficiency of the new algorithm are demonstrated by comparing results with other algorithms on some benchmark problems. Comparing results indicate that PSO-based algorithm is a viable and effective approach for the job-shop scheduling problem.