Abstract:
Un problème d'optimisation combinatoire consiste à trouver dans un ensemble fini une ou un sous ensemble de meilleures solutions réalisables.
Les problèmes d’optimisation deviennent de plus en plus difficiles et leur difficulté réside précisément dans le fait que le nombre de solutions réalisables rend leur énumération impossible par une recherche exhaustive, ou bien de dire s'il en existe une solution ou pas quand ces problèmes sont NP-complet.
L’utilisation des méta heuristiques permet de réduire la difficulté des problèmes pour lesquels on ne connaît pas de méthode de résolution classique, en donnant en un temps raisonnable une solution acceptable ou se rapprochant de l’optimum.
Ajouter a ces méthodes, Ces dernières années le calcul parallèle spécifiquement celui sur GPU a fait ses preuves en permettant de décupler les performances de calcul en exploitant la puissance des processeurs graphiques (GPU).
Dans ce mémoire nous combinons ces deux avantages en utilisant les méta heuristiques sous une architecture de traitement parallèle développée par NVIDIA (CUDA) en concevant et réalisant un algorithme génétique parallèle basé sur le modèle maitre esclave pour résoudre le problème du flow-shop, intégrant la particularité de généricité pour offrir la possibilité d’inclure et de résoudre d’autres problèmes combinatoires.
Cependant, Il reste un grand travail à faire pour surmonter les contraintes qui font face à l’exploitation efficace des GPU, a savoir les contraintes liées à la gestion de la mémoire (latence et taille), ou celles associées à la synchronisation des threads et la gestion de leur divergence.
