Scheduling UET-Tasks on a Star Network: Complexity and Approximation - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles 4OR: A Quarterly Journal of Operations Research Year : 2011

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.
No file

Dates and versions

lirmm-00578530 , version 1 (21-03-2011)

Identifiers

Cite

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, 2011, 9 (1), pp.29-48. ⟨10.1007/s10288-010-0127-7⟩. ⟨lirmm-00578530⟩
76 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More