Skip to Main content Skip to Navigation
Journal articles

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

Rodolphe Giroudeau 1 Jean-Claude König 1 Benoît Valery 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Journal articles
Complete list of metadatas
Contributor : Rodolphe Giroudeau <>
Submitted on : Monday, March 21, 2011 - 1:13:22 PM
Last modification on : Monday, February 11, 2019 - 11:50:15 AM




Rodolphe Giroudeau, Jean-Claude König, Benoît Valery. 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⟩



Record views