Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00289342
Contributor : Rodolphe Giroudeau <>
Submitted on : Friday, June 20, 2008 - 12:52:50 PM
Last modification on : Friday, April 12, 2019 - 10:18:09 AM

Identifiers

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. ⟨10.1016/j.tcs.2008.03.027⟩. ⟨lirmm-00289342⟩

Share

Metrics

Record views

169