An Iterated Greedy-based Approach Exploiting Promising Sub-Sequences of Jobs to solve the No-Wait Flowshop Scheduling Problem

The no-wait flowshop scheduling problem is a variant of the classical permutation flowshop problem , with the additional constraint that jobs have to be processed by the successive machines without waiting time. To efficiently address this NP hard combinatorial problem we conducted an analysis of the structure of good quality solutions. This study shows that the No-Wait specificity gives them a common structure: they share identical sub-sequences of jobs. After a discussion on the way to identify these sub-sequences, we propose to exploit them into the well-known Iterated Greedy algorithm. Experiments are conducted on Taillard's instances. The experimental results show the proposed approach is efficient and robust, and is able to find out new best solutions for all the largest instances.