B&B@Grid : une approche efficace pour la gridification d'un algorithme Branch and Bound

Mohand Mezmaz 1, * Nouredine Melab 1, * El-Ghazali Talbi 1
* Auteur correspondant
1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Résumé : La résolution exacte de problèmes d'optimisation combinatoire de grande taille, tels que les problèmes d'ordonnancement, constitue un vrai défi pour les grilles informatiques. En effet, il est nécessaire de repenser les algorithmes de résolution pour prendre en compte les caractéristiques de tels environnements, notamment leur grande échelle, l'hétérogénéité et la disponibilité dynamique de leurs ressources, et leur nature multi-domaine d'administration. Dans cet article, nous proposons une nouvelle approche de passage sur grilles de calcul des méthodes exactes de type Branch-and-Bound appelée B&B@Grid. Cette approche est basée sur un codage des unités de travail (sous problèmes) sous forme d'intervalles permettant de minimiser le coût des communications induites par les opérations de régulation de charge, de tolérance aux pannes et de détection de la terminaison. Cette approche, beaucoup plus performante en terme de coût de communication et de sauvegarde que les meilleures approches connues dans la littérature, a permis la résolution optimale sur la grille nationale Grid'5000 d'une instance standard du problème du Flow-Shop restée non résolue depuis une quinzaine d'années. Le Flow-Shop est l'un des problèmes d'ordonnancement les plus étudiés.
Type de document :
Rapport
[Rapport de recherche] RR-6937, INRIA. 2009, pp.32
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00384924
Contributeur : Mohand Mezmaz <>
Soumis le : dimanche 17 mai 2009 - 21:42:46
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 10 juin 2010 - 21:28:08

Fichier

RR-6937.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00384924, version 1

Citation

Mohand Mezmaz, Nouredine Melab, El-Ghazali Talbi. B&B@Grid : une approche efficace pour la gridification d'un algorithme Branch and Bound. [Rapport de recherche] RR-6937, INRIA. 2009, pp.32. 〈inria-00384924〉

Partager

Métriques

Consultations de la notice

215

Téléchargements de fichiers

203