TY - BOOK
T1 - Minimizing total completion time in a two-machine flowshop : analysis of special cases
AU - Hoogeveen, J.A.
AU - Kawaguchi, T.
PY - 1996
Y1 - 1996
N2 - 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??.
AB - 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??.
M3 - Report
T3 - Memorandum COSOR
BT - Minimizing total completion time in a two-machine flowshop : analysis of special cases
PB - Technische Universiteit Eindhoven
CY - Eindhoven
ER -