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.
Type de document :
Communication dans un congrès
Emilio Luque and Tomàs Margalef and Domingo Benítez. The 14th International Euro-Par Conference on Parallel and Distributed Computing (Euro-Par 2008), Aug 2008, Las Palmas de Gran Canaria, Spain. Springer Berlin / Heidelberg, 5168, pp.877-886, 2008, Lecture Notes in Computer Science. 〈10.1007/978-3-540-85451-7_94〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00333906
Contributeur : Emmanuel Jeannot <>
Soumis le : vendredi 24 octobre 2008 - 13:51:51
Dernière modification le : jeudi 11 janvier 2018 - 06:22:01

Lien texte intégral

Identifiants

Citation

Emmanuel Jeannot, Erik Saule, Denis Trystram. Bi-Objective Approximation Scheme for Makespan and Reliability Optimization on Uniform Parallel Machines. Emilio Luque and Tomàs Margalef and Domingo Benítez. The 14th International Euro-Par Conference on Parallel and Distributed Computing (Euro-Par 2008), Aug 2008, Las Palmas de Gran Canaria, Spain. Springer Berlin / Heidelberg, 5168, pp.877-886, 2008, Lecture Notes in Computer Science. 〈10.1007/978-3-540-85451-7_94〉. 〈inria-00333906〉

Partager

Métriques

Consultations de la notice

298