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
Document type :
Journal articles
Complete list of metadatas
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00269765
Contributor : Christine Carvalho de Matos <>
Submitted on : Thursday, April 3, 2008 - 8:22:42 AM
Last modification on : Friday, April 12, 2019 - 10:18:09 AM

Links full text

openaccess

Identifiers

Collections

CNRS | APR | UNIV-EVRY | 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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

129

Contact

Informations

CCSD