An Approximate Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communications - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2003

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

Evripidis Bampis
  • Fonction : Auteur
  • PersonId : 855947
Rodolphe Giroudeau
Jean-Claude König

Résumé

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.

Dates et versions

lirmm-00269765 , version 1 (03-04-2008)

Identifiants

Citer

Evripidis Bampis, Rodolphe Giroudeau, Jean-Claude König. An Approximate Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communications. Theoretical Computer Science, 2003, 290 (3), pp.1883-1895. ⟨10.1016/S0304-3975(02)00328-6⟩. ⟨lirmm-00269765⟩
63 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More