Scheduling in flowshops with no-idle machines

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 http://www.springer.com/engineering/book/978-3-642-02835-9