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.