𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Bicriteria approximation algorithms for scheduling problems with communications delays

✍ Scribed by Evripidis Bampis; Alexander Kononov

Publisher
Springer US
Year
2005
Tongue
English
Weight
244 KB
Volume
8
Category
Article
ISSN
1094-6136

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Approximation algorithms for scheduling
Approximation algorithms for scheduling trees with general communication delays
✍ Alix Munier πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 101 KB

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

Approximation algorithms for shop schedu
Approximation algorithms for shop scheduling problems with minsum objective
✍ Maurice Queyranne; Maxim Sviridenko πŸ“‚ Article πŸ“… 2002 πŸ› Springer US 🌐 English βš– 166 KB

We consider a general class of multiprocessor shop scheduling problems, preemptive or non-preemptive, with precedence constraints between operations, with job or operation release dates, and with a class of objective functions including weighted sums of job, operations and stage completion times. We

Approximation Algorithms for Scheduling
Approximation Algorithms for Scheduling with
✍ Florian Diedrich; Klaus Jansen; Fanny Pascual; Denis Trystram πŸ“‚ Article πŸ“… 2009 πŸ› Springer 🌐 English βš– 474 KB
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