Complexity and Approximation for Precedence Constrained Scheduing Problems with Large Communication Delays

Abstract : We investigate the problem of minimizing the makespan (resp. the sumof completion time) fort hemultiprocessor scheduling problem.We show that there is no hope of finding aρ-approximation with ρ<1 +1/(c+4) for minimization of the makespan (resp. 1+ 1/ (2c +5) for total job completion time minimization) (unless P=NP) for the case where all the task soft he precedence graph have unit execution times, where the multiprocessor is composed of an unrestricted number of machines, and where cde notes the communication de lay between two tasks i and j submitted to aprecedence constraint and to be processed by two different machines. The problembe comes polynomial whe never them ake span is at most (c +1). The(c +2) case is still partially open. Moreover, we both define and study a new scheduling approximation to schedule un itary tasks in the presence of large communication delays.We provide apolynomial-time approximation algorithm with performance ratio 2(c+1) 3 with c≥2.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00289342
Contributeur : Rodolphe Giroudeau <>
Soumis le : vendredi 20 juin 2008 - 12:52:50
Dernière modification le : jeudi 11 janvier 2018 - 06:26:07

Identifiants

Collections

Citation

Rodolphe Giroudeau, Jean-Claude König, Jérôme Palaysi, Farida Moulai. Complexity and Approximation for Precedence Constrained Scheduing Problems with Large Communication Delays. Theoretical Computer Science, Elsevier, 2008, 401, pp.107-119. 〈http://www.sciencedirect.com/science/article/pii/S0304397508002387?via%3Dihub〉. 〈10.1016/j.tcs.2008.03.027〉. 〈lirmm-00289342〉

Partager

Métriques

Consultations de la notice

64