Résumé: La résolution exacte de problèmes d’optimisation combinatoire avec les algorithmes Branch and Bound (B&B) nécessite un nombre exorbitant de ressources de calcul. Actuellement, cette puissance est offerte par les environnements large échelle comme les grilles de calcul. Cependant, les grilles présentent de nouveaux challenges : le passage à l’échelle, l’hétérogénéité et la tolérance aux pannes. La majorité des algorithmes B&B revisités pour les grilles de calcul sont basés sur le paradigme Master-Worker, ce qui limite leur passage à l’échelle. De plus, la tolérance aux pannes est rarement adressée dans ces travaux. Dans cette thèse, nous proposons trois principales contributions : P2P-B&B, H-B&B et FTH-B&B. P2PB& B est un famework basé sur le paradigme Master-Worker traite le passage à l’échelle par la réduction de la fréquence de requêtes de tâches et en permettant les communications directes entre les workers. H-B&B traite aussi le passage à l’échelle. Contrairement aux approches proposées dans la littérature, H-B&B est complètement dynamique et adaptatif i.e. prenant en compte l’acquisition dynamique des ressources de calcul. FTH-B&B est basé sur de nouveaux mécanismes de tolérance aux pannes permettant de construire et maintenir la hiérarchie équilibrée, et de minimiser la redondance de travail quand les tâches sont sauvegardées et restaurées. Les approches proposées ont été implémentées avec la plateforme pour grille ProActive et ont été appliquées au problème d’ordonnancement de type Flow-Shop. Les expérimentations large échelle effectuées sur la grille Grid’5000 ont prouvé l’efficacité des approches proposées

Langue: Français
Collation: 116 p. ill. ;30 cm.
Diplôme: Docteur Es Sciences
Etablissement de soutenance: Béjaia, Université Abderrahmane Mira. Faculté des Sciences Exactes
Spécialité: Informatique
Index décimal 005.741 .Méthodes d'accès et organisation des fichiers de données (adressage calculé, algorithmes de recherche ou de tri, arborescences de recherche, formats de fichiers de données, fusion, modes d'accès, regroupement, tri)
Thème Informatique

Mots clés:
Branch, Algorithme
Optimisation combinatoire
Grilles informatiques

Note: Bibliogr. pp.110-116