A hybrid particle swarm optimization and simulated annealing algorithm for job-shop scheduling

It is a NP-Hard problem to obtain optimal solutions to deal with the large-size job-shop scheduling problem (JSSP). In this paper, a new hybrid algorithm based on traditional particle swarm optimization (PSO) algorithm for addressing a JSSP is proposed. Firstly, a particles encoding is designed to reduce the range of solution space. Secondly, a simulated annealing operator combined with local search operator is immersed into the algorithm to extricate itself from local optimal solution, and the performance of the individual search is improved as well. Furthermore, an interference operator is integrated to search the optimal solution by the rapid convergence features. Experimental results based on benchmark problems of LA instances and some FT instances demonstrate that the proposed hybrid algorithm shows higher performance in dealing with the classical large-scale problem than the original design.