| Popis: |
Le probleme de gestion de projet sous contraintes de ressources (Resource Constrained Project Scheduling Problem) consiste en l'ordonnancement de tâches, egalement appelees activites, a l'aide d'une ou plusieurs ressources renouvelables ou non, en quantite limitee. Le but vise par la resolution de ce probleme est la determination des dates d'execution des activites en fonction de la disponibilite des ressources et de facon a satisfaire des objectifs fixes. Les activites sont liees entre elles par des contraintes de preseance qui doivent etre respectees lors de l'ordonnancement. Depuis plus de 30 ans, de nombreuses etudes ont ete consacrees au RCPSP qui est un probleme NP-difficile au sens fort. L'aspect pratique de ce probleme dans des contextes industriels divers a conduit a de nombreuses recherches et ainsi a des resolutions par des methodes heuristiques et metaheuristiques. Les algorithmes genetiques (AG) figurent parmi les metaheuristiques qui perforaient le mieux pour la resolution de ce probleme. L'optimisation par essaims particulaire (OEP), quant a elle, est une methode emergente qui interesse de plus en plus de chercheurs dans le domaine de l'optimisation discrete et qui donne d'assez bons resultats. Ce memoire propose une hybridation de ces.deux methodes dans le but d'ameliorer leurs performances individuelles sur des instances de taille moyenne. L'hybridation se fait au niveau du croisement en combinant deux methodes de croisement, l'une etant le croisement classique a deux points largement repandu au sein de la litterature. La seconde methode de croisement est nouvelle et se base sur un concept de distances entre deux solutions emprunte a un algorithme d'OEP de la litterature traitant du probleme de minimisation du retard total pondere sur une machine unique. Cet algorithme a d'abord ete reproduit et adapte au RCPSP. La comparaison des performances obtenues avec celles des deux autres algorithmes d'OEP connus dans la litterature du RCPSP a ete favorable a cette adaptation. Cela a donne lieu a la conception d'une methode de croisement qui s'inspire des principes de l'OEP et du concept de distances pour generer de nouvelles solutions. Les performances observees lors de l'hybridation des deux methodes de croisement ci-dessus enumerees montrent bien l'apport de cette technique innovatrice que constitue l'OEP discrete pour la resolution du RCPSP. Ce travail de recherche represente surtout une premiere exploration du potentiel offert par la technique de l'OEP et sa combinaison avec deux autres champs de recherche en evolution continue : le RCPSP et les AG. L'association de ces trois domaines de recherche laisse entrevoir des possibilites interessantes pouvant mener a la conception de nouveaux algorithmes plus performants pour la resolution du RCPSP. Ce memoire constitue une contribution non seulement vers une meilleure connaissance de l'OEP mais aussi vers l'amelioration des outils d'optimisation en gestion de projet. |
