MO-Greedy: an extended beam-search approach for solving a multi-criteria scheduling problem on heterogeneous machines

Louis-Claude Canon 1 Emmanuel Jeannot 2
1 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
2 RUNTIME - Efficient runtime systems for parallel architectures
Inria Bordeaux - Sud-Ouest, UB - Université de Bordeaux, CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : Optimization problems can often be tackled with respect to several objectives. In such cases, there can be several incomparable Pareto-optimal solutions. Computing or approximating such solutions is a major challenge in algorithm design. Here, we show how to use an extended beam-search technique to solve a multi-criteria scheduling problem for heterogeneous machines. This method, called MO-Greedy (for Multi-Objective greedy), allows the design of a multi-objective algorithm when a single-objective greedy one is known. We show that we can generate, in a single execution, a Pareto front optimized with respect to the preferences specified by the decision maker. We compare our approach to other heuristics and an approximation algorithm and show that the obtained front is, on average, better with our method.
Type de document :
Communication dans un congrès
International Heterogeneity in Computing Workshop, May 2011, Anchorage, United States. 2011
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00653724
Contributeur : Louis-Claude Canon <>
Soumis le : mardi 20 décembre 2011 - 09:45:11
Dernière modification le : jeudi 11 octobre 2018 - 08:48:03
Document(s) archivé(s) le : vendredi 16 novembre 2012 - 16:06:02

Fichier

hcw11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00653724, version 1

Citation

Louis-Claude Canon, Emmanuel Jeannot. MO-Greedy: an extended beam-search approach for solving a multi-criteria scheduling problem on heterogeneous machines. International Heterogeneity in Computing Workshop, May 2011, Anchorage, United States. 2011. 〈hal-00653724〉

Partager

Métriques

Consultations de la notice

438

Téléchargements de fichiers

231