Techniques de résolution basées sur la Programmation Linéaire pour
l'Ordonnancement de Projet

Jean Damay
LIMOS - Université Blaise Pascal 

Résumé:

 

    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, de manière à minimiser le makespan. 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 de ces
instances à 30 activités de la PSPLIB.