Three, four, five, six or the complexity of scheduling with communication delays

J.A. Hoogeveen, J.K. Lenstra, B. Veltman

Research output: Book/ReportReportAcademic

55 Downloads (Pure)

Abstract

A set of unit·time tasks has to be processed on identical parallel processors subject to precedence constraints and unit·time communication delays; doesthere exist aschedule of length at most d? The problem has two variants, depending on whether the number of processors is restrictively small or not. For the first variant the question can be answered in polynomial time for d=3 and is NP-complete for d=4. The second variant is solvable in polynomial time for d=5 and NP-complete for d=6. As a consequence, neither of the corresponding optimization problems has a polynomial approximation scheme, unless P=NP. Key Words & Phrases: Identical parallel processors, precedence constraints, communication delays, makespan, complexity, approximation.
Original languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages8
Publication statusPublished - 1993

Publication series

NameMemorandum COSOR
Volume9319
ISSN (Print)0926-4493

Fingerprint Dive into the research topics of 'Three, four, five, six or the complexity of scheduling with communication delays'. Together they form a unique fingerprint.

Cite this