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

J.A. Hoogeveen, T. Kawaguchi

Research output: Book/ReportReportAcademic

6 Citations (Scopus)
43 Downloads (Pure)

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 languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages29
Publication statusPublished - 1996

Publication series

NameMemorandum COSOR
Volume9627
ISSN (Print)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.

Cite this