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; email@example.com. firstname.lastname@example.org.
a2 LIRMM, Université de Montpellier II, UMR 5506 du CNRS, 161 rue Ada, 34392 Montpellier Cedex 5, France; email@example.com.
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)
Mathematics Subject Classification: