Méthodes hybrides de programmation par contraintes et programmation linéaire pour le problème d'ordonnancement de projet à contrainte de ressources
Institution:
AvignonDisciplines:
Directors:
Abstract EN:
The standard resource-constrained project scheduling problem (RCPSP) aims at scheduling the activities of a project sharing renewelable resources, available in limited amounts. The intractability of the RCPSP has motivated test of numerous optimization techniques and led to an extensive literature. We are interested in the exact resolution of this problem by means of methods combining constraint programming (CP) and linear programming (LP) techniques. Such hybrid methods are more and more successfully applied to solve the hardest combinatorial problems. This dissertation opens with a review of the main CP/LP hybrid exact methods in the optimization literature, and a state-of-the-art for the RCPSP. In a first part, we present new lower bounds for the RCPSP computed by lagrangean relaxation and cutting-plane generation techniques. Well-known constraint propagation techniques as well as a new shaving scheme are applied as preprocessing to speed up the resolution of the different linear programs. Furthermore, we present original cutting planes for the RCPSP that are directly derived from the deductions of the constraint propagation phase. Our experiments show that these lower bounds are among the best lower bounds known to date for the RCPSP. In the second part, we propose an original exact method for the RCPSP, based on the resolution search algorithm of Chvatal. We present a study of this algorithm which is an alternative to the branch-and-bound methods. We also show how resolution search can be assimilated to intelligent backtracking in constraint programming. We prove its efficiency by an experimental comparison with a similar branch-and-bound for the RCPSP. Last, we introduce some new features to improve the general algorithm or to adapt it more specifically to the RCPSP
Abstract FR:
La version classique du problème d'ordonnancement de projet à contraintes de ressources (RCPSP) consiste à trouver un ordonnancement, de durée minimale, des activités d'un projet entrant en compétition sur l'usage de ressources renouvelables, cumulatives et disponibles en quantité limité. La réputation d'extrême difficulté du RCPSP a mené nombre de chercheurs à proposer de nouvelles méthodes de résolution toujours plus complexes pour ce problème. Nous nous intéressons à la résolution exacte du RCPSP par combinaison de techniques issues de la programmation par contraintes et de la programmation linéaire. De telles méthodes hybrides sont en effet de plus en plus prisées pour appréhender les problèmes combinatoires les plus difficiles. Après une étude des principales techniques d'hybridation de la littérature, nous nous attachons, dans un premier temps, au calcul de bornes inférieures pour le RCPSP par relaxation lagrangienne ainsi que par génération de coupes. Des techniques éprouvées de propagation de contraintes, dont la règle globale du shaving sont utilisées en prétraitement des programmes linéaires pour en accélerer la résolution et améliorer les bornes. De plus, les coupes linéaires proposées sont directement déduites des règles de propagation de contraintes. Nous proposons, dans un second temps, une méthode originale de résolution exacte pour le RCPSP, basée sur la procédure de resolution search de Chvatal. Nous montrons comment cette alternative aux méthodes arborescentes classiques pour les programmes linéaires en variables binaires s'identifie aux techniques de backtracking intelligent en programmation par contraintes. Nous prouvons son efficacité comparativement à une PSE équivalente en l'appliquant de manière basique à une formulation linéaire en variables binaires du RCPSP. Nous présentons enfin quelques améliorations possibles et étudions comment resolution search peut être adaptée à des règles de branchement plus spécifiques au RCPSP