Non-approximability results for scheduling problems with minsum criteria

J.A. Hoogeveen, P. Schuurman, G.J. Woeginger

Research output: Book/ReportReportAcademic

70 Downloads (Pure)


We provide several non-??approximability results for deterministic scheduling problems whose objective is to minimize the total job completion time.?? Unless P = NP, none of the problems under consideration can be approximated in polynomial time within arbitrarily good precision.?? Most of our results are derived by Max SNP hardness proofs??. Among the investigated problems are :?? scheduling unrelated machines with job release dates, scheduling ??flow shops, scheduling open shops, scheduling parallel machines with precedence constraints and unit processing times, and two variants of the latter problem with unit communication delays??. Keywords:?? Scheduling, approximation algorithm, approximation scheme, worst??-case analysis, non??-approximability, L-??reduction, unrelated parallel machines, open shop, fl??ow shop, precedence constraints, communication delays??.
Original languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages16
Publication statusPublished - 1997

Publication series

NameMemorandum COSOR
ISSN (Print)0926-4493


Dive into the research topics of 'Non-approximability results for scheduling problems with minsum criteria'. Together they form a unique fingerprint.

Cite this