M?hodes d''optimisation Combinatoire Sur Grilles de Calcul

La r?solution exacte de probl?mes d'optimisation combinatoire de grande taille 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 caracteristiques 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 cette th?se, nous avons propos? 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?gulationde charge, de tol?rance aux pannes et de d?tection de la terminaison. Cette approche, environ 100 fois plus performante en termes de co?t de communication que la meilleure approche connue, a permis la r?solution optimale sur la grillenationale Grid5000 d'une instance standard du probl?me du Flow-Shop rest?e non r?solue depuis une quinzaine d'ann?es.

Author: Mezmaz-M

Publisher: Omniscriptum

Publication Date: Feb 28, 2018

Number of Pages: 152 pages

Binding: Paperback or Softback

ISBN-10: 6131542228

ISBN-13: 9786131542220