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

J.A. Hoogeveen, T. Kawaguchi

6 Citations (Scopus)

## Abstract

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??.
Original language English Eindhoven Technische Universiteit Eindhoven 29 Published - 1996

### Publication series

Name Memorandum COSOR 9627 0926-4493

## Fingerprint

Dive into the research topics of 'Minimizing total completion time in a two-machine flowshop : analysis of special cases'. Together they form a unique fingerprint.