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 fi??rst machine takes time no more than its processing on the second machine, and processing a job on the fi??rst machine takes time no less than its processing on the second machine.?? We prove that the fi??rst 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 show that the other three cases are solvable in polynomial time??. Keywords and Phrases: Flowshop, total completion time, NP??-hardness, heuristics, worst??-case analysis, special cases, polynomial algorithms??.