𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Scheduling tasks with communication delays on parallel processors

✍ Scribed by Christian Chenier; Jorge Urrutia; Nejib Zaguia

Publisher
Springer Netherlands
Year
1995
Tongue
English
Weight
518 KB
Volume
12
Category
Article
ISSN
0167-8094

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Using duplication for scheduling unitary
Using duplication for scheduling unitary tasks on m processors with unit communication delays
✍ A. Munier; C. Hanen πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 633 KB

This paper introduces a new list scheduling algorithm that uses greedy duplication to solve a scheduling problem with communication delays and resource limitations. We prove that, for any priority list, its worst-case relative performance is bounded by 2 -l/m and that this bound is tight.

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