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 -