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

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

    Research output: Contribution to journalArticleAcademicpeer-review

    53 Citations (Scopus)
    1 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; does there exist a schedule 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.
    Original languageEnglish
    Pages (from-to)129-137
    Number of pages9
    JournalOperations Research Letters
    Volume16
    Issue number3
    DOIs
    Publication statusPublished - 1994

    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