A hybrid discrete particle swarm optimization algorithm for the no-wait flow shop scheduling problem with makespan criterion

This paper proposes a novel hybrid discrete particle swarm optimization (HDPSO) algorithm to solve the no-wait flow shop scheduling problems with the criterion to minimize the maximum completion time (makespan). Firstly, a simple approach is presented in the paper to calculate the makespan of a job permutation. Secondly, a speed-up method is proposed to evaluate the similar insert neighborhood solution. Thirdly, a discrete particle swarm optimization (DPSO) algorithm based on permutation representation and a local search algorithm based on the insert neighborhood are fused to enhance the searching ability and to balance the exploration and exploitation. Then, computational simulation results based on the well-known benchmarks and statistical performance comparisons are provided. It is concluded that the proposed HDPSO algorithm is superior to both the single DPSO algorithm and the existing hybrid particle swarm optimization (HPSO) algorithm from literature in terms of searching quality, robustness and efficiency.