Chemin critique et durée minimale du projet

Terminale Technologique · Mathématiques STMG Terminale

À retenir

• Le chemin critique est le plus long chemin du graphe des tâches, du début au jalon final. • Sa longueur est la durée minimale du projet : 36 jours pour le déménagement de Vallobre. • Une tâche est critique si sa marge totale est nulle ; toute autre peut attendre. • Début au plus tôt : DTo(k) = FTo(p) sur tous les prédécesseurs p, puis FTo(k) = DTo(k) + d(k).

Le cours

1. Chemin critique et durée minimale Un chemin du graphe est une suite de tâches reliées par des arcs, du début à la fin du projet. Le chemin critique est le plus long de ces chemins : c'est celui qui fixe la durée minimale du projet, celle que l'on ne peut pas réduire sans raccourcir l'une de ses tâches. • Sa longueur est la somme des durées de ses tâches : c'est la durée minimale du projet. • Chaque tâche qui le compose a une marge totale nulle : elle ne peut pas attendre. • Raccourcir une tâche hors du chemin critique ne réduit pas la durée du projet. • Une contrainte de date (attente imposée) peut rendre la durée du projet plus longue que cette somme. Tâche Durée Début au plus tôt Fin au plus tôt A 4 0 4 B 5 0 5 C 6 4 10 D 8 10 18 E 7 18 25 F 5 25 30 G 4 30 34 H 2 34 36 I 5 10 15 Z 0 36 36 2. Le balayage avant, pas à pas On parcourt le graphe dans l'ordre topologique et on remplit deux colonnes. Pour chaque tâche, le début au plus tôt est la plus grande des fins de ses précédents, et la fin au plus tôt vaut ce début plus la durée. On les note DTo et FTo. • A et B n'ont pas de précédent : DTo = 0 et FTo = d. • C : DTo(C) = (FTo(A)) = 4, donc FTo(C) = 4 + 6 = 10. • E : DTo(E) = (18, 5) = 18 : c'est D, et non B, qui commande. • Z : DTo(Z) = (36, 15) = 36 : la durée minimale du projet vaut 36 jours. 3. Pièges de calcul • Chercher le chemin le plus court : c'est le chemin le plus long qui fixe la durée du projet. • Oublier la tâche B au moment du maximum pour E : ici 18 > 5 donne le bon résultat par chance ; si B durait 20 jours, E ne pourrait démarrer qu'au jour 20. • Additionner les durées de toutes les tâches : on obtient 46 jours, la charge, pas la durée du projet. • Conclure trop vite au raccourcissement : une tâche hors chemin critique peut être réduite sans effet.

Dans ce chapitre