On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications
Bampis, Evripidis ; Giroudeau, R. ; König, J.-C.1
1 LIRMM, Université de Montpellier II, UMR 5506 du CNRS, 161 rue Ada, 34392 Montpellier Cedex 5, France
RAIRO - Operations Research - Recherche Opérationnelle, Tome 36 (2002) no. 1, pp. 21-36.

We consider the unit execution time unit communication time (UET-UCT) scheduling model with hierarchical communications [1], 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 𝒫=𝒩𝒫). This result is an extension of the result of Hoogeveen et al. [6] who proved that there is no polynomial time ρ-approximation algorithm with ρ<7/6 for the classical UET-UCT scheduling problem with homogeneous communication delays and an unrestricted number of identical machines.

DOI : 10.1051/ro:2002003
Classification : 90B35
Mots-clés : scheduling, hierarchical communications, non-approximability
Bampis, Evripidis  ; Giroudeau, R.  ; König, J.-C. 1

1 LIRMM, Université de Montpellier II, UMR 5506 du CNRS, 161 rue Ada, 34392 Montpellier Cedex 5, France 
@article{RO_2002__36_1_21_0,
     author = {Bampis, Evripidis and Giroudeau, R. and K\"onig, J.-C.},
     title = {On the hardness of approximating the {UET-UCT} scheduling problem with hierarchical communications},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {21--36},
     publisher = {EDP-Sciences},
     volume = {36},
     number = {1},
     year = {2002},
     doi = {10.1051/ro:2002003},
     mrnumber = {1920377},
     zbl = {1005.90031},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro:2002003/}
}
TY  - JOUR
AU  - Bampis, Evripidis
AU  - Giroudeau, R.
AU  - König, J.-C.
TI  - On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2002
SP  - 21
EP  - 36
VL  - 36
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro:2002003/
DO  - 10.1051/ro:2002003
LA  - en
ID  - RO_2002__36_1_21_0
ER  - 
%0 Journal Article
%A Bampis, Evripidis
%A Giroudeau, R.
%A König, J.-C.
%T On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2002
%P 21-36
%V 36
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro:2002003/
%R 10.1051/ro:2002003
%G en
%F RO_2002__36_1_21_0
Bampis, Evripidis; Giroudeau, R.; König, J.-C. On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications. RAIRO - Operations Research - Recherche Opérationnelle, Tome 36 (2002) no. 1, pp. 21-36. doi : 10.1051/ro:2002003. http://archive.numdam.org/articles/10.1051/ro:2002003/

[1] E. Bampis, R. Giroudeau and J.C. König, Using duplication for multiprocessor scheduling problem with hierarchical communications. Parallel Process. Lett. 10 (2000) 133-140.

[2] B. Chen, C.N. Potts and G.J. Woeginger, A review of machine scheduling: Complexity, algorithms and approximability, Technical Report Woe-29. TU Graz (1998). | MR

[3] Ph. Chrétienne, E.J. Coffman Jr., J.K. Lenstra and Z. Liu, Scheduling Theory and its Applications. Wiley (1995). | MR | Zbl

[4] M.R. Garey and D.S. Johnson, Computers and Intractability, a Guide to the Theory of 𝒩𝒫-Completeness. Freeman (1979). | MR | Zbl

[5] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministics sequencing and scheduling theory: A survey. Ann. Discrete Math. 5 (1979) 287-326. | MR | Zbl

[6] J.A. Hoogeveen, J.K. Lenstra and B. Veltman. Three, four, Five, six, or the complexity of scheduling with communication delays. Oper. Res. Lett. 16 (1994) 129-137. | MR | Zbl

Cité par Sources :