An Approximate Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communications

Evripidis Bampis 1 Rodolphe Giroudeau 2 Jean-Claude König 2
2 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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 approximation algorithm for the Unit Communication Time hierarchical problem with arbitrary but integer processing times and an unbounded number of biprocessor machines. We extend this result in the case where each cluster has m processors (where m is a fixed constant) by presenting a (2−2/(2m+1))-approximation algorithm.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2003, 290 (3), pp.1883-1895. 〈10.1016/S0304-3975(02)00328-6〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00269765
Contributeur : Christine Carvalho de Matos <>
Soumis le : jeudi 3 avril 2008 - 08:22:42
Dernière modification le : mardi 17 avril 2018 - 11:48:04

Lien texte intégral

Identifiants

Collections

Citation

Evripidis Bampis, Rodolphe Giroudeau, Jean-Claude König. An Approximate Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communications. Theoretical Computer Science, Elsevier, 2003, 290 (3), pp.1883-1895. 〈10.1016/S0304-3975(02)00328-6〉. 〈lirmm-00269765〉

Partager

Métriques

Consultations de la notice

69