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

This paper addresses the two-machine flowshop problem to minimize mean flow time where setup times are separated and sequence independent. Optimal solu tions are obtained for two special cases. For the general case, two dominan ce 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 solv ed optimally in a reasonable time. Moreover, for the general case, three he uristic 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.