Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 35, Issue 9, Pages 2807-2839Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2006.12.030
Keywords
no-wait flowshop; makespan; total flowtime; particle swarm optimization; variable neighborhood descent
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available