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

This paper addresses the two-machine flowshop problem to minimize mean flowtime 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 effectiveness 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 find an approximate solution for larger problems, and they are empirically evaluated to assess their effectiveness in finding 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.