Scheduling UET-Tasks on a Star Network: Complexity and Approximation

Abstract : In this article we investigate complexity and approximation on a processor network where the communication delay depends on the distance between the processors performing tasks. We then prove that there is no polynomial-time heuristic with a performance guarantee smaller than 65 (respectively 1413) for minimization of the makespan (respectively the total job completion time) on a processor network represented by a star. Moreover, we design an efficient polynomial-time approximation algorithm with a worst-case ratio of four. We also prove that a polynomial-time algorithm exists for a schedule with a length of at most four. Lastly, we generalize all previous results on complexity and approximation.
Type de document :
Article dans une revue
4OR: A Quarterly Journal of Operations Research, Springer Verlag, 2011, 9 (1), pp.29-48. 〈10.1007/s10288-010-0127-7〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00578530
Contributeur : Rodolphe Giroudeau <>
Soumis le : lundi 21 mars 2011 - 13:13:22
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

Collections

Citation

Rodolphe Giroudeau, Jean-Claude König, Valéry Benoit. Scheduling UET-Tasks on a Star Network: Complexity and Approximation. 4OR: A Quarterly Journal of Operations Research, Springer Verlag, 2011, 9 (1), pp.29-48. 〈10.1007/s10288-010-0127-7〉. 〈lirmm-00578530〉

Partager

Métriques

Consultations de la notice

99