Bi-Objective Approximation Scheme for Makespan and Reliability Optimization on Uniform Parallel Machines

Emmanuel Jeannot 1 Erik Saule 2, 3 Denis Trystram 3
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : We study the problem of scheduling independent tasks on a set of related processors which have a probability of failure governed by an exponential law. We are interested in the bi-objective analysis, namely simultaneous optimization of the makespan and the reliability. We show that this problem can not be approximated by a single schedule. A similar problem has already been studied leading to a -approximation algorithm (i.e. for any fixed value of the makespan, the obtained solution is optimal on the reliability and no more than twice the given makespan). We provide an algorithm which has a much lower complexity. This solution is finally used to derive a (2 + ε, 1)-approximation of the Pareto set of the problem, for any ε> 0.
Complete list of metadatas

https://hal.inria.fr/inria-00333906
Contributor : Emmanuel Jeannot <>
Submitted on : Friday, October 24, 2008 - 1:51:51 PM
Last modification on : Thursday, May 16, 2019 - 6:46:08 PM

Links full text

Identifiers

Citation

Emmanuel Jeannot, Erik Saule, Denis Trystram. Bi-Objective Approximation Scheme for Makespan and Reliability Optimization on Uniform Parallel Machines. The 14th International Euro-Par Conference on Parallel and Distributed Computing (Euro-Par 2008), Aug 2008, Las Palmas de Gran Canaria, Spain. pp.877-886, ⟨10.1007/978-3-540-85451-7_94⟩. ⟨inria-00333906⟩

Share

Metrics

Record views

346