Evaluation and Optimization of the Robustness of DAG Schedules in Heterogeneous Environments

Louis-Claude Canon 1 Emmanuel Jeannot 1
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : A schedule is said to be robust if it is able to absorb some degree of uncertainty in tasks duration while maintaining a stable solution. This intuitive notion of robustness has led to a lot of different metrics and almost no heuristics. In this paper, we perform an experimental study of these different metrics and show how they are correlated to each other. Additionally, we proposed different strategies for minimizing the makespan while maximizing the robustness: from an evolutionary metaheuristic (best solutions but longer computation time) to more simple heuristics making approximations (bad quality solutions but fast computation time). We compare these different approaches experimentally and show that we are able to find different approximations of the Pareto front for this bicriteria problem.
Type de document :
Article dans une revue
IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2010, 21 (4), 〈http://www.computer.org/portal/web/csdl/doi/10.1109/TPDS.2009.84〉. 〈10.1109/TPDS.2009.84>〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00430920
Contributeur : Emmanuel Jeannot <>
Soumis le : mardi 10 novembre 2009 - 12:02:36
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

Collections

Citation

Louis-Claude Canon, Emmanuel Jeannot. Evaluation and Optimization of the Robustness of DAG Schedules in Heterogeneous Environments. IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2010, 21 (4), 〈http://www.computer.org/portal/web/csdl/doi/10.1109/TPDS.2009.84〉. 〈10.1109/TPDS.2009.84>〉. 〈inria-00430920〉

Partager

Métriques

Consultations de la notice

232