An Approximate Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communications - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Theoretical Computer Science Year : 2003

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

Evripidis Bampis
  • Function : Author
  • PersonId : 855947
Rodolphe Giroudeau
Jean-Claude König

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.

Dates and versions

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

Identifiers

Cite

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⟩
80 View
0 Download

Altmetric

Share

More