RAIRO - Operations Research

Table of Contents - January 2002 - Volume 36, Issue 01  

Research Article

On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications

Bampis, Evripidisa1, Giroudeau, R.a1 and König, J.-C.a2

a1 Laboratoire de Méthodes Informatiques (LaMI), Université d'Evry-Val-d'Essonne, UMR 8042 du CNRS, 523 place des Terrasses, Immeuble ÉVRY-II, 91000 Evry, France; bampis@lami.univ-evry.fr. giroudeau@lami.univ-evry.fr.

a2 LIRMM, Université de Montpellier II, UMR 5506 du CNRS, 161 rue Ada, 34392 Montpellier Cedex 5, France; konig@lirmm.fr.

Abstract

We consider the unit execution time unit communication time (UET-UCT) scheduling model with hierarchical communica tions [CITE], and we study the impact of the hierarchical communications hypothesis on the hardness of approximation. We prove that there is no polynomial time approximation algorithm with performance guarantee smaller than 5/4 (unless P = NP). This result is an extension of the result of Hoogeveen et al. [CITE] who proved that there is no polynomial time ρ-approximation algorithm with p < 7/6 for the classical UET-UCT scheduling problem with homogeneous communication delays and an unrestricted number of identical machines.

(Received September 1999)

(Online publication July 15 2002)

Key Words:

  • Scheduling;
  • hierarchical communications;
  • non-approxima bility.

Mathematics Subject Classification:

  • 90B35