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

Evripidis Bampis 1 Rodolphe Giroudeau 2 Jean-Claude König 2
1 LaMI - Laboratoire de Méthodes Informatiques
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.
Keywords : Scheduling Approximability Hierarchical communications
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 : jeudi 24 mai 2018 - 15:59:21

Lien texte intégral

openaccess

Identifiants

Collections

APR | APR-LIRMM | LIRMM | MIPS | UNIV-MONTPELLIER

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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

75

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD