méthodes de résolution exactes basées sur la programmation linéaire en nombres entiers

Télécharger le fichier original (Mémoire de fin d’études)

Introduction

De nos jours, toute entreprise doit gérer eﬃcacement ses ressources (matérielles, humaines) afin de maintenir son niveau de compétitivité au plus haut. En eﬀet, les impacts d’une gestion des ressources de qualité peuvent être extrêmement béné-fiques non seulement en termes de temps de réalisation des activités, mais aussi en termes de coût, permettant ainsi à l’entreprise de gagner en productivité. En dépit de ce constat, les fonctionnalités de planification proposées par les logiciels d’aide à la décision actuels quant à la gestion des ressources restent limitées à l’implémen-tation de méthodes simples, qui ne permettent pas d’englober tous les aspects de la gestion de projet. En particulier, ces outils ne permettent pas de prendre en compte diﬀérents niveaux de granularité temporelle pour la prise de décision concernant les divers éléments du projet. Si, par exemple, en termes de logistique, les dates de lancement des activités doivent être décidées avec une granularité assez fine sur l’horizon du projet, il n’est peut-être ni souhaitable ni nécessaire de planifier l’uti-lisation des ressources avec la même granularité. Par exemple, il est inutile, voire impossible, de concevoir un planning à long ou moyen terme dans lequel l’emploi du temps du personnel est détaillé pour chaque individu ; à ce stade, on préfèrera raisonner en termes de quantité de main d’œuvre disponible, selon les phases du pro-jet. Notre objectif dans cette thèse est de proposer des modèles et des algorithmes d’ordonnancement et de planification susceptibles d’apporter une telle flexibilité en termes de granularité temporelle.
Dans la littérature consacrée à la gestion de projet, le problème le plus connu et le plus étudié est certainement le problème d’ordonnancement de ressources sous contraintes de ressources (Resource-Constrained Project Scheduling Problem, RCPSP), défini comme suit. Étant donnés un ensemble d’activités et de ressources, caractérisés par les durées des activités, leurs consommations en ressources, les ca-pacités des ressources (nombres d’unités disponibles à chaque instant), ainsi que des relations d’antériorité entre les activités, l’objectif est de trouver un ordonnan-cement (c’est-à-dire choisir une date de début pour chaque activité) qui minimise la date de fin du projet (en supposant que celui commence à la date = 0), en respec-tant deux types de contraintes. D’une part, les contraintes d’antériorité imposent qu’une activité ne peut pas être démarrée avant que ses prédécesseurs soient termi-nés. D’autre part, les contraintes de ressources imposent qu’à chaque instant, pour toute ressource, la somme des consommations des activités en cours d’exécution ne peut pas dépasser la capacité de la ressource.
Le RCPSP est l’un des problèmes combinatoires les plus diﬃciles à résoudre. Il existe encore à l’heure actuelle des instances de projets de petite taille (60 activités, 4 ressources) pour lesquelles l’optimalité n’a pu être prouvée pour aucune solution. Si la version standard RCPSP reste un sujet de recherche actif encore au-jourd’hui, de nombreuses variantes ont été proposées et également très étudiées dans la littérature. Par exemple, l’introduction de contraintes d’antériorité géné-ralisées entre activités permettent de borner inférieurement et supérieurement le délai entre la fin d’une activité et le début d’un de ses successeurs. Dans le RCPSP multi-modes, il faut déterminer pour chaque activité non seulement sa date de dé-but, mais aussi choisir un mode d’exécution (durée et consommations) parmi un ensemble de choix (fini et discret).
Le RCPSP est donc un modèle pertinent lorsqu’il est utilisé à un niveau de décision opérationnel (ordonnancement, à court terme). En revanche, ce modèle n’est pas assez flexible pour un niveau de décision tactique (planification, à moyen terme). En eﬀet, à un niveau intermédiaire, l’estimation des paramètres du problème est soumise à des incertitudes. De plus, il est courant de procéder à une agrégation de l’information, par exemple en raisonnant non pas sur des tâches élémentaires mais des macro-tâches, ou encore en évaluant la consommation des tâches non pas précisément à chaque instant, mais en moyenne sur des périodes ; ainsi, les décisions prises au niveau tactique doivent permettre une certaine flexibilité, afin d’équilibrer la charge de travail dans chaque période et faciliter le calcul d’un ordonnancement réalisable au niveau opérationnel.
Dans cette thèse est proposé un modèle de gestion de projet situé entre les niveaux tactique et opérationnel, qui permet à la fois de définir précisément les dates de début et de fin des activités, notamment pour respecter les relations d’antériorité, tout en évaluant la consommation des tâches en ressources de manière agrégée sur un horizon discrétisé en périodes de même durée. La durée de ces périodes, paramétrable, devient ainsi un levier qui permet au décideur, pour un projet donné, de sélectionner le niveau d’agrégation le plus adapté au niveau de précision souhaité en termes de consommation des ressources.
La redéfinition des contraintes de ressources, évaluées non plus à chaque instant mais en moyenne dans chaque période, entraîne cependant une modification sub-stantielle de la structure du problème, qui demande donc une étude théorique et pratique spécifique.
Ce manuscrit est structuré selon le plan suivant.
Tout d’abord, un état de l’art sur la programmation linéaire en nombres entiers pour l’ordonnancement de projet est proposé dans le chapitre 1, portant notam-ment sur des formulations indexées par le temps, ainsi que sur la notion d’ensemble admissible.
Les chapitres suivants traitent du problème principal étudié dans cette thèse, intitulé problème d’ordonnancement de projet sous contraintes de ressources avec agrégation périodique (PARCPSP).
Celui-ci est défini formellement dans le chapitre 2 et illustré sur quelques exemples. Ce chapitre comprend également une étude dans le cadre de la théorie de la complexité montrant que le PARCPSP est en général -diﬃcile.
Une analyse des propriétés structurelles est menée dans le chapitre 3. À partir de concepts relatifs à l’altération de la faisabilité d’une solution par translation, le PARCPSP est comparé au RCPSP d’un point de vue théorique. L’impact de la durée des périodes sur la consommation moyenne des activités en ressources est également étudié.
Le chapitre 4 est dédié à des formulations exactes de programmation linéaire en nombres entiers pour le PARCPSP. Certaines propriétés du PARCPSP sont exploitées afin de renforcer ces modèles. Deux de ces modèles sont comparés d’un point de vue théorique en termes de qualité de leur relaxation linéaire.
Enfin, le chapitre 5 aborde des approches heuristiques pour le PARCPSP. Des algorithmes de liste sont adaptés à ce problème, et un algorithme itératif exploi-tant diﬀérentes échelles de temps est également proposé. Une analyse des résultats expérimentaux permet de comparer ces diﬀérentes méthodes de résolution.

Table des matières

Introduction
1 Programmation linéaire en nombres entiers pour l’ordonnancement
de projet
1.1 RCPSP – Resource-Constrained Project Scheduling Problem
1.1.1 Définition du problème
1.1.2 Conditions nécessaires et suffisantes d’existence de solutions
1.1.3 Règles de dominance et réductions de domaines
1.2 Formulations indexées par les périodes
1.2.1 Trois types de variables binaires
1.2.2 Modèle basé sur des variables pulse
1.2.3 Modèle basé sur des variables step
1.2.4 Modèle basé sur des variables on/off
1.3 Formulations étendues basées sur la notion d’ensemble d’activités
admissible
1.3.1 Ensemble d’activités admissible
1.3.2 Problème maître
1.3.3 Sous-problème
1.4 Extensions du RCPSP dans la littérature
2 PARCPSP : définition, complexité
2.1 Définition du PARCPSP : Periodically Aggregated Resource-
Constrained Project Scheduling Problem
2.1.1 Données
2.1.2 Représentation d’une solution en termes de dates et de
consommation de ressources
2.1.3 Formulation abstraite
2.1.4 Dominance des solutions commençant dans la première période
2.1.5 Existence de solutions réalisables
2.2 Exemples
2.3 Complexité
2.3.1 Appartenance à la classe 𝐍𝐏
2.3.2 Réduction depuis le problème Partition
2.3.3 Réduction depuis le problème 3-Partition
2.3.4 Réduction depuis le problème de coloration des sommets d’un
graphe
3 PARCPSP : propriétés structurelles
3.1 Extensions de la notion de faisabilité
3.1.1 Définitions
3.1.2 Propriétés
3.2 Propriétés structurelles du PARCPSP en tant que relaxation du
RCPSP
3.3 Propriétés structurelles du PARCPSP pour des instances définies à
partir d’un même projet
3.4 Algorithme polynomial pour déterminer si une solution est réalisable,
réalisable localement et réalisable globalement
3.4.1 Recherche de l’ensemble des décalages temporels pour lesquels
un ordonnancement donné est réalisable
3.4.2 Agrégation des résultats sur une période
3.4.3 Exemple
4 PARCPSP : méthodes de résolution exactes basées sur la programmation
linéaire en nombres entiers
4.1 Exploitation de la structure du problème pour caractériser la fenêtre
d’exécution d’une activité
4.1.1 Analyse de la fonction d’évaluation de la durée d’exécution
d’une activité dans une période
4.1.2 Nombre de périodes intersectées par une fenêtre d’exécution
4.2 Modèles indexés par période
4.2.1 Première formulation
4.2.2 Seconde formulation
4.2.3 Comparaison des deux formulations
4.3 Modèle compact
5 PARCPSP : méthodes approchées et résultats expérimentaux
5.1 Algorithmes de listes
5.1.1 Algorithmes basés sur des listes de priorité pour le RCPSP
5.1.2 Adaptation au cas du PARCPSP
5.2 Schéma de résolution itératif
5.3 Évaluation expérimentale des heuristiques
5.3.1 Description des schémas de résolution
5.3.2 Analyse des résultats
5.4 Comparaison expérimentale des formulations PLNE
5.4.1 Comparaison des relaxations linéaires
5.4.2 Comparaison des formulations (en nombres entiers)
Conclusion
Bibliographie