Minimizing total completion time in a two-machine flowshop: Analysis of special cases

We consider the problem of minimizing total completion time in a two-machine flowshop. We present a heuristic with worst-case bound 2 beta/(alpha + beta), where alpha and beta denote the minimum and maximum processing time of all operations. Furthermore, we analyze four special cases: equal processing times on the first machine, equal processing times on the second machine, processing a job on the first machine takes time no less than its processing on the second machine, acid processing a job on the first machine takes time no more than its processing on the second machine. We prove that the first special case is NP-hard in the strong sense and present an O(n log n) approximation algorithm for it with worst-case bound 4/3. We repeat the easy polynomial algorithms for the cases two and three, and show that problem four is solvable in polynomial time as well.