B&B@Grid : une approche efficace pour la ...
Document type :
Rapport de recherche: Autre communication scientifique (congrès sans actes - poster - séminaire...)
Title :
B&B@Grid : une approche efficace pour la gridification d'un algorithme Branch and Bound
Author(s) :
Mezmaz, Mohand [Auteur correspondant]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Melab, Nouredine [Auteur correspondant]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Talbi, El-Ghazali [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Melab, Nouredine [Auteur correspondant]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Talbi, El-Ghazali [Auteur]

Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Institution :
INRIA
Publication date :
2009
English keyword(s) :
Branch and Bound
Parallel Computing
Grid Computing
Flow-Shop Problem
Performance Evaluation
Parallel Computing
Grid Computing
Flow-Shop Problem
Performance Evaluation
HAL domain(s) :
Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
Computer Science [cs]/Operations Research [math.OC]
Computer Science [cs]/Operations Research [math.OC]
French abstract :
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 ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Français
ANR Project :
Collections :
Source :
Files
- https://hal.inria.fr/inria-00384924/document
- Open access
- Access the document
- https://hal.inria.fr/inria-00384924/document
- Open access
- Access the document
- https://hal.inria.fr/inria-00384924/document
- Open access
- Access the document
- document
- Open access
- Access the document
- RR-6937.pdf
- Open access
- Access the document