Complexity and Approximation for Precedence Constrained Scheduing Problems with Large Communication Delays - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Theoretical Computer Science Year : 2008

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.

Dates and versions

lirmm-00289342 , version 1 (20-06-2008)

Identifiers

Cite

Rodolphe Giroudeau, Jean-Claude König, Jérôme Palaysi, Feryal Windal. Complexity and Approximation for Precedence Constrained Scheduing Problems with Large Communication Delays. Theoretical Computer Science, 2008, 401, pp.107-119. ⟨10.1016/j.tcs.2008.03.027⟩. ⟨lirmm-00289342⟩
104 View
0 Download

Altmetric

Share

More