Skip to Main content Skip to Navigation
Journal articles

Seuil d'approximation pour le modèle UET-UCT en présence d'une infinité de processeurs : Une preuve alternative

Rodolphe Giroudeau 1
1 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We propose a new approach for the proof of classical scheduling problem with communication delay. We study the problem of minimizing the makespan for the multiprocessor scheduling problem in the presence of a communication delay. We consider the problem in which all the tasks, in the precedence graph admit an unit execution time and the multiprocessor system is constituted by an unrestricted number of processors. The communication delays between two adjacency tasks i and j which are executed on two different processors is equal to one unit of time (UET-UCT model). In such a context, we prove that there is no heuristic with performance guarantee smaller than 7/6 (resp. 9/8) for the minimization of the length of the schedule (resp. the sum of the completion time).
Keywords : Non-Approximation
Document type :
Journal articles
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00276718
Contributor : Rodolphe Giroudeau Connect in order to contact the contributor
Submitted on : Wednesday, April 30, 2008 - 7:35:49 PM
Last modification on : Friday, February 8, 2019 - 10:16:22 AM

Links full text

Identifiers

Collections

Citation

Rodolphe Giroudeau. Seuil d'approximation pour le modèle UET-UCT en présence d'une infinité de processeurs : Une preuve alternative. Revue des Sciences et Technologies de l'Information - Série TSI : Technique et Science Informatiques, Lavoisier, 2008, 27 (5), pp.571-588. ⟨10.3166/tsi.27.571-588⟩. ⟨lirmm-00276718⟩

Share

Metrics

Record views

135