Skip to Main content Skip to Navigation
Reports

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
* Corresponding author
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.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00384924
Contributor : Mohand Mezmaz <>
Submitted on : Sunday, May 17, 2009 - 9:42:46 PM
Last modification on : Thursday, May 28, 2020 - 9:22:09 AM
Document(s) archivé(s) le : Thursday, June 10, 2010 - 9:28:08 PM

File

RR-6937.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

303

Files downloads

266