An effective hybrid particle swarm optimization for no-wait flow shop scheduling

作者：Liu Bo^*; Wang Ling; Jin Yi Hui

来源：International Journal of Advanced Manufacturing Technology, 2007, 31(9-10): 1001-1011.

DOI：10.1007/s00170-005-0277-5

• flow shop scheduling
• no-wait
• makespan
• particle swarm optimization
• simulated annealing
• local search

The no-wait flow shop scheduling that requires jobs to be processed without interruption between consecutive machines is a typical NP-hard combinatorial optimization problem, and represents an important area in production scheduling. This paper proposes an effective hybrid algorithm based on particle swarm optimization (PSO) for no-wait flow shop scheduling with the criterion to minimize the maximum completion time (makespan). In the algorithm, a novel encoding scheme based on random key representation is developed, and an efficient population initialization, an effective local search based on the Nawaz-Enscore-Ham (NEH) heuristic, as well as a local search based on simulated annealing (SA) with an adaptive meta-Lamarckian learning strategy are proposed and incorporated into PSO. Simulation results based on well-known benchmarks and comparisons with some existing algorithms demonstrate the effectiveness of the proposed hybrid algorithm.

• 出版日期2007-1
• 单位清华大学