Minimizing mean flowtime in a two-machine flowshop with sequence-independent setup times

This paper addresses the two-machine #owshop problem to minimize mean #owtime where setup times are separated and sequence independent. Optimal solutions are obtained for two special cases. For the general case, two dominance relations are established and their e!ectiveness in a branch-and-bound algorithm is evaluated. It is shown that problems up to 35 jobs can be solved optimally in a reasonable time. Moreover, for the general case, three heuristic algorithms are proposed to "nd an approximate solution for larger problems, and they are empirically evaluated to assess their e!ectiveness in "nding the optimal solution. Computational results show that one of the heuristic algorithms has an overall average error of 0.7% from the optimal value and that the error is independent of the number of jobs.