A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem

In this paper, a discrete particle swarm optimization (DPSO) algorithm is presented to solve the no-wait flowshop scheduling problem with both makespan and total flowtime criteria. The main contribution of this study is due to the fact that particles are represented as discrete job permutations and a new position update method is developed based on the discrete domain. In addition, the DPSO algorithm is hybridized with the variable neighborhood descent (VND) algorithm to further improve the solution quality. Several speed-up methods are proposed for both the swap and insert neighborhood structures. The DPSO algorithm is applied to both 110 benchmark instances of Taillard [Benchmarks for basic scheduling problems. European Journal of Operational Research 1993;64:278 - 851 by treating them as the no-wait flowshop problem instances with the total flowtime criterion, and to 31 benchmark instances provided by Carlier [Ordonnancements a contraintes disjonctives. RAIRO Recherche operationelle 1978;12:333 - 51], Heller [Some numerical experiments for an M x J flow shop and its decision-theoretical aspects. Operations Research 1960;8:178 - 84], and Revees [A genetic algorithm for flowshop sequencing. Computers and Operations Research 1995;22:5 - 13] for the makespan criterion. For the makespan criterion, the solution quality is evaluated according to the reference makespans generated by Rajendran [A no-wait flowshop scheduling heuristic to minimize makespan. Journal of the Operational Research Society 1994;45:472 - 8] whereas for the total flowtime criterion, it is evaluated with the optimal solutions, lower bounds and best known solutions provided by Fink and VoB [Solving the continuous flow-shop scheduling problem by metaheuristics. European Journal of Operational Research 2003;151:400 - 14]. The computational results show that the DPSO algorithm generated either competitive or better results than those reported in the literature. Ultimately, 74 out of 80 best known solutions provided by Fink and VoB [Solving the continuous flow-shop scheduling problem by metaheuristics. European Journal of Operational Research 2003; 151:400 - 14] were improved by the VND version of the DPSO algorithm. (c) 2007 Published by Elsevier Ltd.