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 optimization problem we conduct an analysis
of the structure of good quality solutions. This analysis shows that the
No-Wait specificity gives them a common structure: they share identical
sub-sequences of jobs, we call super-jobs. After a discussion on the way to
identify these super-jobs, we propose IG-SJ, an algorithm that exploits
super-jobs within the state-of-the-art algorithm for the classical permutation
flowshop, the well-known Iterated Greedy (IG) algorithm. An iterative approach
of IG-SJ is also proposed. Experiments are conducted on Taillard's instances.
The experimental results show that exploiting super-jobs is successful since
IG-SJ is able to find 64 new best solutions.
