HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Approximation algorithms for energy, reliability and makespan optimization problems

Guillaume Aupy 1, 2, * Anne Benoit 1, 2, *
* Corresponding author
2 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In this paper, we consider the problem of scheduling an application on a parallel computational platform. The application is a particular task graph, either a linear chain of tasks, or a set of independent tasks. The platform is made of identical processors, whose speed can be dynamically modified. It is also subject to failures: if a processor is slowed down to decrease the energy consumption, it has a higher chance to fail. Therefore, the scheduling problem requires to re-execute or replicate tasks (i.e., execute twice a same task, either on the same processor, or on two distinct processors), in order to increase the reliability. It is a tri-criteria problem: the goal is to minimize the energy consumption, while enforcing a bound on the total execution time (the makespan), and a constraint on the reliability of each task. Our main contribution is to propose approximation algorithms for these particular classes of task graphs. For linear chains, we design a fully polynomial time approximation scheme. However, we show that there exists no constant factor approximation algorithm for independent tasks, unless P=NP, and we are able in this case to propose an approximation algorithm with a relaxation on the makespan constraint.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

Contributor : Guillaume Pallez (aupy) Connect in order to contact the contributor
Submitted on : Monday, July 7, 2014 - 11:58:01 AM
Last modification on : Monday, May 16, 2022 - 4:46:02 PM
Long-term archiving on: : Tuesday, April 11, 2017 - 10:02:03 AM


Files produced by the author(s)


  • HAL Id : hal-00742754, version 2



Guillaume Aupy, Anne Benoit. Approximation algorithms for energy, reliability and makespan optimization problems. [Research Report] RR-8107, INRIA. 2014, pp.32. ⟨hal-00742754v2⟩



Record views


Files downloads