  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.
