Correction exercice ordonnancement mpm -Programmation linair
Télécharger PDFOrdonnancement de Projet : Correction du TD N°4
Ce document présente la correction détaillée des exercices du TD n°4, axés sur les méthodes d'ordonnancement de projet. Nous allons explorer la construction de graphes potentiels-tâches (MPM), le calcul des calendriers au plus tôt et au plus tard, l'identification du chemin critique, et la détermination des marges pour une gestion optimale des projets.
Exercice 1 : Ordonnancement d'une Semaine de Ski
Tracé du Graphe Potentiels-Tâches (MPM) et AON
Le graphe potentiels-tâches, également connu sous le nom de graphe MPM (Méthode des Potentiels Métra) développé par Bernard Roy, ou encore graphe AON (Activities On Nodes), est une représentation graphique de l'enchaînement des tâches d'un projet. Dans ce type de graphe :
- Les tâches ou activités sont représentées par des sommets (nœuds).
- Les contraintes d'antériorité entre les tâches sont représentées par des arcs (flèches). Par exemple, si la tâche X doit s'exécuter avant la tâche Y, cela est symbolisé par un arc allant de X vers Y.
- Le graphe est valué : les arcs portent une valeur numérique correspondant aux durées des tâches. La durée de la tâche est affectée à l'arc partant de son sommet.
Pour faciliter la construction et la lecture du graphe, deux sommets fictifs sont introduits :
- Un sommet « Début » : il représente le lancement du projet et est rattaché à toutes les tâches n'ayant aucun prédécesseur.
- Un sommet « Fin » : il indique la fin du projet et est rattaché à toutes les tâches n'ayant aucun successeur.
Le graphe potentiels-tâches est par nature un graphe sans circuit, ce qui garantit un ordonnancement logique et sans boucle infinie.
Classement des Tâches par Niveaux
Afin de simplifier le tracé du graphe, il est courant de classer les tâches par niveaux. Cela consiste à identifier progressivement les tâches qui n'ont pas de prédécesseur ou dont tous les prédécesseurs sont d'un niveau inférieur. Les tâches sans prédécesseur sont automatiquement de niveau 0. L'algorithme est le suivant :
- Étape 1 : À partir du dictionnaire des prédécesseurs, identifier les tâches n'ayant aucun prédécesseur. Ces tâches sont de niveau 0. Rayer ces tâches du tableau.
- Étape 2 : Les tâches du nouveau niveau sont celles qui, après avoir rayé les tâches du niveau précédent, n'ont plus de prédécesseurs. Ces tâches sont rayées à leur tour.
- Étape 3 : S'il reste des tâches non rayées, retourner à l'étape 1. Sinon, le classement est terminé.
Appliquons cet algorithme pour le projet d'organisation d'une semaine de ski (Exercice 1) :
| Tâches | Tâches antérieures | N0 | N1 | N2 | N3 | N4 | N5 |
|---|---|---|---|---|---|---|---|
| A | - | A | |||||
| B | C | B | |||||
| C | - | C | |||||
| D | A | D | |||||
| E | D, J | E | |||||
| F | E, G, I, H, B | F | |||||
| G | J | G | |||||
| H | D, E, J | H | |||||
| I | J | I | |||||
| J | A | J |
Le tracé du graphe potentiels-tâches se réalise en plaçant les sommets selon l'ordre croissant de leurs niveaux, en ajoutant les arcs pour chaque contrainte d'antériorité et en introduisant les sommets fictifs "Début" et "Fin". Le graphe ainsi construit (réf. Figure 1 de l'énoncé) représente visuellement les dépendances entre les tâches.
Calcul du Calendrier au Plus Tôt (Dates EST)
Le calcul du calendrier au plus tôt vise à déterminer un planning d'activation des tâches permettant de réaliser le projet dans un temps minimal. Cette durée minimale correspond au chemin le plus long dans le graphe, ce qui peut sembler contre-intuitif mais est essentiel pour garantir que toutes les tâches et leurs enchaînements les plus longs soient pris en compte.
Pour chaque tâche, on détermine sa date de début « au plus tôt » (EST - Earliest Start Time). Pour qu'une tâche puisse commencer, il faut que toutes ses tâches prédécesseurs soient entièrement réalisées. On évalue donc le chemin le plus long entre le sommet "Début" du graphe et le sommet correspondant à la tâche en question.
Cet algorithme repose sur le principe d'optimalité de Bellman, qui stipule que pour trouver le plus long chemin d'un sommet de départ S0 à un sommet S, il suffit de prendre la plus grande des longueurs maximales des chemins arrivant aux sommets prédécesseurs de S, puis d'y ajouter la longueur des arcs reliant ces prédécesseurs à S.
On applique ce principe en partant du sommet "Début", auquel on attribue la valeur 0 (ou une date calendaire de démarrage). La date de début au plus tôt pour une tâche i est notée EST(i). De même, on calcule la date de fin au plus tôt pour une tâche i en ajoutant sa durée di : EFT(i) = EST(i) + di.
La représentation des tâches dans le graphe pour ces calculs est souvent un cadran :
EST(i)
i
LST(i)
Exemple : Pour la tâche E, qui a pour prédécesseurs les tâches D et J, et dont l'EST de ses prédécesseurs est 30 pour D et 30 pour J :
- Date de fin au plus tôt de D : EST(D) + Durée(D) = 30 + 3 = 33
- Date de fin au plus tôt de J : EST(J) + Durée(J) = 30 + 5 = 35
La tâche E ne peut commencer que lorsque ses deux prédécesseurs sont terminés. Par conséquent, EST(E) est la plus grande de ces dates de fin au plus tôt, soit EST(E) = 35.
Le graphe avec les calendriers au plus tôt (réf. Figure 2 de l'énoncé) illustre ces calculs pour toutes les tâches du projet.
Identification du Chemin Critique et Durée Optimale du Projet
Le chemin critique est défini comme le chemin le plus long entre le sommet "Début" et le sommet "Fin" du graphe. Sa longueur représente la durée minimale de réalisation de l'ensemble du projet.
Dans le cas de l'exercice 1, le chemin critique est constitué successivement des tâches C, B et F. La somme de leurs durées donne une longueur totale de 120. Ces tâches C, B et F sont appelées les tâches critiques du projet. Tout retard sur une tâche critique se répercutera directement sur la durée totale du projet.
La durée minimale de réalisation de ce projet est donc de 120 jours.
Calcul des Marges : Totales et Libres
Les marges sont des indicateurs clés pour l'ordonnancement, offrant une flexibilité dans l'exécution des tâches.
- Marge totale d'une tâche : C'est le délai maximal qu'une tâche peut prendre sans retarder la date d'achèvement du projet. Elle est calculée comme la différence entre sa date de début au plus tard (LST - Latest Start Time) et sa date de début au plus tôt (EST). Une tâche critique a toujours une marge totale nulle.
- Marge libre d'une tâche : C'est le délai maximal qu'une tâche peut prendre sans affecter le calendrier au plus tôt des tâches qui la suivent. Pour une tâche i avec une date de début au plus tôt EST(i) et une durée di, la marge libre est égale à la différence entre la plus petite des dates de début au plus tôt des tâches suivantes (successeurs) et (EST(i) + di).
Calcul du Calendrier au Plus Tard (Dates LST)
Pour calculer les marges totales, il est d'abord nécessaire de déterminer le calendrier au plus tard. Cette fois-ci, on procède en remontant le graphe, depuis le sommet "Fin" vers le sommet "Début".
La date de début au plus tard (LST) du sommet "Fin" est prise égale à sa date de début au plus tôt, c'est-à-dire la durée totale du projet (120 jours dans notre cas). Pour trouver la date de début au plus tard d'une tâche i de durée di, il faut avoir calculé les dates de début au plus tard de toutes les tâches Si qui suivent la tâche i. La date de début au plus tard de la tâche i sera égale à la plus petite valeur des différences (LST(Si) – di ).
Le graphe avec les calendriers au plus tôt et au plus tard (réf. Figure 3 de l'énoncé) intègre ces informations. On remarque que pour les tâches critiques (C, B et F), les calendriers au plus tôt et au plus tard sont identiques, ce qui confirme une marge totale nulle. Une marge totale nulle signifie que tout retard sur le démarrage de cette tâche aura un impact direct sur la durée totale du projet.
Résumé des Marges des Tâches Non Critiques
En utilisant les règles de calcul des marges mentionnées précédemment, le tableau suivant résume les marges totales et libres pour les tâches non critiques du projet :
| Tâche | Marge totale (en jours) | Marge libre (en jours) |
|---|---|---|
| A | 20 | 0 |
| D | 22 | 2 |
| E | 20 | 0 |
| G | 40 | 40 |
| H | 20 | 20 |
| I | 65 | 65 |
| J | 20 | 0 |
Mise à Jour du Graphe avec une Nouvelle Tâche
Le graphe peut être mis à jour pour intégrer de nouvelles tâches ou modifications. Dans cet exemple, une nouvelle tâche K est ajoutée. Cette tâche K ne peut commencer que sept jours après la fin de la tâche F et durera cinq jours.
Le nouveau graphe (réf. Figure 4 de l'énoncé) intègre cette modification, montrant un nouvel arc de F vers K avec un décalage temporel de 7 jours, et K se connectant au sommet "Fin".
Exercice 2 : Application à un Projet d'Exploitation
Tracé du Graphe MPM et Calcul des Calendriers au Plus Tôt et au Plus Tard
Pour modéliser ce second problème d'ordonnancement, nous suivons la même démarche. Nous commençons par classer les tâches par niveaux croissants pour optimiser la disposition des tâches sur le graphe et faciliter l'application des algorithmes de calcul des calendriers.
Classement des Tâches par Niveaux
Le classement des tâches est effectué à partir du tableau descriptif du projet, en utilisant les informations sur les opérations et leurs prédécesseurs :
| Opérations | Opérations précédentes | N0 | N1 | N2 | N3 | N4 | N5 |
|---|---|---|---|---|---|---|---|
| A | - | A | |||||
| B | A | B | |||||
| C | B | C | |||||
| D | B | D | |||||
| E | B | E | |||||
| F | B | F | |||||
| G | C, D | G | |||||
| H | E, F, G | H | |||||
| I | H, J | I | |||||
| J | E, F, G | J | |||||
| K | H, J | K | |||||
| L | H, J | L |
Dans le graphe potentiels-tâches, les tâches sont des sommets et les arcs représentent les contraintes de précédence. La contrainte "i précède j" est symbolisée par un arc entre les sommets i et j, dont la longueur correspond à la durée de la tâche associée au sommet i.
Le graphe MPM associé au projet (réf. Figure 1 de l'énoncé) est construit en suivant cette logique. Une fois le graphe établi, le calcul des calendriers au plus tôt et au plus tard peut être effectué en utilisant les algorithmes précédemment expliqués (parcours avant pour EST, parcours arrière pour LST). Les résultats de ces calculs sont reportés sur le graphe MPM (réf. Figure 2 de l'énoncé), avec les dates de début au plus tôt et au plus tard positionnées respectivement au-dessus et en dessous de chaque tâche.
Détermination du Chemin Critique et Durée Minimale de Réalisation
Le chemin critique est mis en évidence sur le graphe d'ordonnancement par un trait gras (réf. Figure 2). Il représente le chemin de longueur maximale du sommet "Début" au sommet "Fin", et sa longueur correspond à la durée minimale de réalisation du projet.
Dans ce cas, le chemin critique est constitué des tâches successives A, B, D, G, H, L. La somme des durées de ces tâches donne une longueur de 142. Par conséquent, la durée minimale pour la réalisation de l'ensemble du projet d'exploitation est de 142 semaines, ce qui équivaut à 35,5 mois.
Calcul des Marges pour les Tâches Non Critiques
En appliquant les mêmes règles de calcul des marges que dans l'Exercice 1, nous pouvons résumer les marges totales et les marges libres des opérations non critiques dans le tableau suivant :
| Tâche | Marge totale (en semaines) | Marge libre (en semaines) |
|---|---|---|
| C | 1 | 1 |
| E | 33 | 33 |
| F | 30 | 30 |
| I | 34 | 34 |
| J | 7 | 7 |
| K | 4 | 4 |
FAQ sur l'Ordonnancement de Projet
Qu'est-ce que le graphe potentiels-tâches (MPM ou AON) et à quoi sert-il ?
Le graphe potentiels-tâches est une représentation graphique des activités d'un projet et de leurs interdépendances. Chaque tâche est un nœud (sommet) et les contraintes d'antériorité sont des arcs (flèches). Il sert à visualiser l'enchaînement des travaux, à calculer les durées de projet et à identifier les tâches critiques. Il est fondamental pour l'ordonnancement et la planification.
Quelle est la différence entre la marge totale et la marge libre d'une tâche ?
La marge totale est le délai maximal qu'une tâche peut prendre sans retarder la date de fin du projet. Elle est cruciale pour identifier la flexibilité globale d'une tâche. La marge libre, quant à elle, est le délai maximal qu'une tâche peut prendre sans retarder le début au plus tôt de ses tâches successeurs. Elle indique la flexibilité locale d'une tâche, sans impacter les tâches immédiatement suivantes.
Pourquoi le chemin critique est-il si important dans la gestion de projet ?
Le chemin critique est la séquence de tâches qui détermine la durée minimale du projet. Il est composé de tâches critiques, qui n'ont aucune marge de manœuvre. Toute modification (retard ou accélération) sur une tâche du chemin critique aura un impact direct et équivalent sur la durée totale du projet. Il est essentiel pour les chefs de projet de surveiller de près ces tâches pour respecter les délais.