Two-machine flowshop scheduling to minimize total completion time with separate setup and removal times

This paper addresses the two-machine flowshop problem with respect to the total completion time performance measure, where setup and removal times are considered as separate from processing times. Optimal solutions are obtained for certain flowshops, and dominance relations are developed for the general problem. A lower bound is established and efficient heuristic algorithms are proposed. The heuristic algorithms and dominance relations are empirically evaluated to assess their effectiveness. Empirical evaluation shows that the dominance relations are quite useful, and that the heuristic algorithms have small error that is independent of the number of jobs.