Scheduling in flowshops with no-idle machines

Research Area: Articulos Year: 2009
Type of Publication: In Book
Authors: Ruiz, Rubén; Vallada, Eva; Fernández-Martínez, Carlos
Editor: Uday K. Chakraborty Volume: 230
Chapter: 2 Pages: 21-52
Publisher: Springer Address: New York
Series: Studies in Computational Intelligence
ISBN: 9783642028359
Part of the book "Computational Intelligence in Flow Shop and Job Shop Scheduling"
This chapter deals with an interesting and not so well studied vari- ant of the classical permutation flowshop problem with makespan criterion. In the studied variant, no idle time is allowed on machines. In order to ensure this no-idle constraint, the start times of jobs on machines must be delayed until all assigned jobs can be processed without incurring in idle times. This is a real situation arising in practice when expensive machinery is operated or when specific machines cannot be easily started and stopped due to technological constraints. We provide a comprehensive characterization and modelization of the no-idle per- mutation flowshop, along with a detailed literature review. Existing methods are critically evaluated. We propose several improvements over existing approaches as well as adaptations of state-of-the-art algorithms that were proposed for related problems. An extensive computational campaign is conducted. Results are care- fully analyzed by means of sound statistical techniques. The results indicate that the recent Iterated Greedy methods outperform existing algorithms by a significant margin.
Also available at
Digital version
[ Back ]