Skip to Main content Skip to Navigation
Journal articles

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.
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

Identifiers

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⟩

Share

Metrics

Record views

146