A Hybrid Algorithm of PSO and SA for Solving JSP

Abstract

A hybrid algorithm of particle swarm optimization (PSO) and simulated annealing (SA) algorithm (HPSOSA) is proposed, which is used to overcome the deficiency of resolving job shop problem (JSP) and improve the quality of searching solutions. According to the characteristics of random and large-scale search of PSO, we adopt PSO to construct the parallel initial solutions of SA. At the same time, we increase shifting bottleneck technology and memory device in local SA. By this way, the search efficiency of SA is improved. HPSOSA algorithm has been tested with the 13 hard benchmark problems. The result shows that the average relative error percentage of the average value in ten time experiments is 2.46% and 0.08% which are respectively smaller than parallel genetic algorithm (PGA) and taboo search algorithm with back jump tracking (TSAB). So it can be concluded that the proposed hybrid particle swarm optimization algorithm is effective.