Abstract FR:

Cette thèse s'inscrit dans le domaine scientifique appelé recherche opérationnelle, elle traite des problèmes d'ordonnancement de projets sous contraintes de ressources ainsi que les méthodes de résolution. Pour ce dernier, elle reprend les principales méthodes approchées et exactes publiées dans la littérature pour résoudre le problème classique du RCPSP (Resource-Constrained Scheduling Problem) ainsi que ses extensions. Dans cette thèse nous avons proposé deux extensions de la méthode d'opimisation à population appelée Optimisation par essaims particulaires ou OEP et une modélisation du problème de RCPSP basée sur les flots. L'OEP, issue de l'étude de l'organisation des groupes d'animaux a été introduite par un psychologue social et par un ingénieur électricien (Kennedy Eberhart, 1995). L'évolution d'une particule se souvient du meilleur point (le plus proche de l'objectif) par lequel il est passé au cours de ses évolutions et tend à y retourner ; chaque particule est informée du meilleur point connu au sein de la population et tend à s'y rendre. La première extension consiste à favoriser davantage le processus d'intensification par rapport au processus de diversification (notions présentées par Blum et Rolli, 2003). Ce qui a conduit à définir la notion d'attracteurs puissants. La deuxième extension porte sur l'adaptation du cadre général proposé par M. Clerc, 2004, aux problèmes d'optimisation combinatoire ayant des contraintes de précédence. Ce qui a amené à redéfinir différents opérateurs et concepts : position d'une particule, différence de deux positions, vitesse d'une particule, somme de deux vitesses, etc. Dans cette thèse, une modélisation du problème de RCPSP basée sur les flots a été proposée. Les concepts de graphe-support, graphe-problème et de graphe-solution ont été définis. Ce qui a conduit à mettre en oeuvre une métaheuristique avec les problèmes de voisinage suivants : le chemin critique, la permutation des activités de la séquence et la pénalisation de certains arcs du graphe. Elle s'est enfin intéressée à un problème industriel, celui des chantiers polyvalents de PSA PEUGEOT CITROEN. Problème industriel complexe dont il a fallu utiliser la méthodologie ASCI (Analyse Spécification Conception et Implantation) pour le décomposer en trois sous-systèmes (physique, logique et décisionnel) disjoints mais communicants. Des methodes approchées (heuristiques, métaheuristiques et simulation) et exactes (programmation linéaire et méthodes de décomposition) ont été utilisées pour résoudre ce problème industriel. Des tests numériques ont été réalisés et les résultats sont comparables et parfois meilleurs à ceux publiés dans la littérature