𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by J.A. Hoogeveen; J.K. Lenstra; B. Veltman

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
648 KB
Volume
16
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The Complexity of Scheduling Trees with
The Complexity of Scheduling Trees with Communication Delays
✍ Jan Karel Lenstra; Marinus Veldhorst; Bart Veltman πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 190 KB

We consider the problem of finding a minimum-length schedule on m machines for a set of n unit-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