Groupe d’études et de recherche en analyse des décisions

Techniques de résolution basées sur la Programmation Linéaire pour l'ordonnancement de projet

Jean Damay

Le RCPSP (Resource-Constrained Project Scheduling Problem), connu pour être NP-difficile au sens fort, consiste à planifier dans le temps l'exécution des activités d'un projet, soumises à des contraintes de précédence et de ressources, dans le but de minimiser le temps total d'exécution. Ce problème suscite un intérêt important dans la communauté des chercheurs opérationnels parce qu'il sert de modèle pour de nombreux problèmes réels de gestion de projet et de planification.

Nous présentons une reformulation originale de ce problème, basée sur une relaxation linéaire continue, où chaque variable est associée à un ensemble d'activités pouvant être exécutées simultanément au cours de l'ordonnancement. La résolution de cette relaxation par l'algorithme du Simplexe fait appel à des techniques de Génération de Colonnes dont le problème de /pricing/ correspond au problème de sac-à-dos / stable maximum. Nous adjoignons à chaque itération de la descente proposée par le Simplexe un test incrémental de respect, par la famille des variables en base, des propriétés identifiées à partir de notre reformulation pour que cette famille représente un ordonnancement réalisable. Un résultat théorique de connexité de l'espace de ces solutions réalisables, pour notre opérateur de voisinage, est fourni.

La qualité médiocre des premiers résultats de cette descente avec pivotage sélectif est dûe au nombre important de minima locaux. Elle incite à proposer des techniques de diversification dans l'espace de recherche. Deux algorithmes ont été développés dans ce sens, améliorant sensiblement les valeurs des solutions réalisables obtenues, l'optimum étant atteint relativement fréquemment sur les instances classiques de la librairie /PSPLIB/ à 30 activités.

De plus, la version préemptive du RCPSP autorise l'interruption de l'exécution d'activités pour être reprise ultérieurement, sans pénalité. Les méthodes décrites ci-dessus traitent avec qualité ce cas particulier. Une méthode par Séparation/Evaluation, basée sur cette même relaxation linéaire, a été développée pour celui-ci. Le branchement correspond à des contraintes de non-circuit que l'on ajoute aux différents noeuds de l'arbre par le biais de mises à zéro de certaines variables. Trois variantes de branchement ont été conçues, et l'une d'elles fournit toutes les solutions optimales préemptives des instances mentionnées ci-dessus.