Ordonnancement de projet avec contraintes -Programmation lin
Télécharger PDFRecherche Opérationnelle et Aide à la Décision (RCP101) – Fiche N°3 : Ordonnancement de Projet
Cette fiche présente trois exercices détaillés sur l'ordonnancement de projet, couvrant les méthodes PERT et MPM, le calcul des dates au plus tôt et au plus tard, les marges, l'identification des chemins critiques et l'analyse des coûts en cas de raccourcissement de projet.
Exercice 1 : Ordonnancement de Projet avec Graphe PERT
Un projet a été décomposé en 11 tâches. Ces tâches ont entre elles des contraintes de précédence représentées par le tableau ci-dessous :
| Tâches | Durée (jours) | Tâches préalables |
|---|---|---|
| A | 4 | - |
| B | 6 | A |
| C | 2 | 2 jours après le début du projet |
| D | 6 | - |
| E | 1 | B |
| F | 4 | C |
| G | 3 | B et D |
| H | 5 | E et G |
| I | 6 | B et F |
| J | 3 | I et H |
| K | 4 | I et H |
1. Tracer un graphe PERT (événement-opération) relatif à ce projet
Le graphe PERT (Program Evaluation and Review Technique) est un outil de gestion de projet qui permet de représenter les différentes tâches d'un projet sous forme de réseau, où les nœuds représentent les événements (début ou fin d'une tâche) et les arcs représentent les tâches (opérations) et leur durée. Il aide à visualiser les dépendances et à déterminer le chemin critique.
2. Calculer les dates au plus tôt des événements
La date au plus tôt d'un événement est la date minimale à laquelle cet événement peut être atteint, en tenant compte des durées de toutes les tâches précédentes.
3. Calculer les dates au plus tard des événements
La date au plus tard d'un événement est la date maximale à laquelle cet événement peut être atteint sans retarder la fin du projet.
4. Calculer les marges libres des tâches
La marge libre d'une tâche est le temps dont on peut retarder le début de cette tâche sans retarder la date au plus tôt du début d'une tâche suivante.
5. Calculer les marges totales des tâches
La marge totale d'une tâche est le temps dont on peut retarder le début de cette tâche sans retarder la date de fin du projet.
6. Identifier les tâches critiques
Les tâches critiques sont les tâches dont la marge totale est nulle. Elles appartiennent au chemin critique, le plus long chemin dans le graphe PERT, dont tout retard entraîne un retard équivalent pour la date de fin du projet.
7. Conséquences des retards des tâches D et G sur le déroulement du projet
On suppose que lors de l’exécution du projet les deux tâches D et G ont été retardées respectivement de 4 et 1 journées. Il s'agit d'analyser l'impact de ces retards sur le chemin critique et la date de fin du projet.
Exercice 2 : Ordonnancement Optimal avec Graphe MPM
On désire déterminer l’ordonnancement optimal d’un projet dont les tâches, leurs durées et leurs contraintes d’antériorité sont données dans le Tableau 1.
Tableau 1
| Tâches | Durée (en jours) | Tâches préalables |
|---|---|---|
| A | 70 | - |
| B | 15 | - |
| C | 25 | ne peut commencer que 20 jours après le début de A |
| D | 10 | ne peut commencer que 50 jours après le début du projet |
| E | 60 | B et C |
| F | 15 | A et D |
| G | 70 | E |
| H | 15 | D |
| I | 5 | F |
| J | 5 | H et N |
| K | 30 | I et N |
| L | 30 | I et M |
| M | 40 | E et J |
| N | 10 | F |
| O | 15 | G, K, L |
1. Construire le graphe MPM et calculer les dates au plus tôt et au plus tard
Il est demandé de construire le graphe MPM (Méthode des Potentiels Métra) associé à cet ordonnancement. Ensuite, il faut calculer la date au plus tôt t_i et la date au plus tard t_i* associées au début de la tâche i. Le graphe MPM représente les tâches par des nœuds et les contraintes de précédence par des arcs.
2. Calculer les marges totales des tâches et donner les tâches et les chemins critiques
Les marges totales des tâches représentent le temps de flexibilité dont dispose une tâche sans affecter la durée totale du projet. Les tâches critiques sont celles dont la marge totale est nulle, et les chemins critiques sont les séquences de tâches critiques qui déterminent la durée minimale du projet.
3. Calculer les marges libres des tâches non critiques
La marge libre m_i de l’activité i se calcule de la manière suivante :
m_i = min [ t_j - d_ij - t_i ] pour tout j successeur de i
où d_ij : temps d’attente imposé entre le début de i et le début de j (en général la durée de l'activité i).
4. Conséquences des retards sur les délais de réalisation et les chemins critiques
La situation au début du 80e jour, mise en évidence par un contrôle d’exécution, se présente de la manière suivante :
- Les tâches A et H sont terminées mais la tâche A a dû être prolongée de 5 jours.
- Les tâches E et F sont en cours (commencées respectivement depuis 30 et 5 jours).
- La tâche I ne pourra pas commencer avant la date 120.
Il est nécessaire d'évaluer les conséquences de ces retards sur les délais de réalisation et sur les chemins critiques du projet.
Exercice 3 : Optimisation des Coûts par Raccourcissement de Projet
On considère un projet formé de 6 tâches élémentaires. Des coûts pour chacune des tâches sont fixés en tenant compte des surcoûts liés aux raccourcissements possibles. Le tableau qui suit indique leur durée, leurs contraintes d’antériorité et leurs coûts.
| Tâches | Tâches préalables | Durée normale (jours) | Durée crash (jours) | Coût normal | Coût crash | Coût par jour de réduction |
|---|---|---|---|---|---|---|
| A | - | 2 | 1 | 30 | 50 | 20 |
| B | - | 2 | 2 | 30 | 30 | 0 |
| C | A | 2 | 1 | 25 | 50 | 25 |
| D | A | 4 | 2 | 60 | 80 | 10 |
| E | B,D | 1 | 1 | 20 | 20 | 0 |
| F | D | 2 | 1 | 20 | 50 | 30 |
1. Construire le graphe MPM associé à cet ordonnancement et calculer les dates au plus tôt et au plus tard des débuts des tâches
Il faut d'abord modéliser le projet à l'aide d'un graphe MPM pour visualiser les dépendances et calculer les dates limites de début de chaque tâche.
2. Calculer les marges totales des activités
La marge totale est essentielle pour identifier la flexibilité de chaque tâche et les chemins critiques.
3. Procéder étape par étape au raccourcissement du projet, en minimisant jour après jour les surcoûts qui en résultent
Cette question implique une analyse du "crashing" de projet, où l'on cherche à réduire la durée totale du projet en accélérant certaines tâches, tout en minimisant les coûts additionnels associés à cette accélération. Il faut identifier les tâches critiques qui peuvent être raccourcies et celles qui offrent le meilleur ratio coût/jour de réduction.
Questions Fréquemment Posées (FAQ)
Qu'est-ce que la méthode PERT et en quoi diffère-t-elle du MPM ?
La méthode PERT (Program Evaluation and Review Technique) est une technique de gestion de projet utilisée pour analyser les tâches nécessaires à la réalisation d'un projet donné, en particulier les tâches nécessaires à l'achèvement d'un projet dans un délai minimum. Elle est axée sur les événements et est utile pour estimer les durées de tâches incertaines. La méthode MPM (Méthode des Potentiels Métra), aussi connue sous le nom de méthode des chemins critiques (CPM), est centrée sur les tâches et leurs dépendances. Elle est généralement utilisée lorsque les durées des tâches sont connues avec plus de certitude et vise à identifier le chemin critique pour optimiser le délai.
Quelle est la différence entre la marge libre et la marge totale d'une tâche ?
La marge libre d'une tâche est le temps maximum pendant lequel une tâche peut être retardée sans affecter la date de début au plus tôt de toute tâche successeur. Elle représente une flexibilité locale. La marge totale, quant à elle, est le temps maximum pendant lequel une tâche peut être retardée sans retarder la date de fin du projet. C'est une flexibilité globale et elle est nulle pour les tâches du chemin critique.
À quoi sert le "crashing" (raccourcissement) dans l'ordonnancement de projet ?
Le "crashing" de projet est une technique utilisée pour réduire la durée totale d'un projet en accélérant certaines tâches, généralement en y allouant des ressources supplémentaires, ce qui entraîne des coûts additionnels. L'objectif est de trouver le meilleur équilibre entre la réduction de la durée du projet et l'augmentation des coûts, souvent pour respecter des délais serrés ou pour optimiser les pénalités de retard.