A new heuristic and dominance relations for no-wait flowshops with setups

The two-machine no-wait flowshop problem, where setup times are considered separate from processing times and sequence independent, is addressed with respect to minimizing total flowtime. A local and a global dominance relation are developed and a new heuristic is provided. Furthermore, a lower bound is obtained and used along with the dominance relations in a branch-and-bound algorithm in order to evaluate the efficiency of the heuristic. Computational experience demonstrates the superiority of the local dominance relation and the new heuristic.Scope and purposeNo-wait flowshop problems, where jobs have to be processed without interruption between consecutive machines, represent an important area in scheduling. There are several industries where the no-wait flowshop problem applies including the metal, plastic, and chemical industries. For instance, in the case of steel production, the heated metal must continuously go through a sequence of operations before it is cooled in order to prevent defects in the composition of the material. Another important area arises when setup time is considered separate from processing time. Such a consideration is particularly justified when the ratio of setup to processing time is non-negligible. Many applications warrant separate consideration of setup; examples include the re-tooling of multi-tool equipment. Other applications can be found in textile, plastic, chemical, and semi-conductor industries. This paper develops a new heuristic and dominance relations for the two-machine no-wait separate setup flowshop problem, where the performance criterion is total flowtime.