The complexity of scheduling trees with communication delays

J.K. Lenstra, M. Veldhorst, B. Veltman

Research output: Contribution to journalArticleAcademicpeer-review

34 Citations (Scopus)

Abstract

We consider the problem of finding a minimum-length schedule onmmachines for a set ofnunit-length tasks with a forest of intrees as precedence relation, and with unit interprocessor communication delays. First, we prove that this problem is NP-complete; second, we derive a linear time algorithm for the special case that m equals 2.
Original languageEnglish
Pages (from-to)157-173
Number of pages17
JournalJournal of Algorithms
Volume20
Issue number1
DOIs
Publication statusPublished - 1996

Fingerprint

Dive into the research topics of 'The complexity of scheduling trees with communication delays'. Together they form a unique fingerprint.

Cite this