✦ LIBER ✦

Approximation algorithms for scheduling trees with general communication delays

✍ Scribed by Alix Munier

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 101 KB
Volume: 25
Category: Article
ISSN: 0167-8191
DOI: 10.1016/s0167-8191(98)00101-x

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the problem of scheduling a tree with general communication delays. Jakoby and Reischuk proved that this problem is NP-hard for binary trees and unlimited number of processors. Firstly, we develop a clustering procedure based on the same lower bounds as Papadimitriou and Yannakakis for a related problem. We deduce an approximation algorithm for an unlimited number of processors with relative performance 2 À 1a1 q, where q denotes the maximum ratio between communication delays and duration of tasks. We also prove that, for a limited number of identical processors m, any list schedule using the clusters structure has a relative performance bounded by 1 1 À 1am2 À 1a1 q and that this bound is tight.

📜 SIMILAR VOLUMES

Tree scheduling with communication delay

Tree scheduling with communication delays

✍ Philippe Chretienne 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 828 KB

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

Approximation algorithms for UET schedul

Approximation algorithms for UET scheduling problems with exact delays

✍ Alexander A. Ageev; Alexei E. Baburin 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 167 KB

Approximation algorithms for general par

Approximation algorithms for general parallel task scheduling

✍ Oh-Heum Kwon; Kyung-Yong Chwa 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 281 KB

A general parallel task scheduling problem is considered. A task can be processed in parallel on one of several alternative subsets of processors. The processing time of the task depends on the subset of processors assigned to the task. We first show the hardness of approximating the problem for bot

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

An approximation algorithm for the prece

An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications

✍ Evripidis Bampis; Rodolphe Giroudeau; Jean-Claude König 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 153 KB

We study the problem of minimizing the makespan for the precedence multiprocessor constrained scheduling problem with hierarchical communications (Parallel Process. Lett. 10(1) (2000) 133). We propose an 8 5 -approximation algorithm for the Unit Communication Time hierarchical problem with arbitrary