Combining PSO and local search to solve scheduling problems

Intelligent manufacturing is associated with a large number of complex optimization problems and for this reason has got a considerable research attention over the last decades. Most of these problems are of combinatorial nature and have been proved to be NP-complete. This paper deals with the flow shop scheduling problem (FSSP) and the Job Shop Scheduling Problem (JSSP). The objective of these problems is to find an appropriate sequence to minimize the makespan, which are defined as the time for completing a final operation. One major challenging issue is how to obtain the high-quality global optimum. In order to refrain from the premature convergence and being easily trapped into local optimum, we are motivated to find high-quality solutions in a reasonable computation time by exploiting Particle Swarm Optimization (PSO), Tabu Search (TS) and Simulated Annealing (SA). We propose a new multi-structural hybrid evolutionary framework, and derive HPTS algorithm as its extension. Extensive experiments on different scale benchmarks validate the effectiveness of our approaches, compared with other well-established methods. The experimental results show that new upper bounds of the unsolved problems are achieved in a relatively reasonable time. For example, in 30 Tailland's and 43 OR-Library benchmarks, 7 new upper bounds and 6 new upper bounds are obtained by the HPTS algorithm, respectively.