Abstract FR:

Les métaheuristiques sont une source d'inspiration inépuisable pour la résolution efficace de problèmes combinatoires. Nos travaux sur la coloration de graphes et un problème de planification le confirment. Nous avons ainsi développé les premières adaptations de la recherche dispersée pour la coloration et de la recherche tabou pour le problème de planification. Nos résultats rejoignent les meilleurs publiés. Nous avons aussi analysé des solutions du problème de coloration. Nos analyses ont révélé que certains ensembles de sommets sont représentatifs des solutions. Cette information nous a permis, non seulement de caractériser la diversité des solutions, mais aussi d'améliorer un algorithme tabou. Concernant la planification, différentes propriétés de la configuration initiale utilisée par notre algorithme tabou ont été exploitées pour développer, dans un premier temps, une approche de réparation exhaustive. Nos résultats dépassent largement ceux des meilleures approches connues malgré une complexité exponentielle. Pour tenter de diminuer cette complexité, nous avons, là encore, observé les solutions, et les choix effectués pour y parvenir. Cela a été profitable puisque nous avons conçu le premier algorithme à complexité linéaire pour résoudre le problème.