𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of scheduling with large communication delays

✍ Scribed by Evripidis Bampis; Aristotelis Giannakos; Jean-Claude König

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
736 KB
Volume
94
Category
Article
ISSN
0377-2217

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

Scheduling chains on uniform processors
Scheduling chains on uniform processors with communication delays
✍ Wieslaw Kubiak1; Bernard Penz; Denis Trystram 📂 Article 📅 2002 🏛 Springer US 🌐 English ⚖ 200 KB

We show that the problem of scheduling chains of unit execution time (UET) jobs on uniform processors with communication delays to minimize makespan is NP-hard in the strong sense. We also give a heuristic that generates solutions with known, and relatively small, absolute error for this problem. Th

Sensitivity analysis of tree scheduling
Sensitivity analysis of tree scheduling on two machines with communication delays
✍ Frédéric Guinand; Aziz Moukrim; Eric Sanlaville 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 282 KB

This paper presents a sensitivity analysis for the problem of scheduling trees with communication delays on two identical processors, to minimize the makespan. Tasks are supposed to have unit execution time (UET UET), and the values associated to communication delays are supposed unknown before the