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.

We consider the unit execution time unit communication time ($\phantom{\rule{-0.166667em}{0ex}}$UET-UCT$\phantom{\rule{-0.166667em}{0ex}}$) 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 $𝒫=\mathrm{𝒩𝒫}$). This result is an extension of the result of Hoogeveen et al. [6] who proved that there is no polynomial time $\rho$-approximation algorithm with $\rho <7/6$ for the classical UET-UCT scheduling problem with homogeneous communication delays and an unrestricted number of identical machines.

DOI : https://doi.org/10.1051/ro:2002003
Classification : 90B35
Mots clés : scheduling, hierarchical communications, non-approximability
@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},
zbl = {1005.90031},
mrnumber = {1920377},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro:2002003/}
}
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://www.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 1665416

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

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

[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 558574 | Zbl 0411.90044

[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 1306216 | Zbl 0816.90083