Recherche opérationnelle
L’ordonnancement de projet
- Présentation du cours
- Qu'est-ce que la recherche opérationnelle
- Modéliser un problème de décision
- Le programme linéaire et ses formes
- La résolution graphique
- Le simplexe, la méthode
- Le simplexe, les cas particuliers
- La dualité
- L'analyse de sensibilité
- Le problème de transport
- Le problème d'affectation
- Les graphes, vocabulaire et représentation
- Le plus court chemin
- Le flot maximal
- L'ordonnancement de projet
- La programmation en nombres entiers
- Gestion des stocks et files d'attente
Recherche opérationnelle
Chapitre 13 : L’ordonnancement de projet
Le problème
Ce qu’on cherche
Un projet
Un ensemble de tâches, chacune de durée connue, liées par des relations d’antériorité : certaines ne peuvent commencer avant que d’autres soient finies.
Trois questions
- Quelle est la durée minimale du projet ?
- Quelles tâches ne souffrent aucun retard ?
- De combien les autres peuvent-elles glisser ?
L’origine des méthodes
PERT naît en 1958 au Bureau des projets spéciaux de la marine américaine, pour le missile Polaris.
CPM naît la même année chez DuPont, pour l’arrêt et le redémarrage des usines chimiques. Deux équipes, deux besoins, presque le même algorithme.
L’exemple du cours
Sept tâches
| Tâche | Durée (jours) | Antériorités |
|---|---|---|
| A | 3 | — |
| B | 5 | — |
| C | 2 | A |
| D | 4 | A, B |
| E | 6 | C |
| F | 3 | D |
| G | 2 | E, F |
Le graphe du projet
Les dates au plus tôt
Le calcul avant
La règle
t_{\text{tot}}(j) = \max_{i \, \to \, j} \big( t_{\text{tot}}(i) + d(i) \big)
Une tâche commence quand la dernière de ses antériorités est terminée.
Le parcours
| Tâche | Début au plus tôt | Fin au plus tôt |
|---|---|---|
| A | 0 | 3 |
| B | 0 | 5 |
| C | 3 | 5 |
| D | \max(3,5) = 5 | 9 |
| E | 5 | 11 |
| F | 9 | 12 |
| G | \max(11,12) = 12 | \mathbf{14} |
La durée du projet
Quatorze jours. C’est la longueur du plus long chemin dans le graphe — jamais la somme des durées, qui vaut 25.
Les tâches parallèles se recouvrent : c’est tout l’intérêt de les ordonnancer.
Les dates au plus tard
Le calcul arrière
La règle
t_{\text{tard}}(i) = \min_{i \, \to \, j} \big( t_{\text{tard}}(j) \big) - d(i)
On part de la fin, fixée à 14, et l’on remonte.
Le parcours et les marges
| Tâche | Début au plus tôt | Début au plus tard | Marge |
|---|---|---|---|
| A | 0 | 1 | 1 |
| B | 0 | 0 | \mathbf{0} |
| C | 3 | 4 | 1 |
| D | 5 | 5 | \mathbf{0} |
| E | 5 | 6 | 1 |
| F | 9 | 9 | \mathbf{0} |
| G | 12 | 12 | \mathbf{0} |
Le chemin critique
La définition
Les tâches de marge nulle forment le chemin critique : tout retard sur l’une d’elles retarde le projet d’autant.
Sur notre projet
B \to D \to F \to G \qquad 5 + 4 + 3 + 2 = \mathbf{14 \text{ jours}}
Ce que le gestionnaire en fait
Il concentre sa surveillance sur quatre tâches au lieu de sept.
Accélérer A, C ou E ne servirait à rien : leur marge d’un jour serait simplement absorbée. Pour raccourcir le projet, il faut agir sur le chemin critique.
Deux marges à distinguer
Marge totale et marge libre
La marge totale est le retard admissible sans retarder le projet.
La marge libre est le retard admissible sans retarder la tâche suivante.
Pourquoi la distinction compte
Consommer la marge totale d’une tâche peut mettre à zéro la marge de celles qui la suivent : le chemin critique se déplace.
La marge libre est la seule qu’on puisse utiliser sans rien changer au reste du plan.
Accélérer le projet
Le compromis coût-délai
Le crashing
Chaque tâche peut être raccourcie moyennant un surcoût. On raccourcit d’abord celle du chemin critique dont le coût par jour gagné est le plus faible.
Sur notre projet
Raccourcir B de 5 à 3 jours ferait passer le projet à 12 jours ?
Non. Le chemin A \to C \to E \to G dure 3+2+6+2 = 13 jours. Il devient critique dès que le premier descend en dessous.
La règle générale
On ne gagne jamais plus que l’écart avec le deuxième plus long chemin.
Au-delà, il faut raccourcir les deux à la fois. C’est pourquoi le crashing se fait pas à pas, en recalculant à chaque étape.
La version probabiliste
PERT à trois durées
Quand la durée est incertaine
On estime trois valeurs : optimiste a, la plus probable m, pessimiste b.
\mathbb{E}(d) = \frac{a + 4m + b}{6} \qquad \sigma(d) = \frac{b - a}{6}
Ce qu’on en tire
La durée du projet est la somme des durées critiques : sa variance est la somme des variances des tâches critiques.
Par le théorème central limite, on peut alors calculer la probabilité de tenir une échéance.
Le biais de PERT
Application en gestion
La méthode ne considère que le chemin critique espéré. Or un chemin non critique très variable peut le devenir.
PERT sous-estime donc systématiquement la durée du projet.
Le remède
Une simulation de Monte-Carlo tire les durées, recalcule le chemin critique à chaque tirage, et donne la distribution empirique de la durée totale.
Le chemin critique n’y est plus un chemin, mais une probabilité attachée à chaque chemin.
Ce qu’il faut retenir
Le résumé du chapitre
Six points
- La durée d’un projet est le plus long chemin, non la somme des durées : 14 contre 25.
- Le calcul avant donne les dates au plus tôt, le calcul arrière les dates au plus tard.
- La marge est leur différence ; les tâches de marge nulle sont critiques.
- Sur l’exemple, le chemin critique est B \to D \to F \to G.
- Le crashing ne gagne jamais plus que l’écart avec le deuxième plus long chemin.
- PERT probabiliste sous-estime la durée : il ignore les chemins qui peuvent devenir critiques.
La suite
Le chapitre 14 revient à la programmation linéaire pour lever son hypothèse la plus gênante : on ne fabrique pas 20{,}5 sacs, et arrondir la solution ne donne pas l’optimum entier.
Ressources du chapitre
- Diapositives
- Polycopié du chapitre
- Exercices corrigés
- Application interactive
- — Vidéo
- QCM (bientôt)