Algorithme de recherche du chemin critique par balayage

Terminale Technologique · Mathématiques STMG Terminale

À retenir

• Quatre phases : ordre topologique, dates au plus tôt, dates au plus tard, sélection des marges nulles. • Au plus tôt : DTo(k) = FTo(p) ; au plus tard : FTa(k) = DTa(s). • Le chemin critique est la liste des tâches de marge nulle, lue dans l'ordre topologique. • Sans initialisation ni ordre topologique, l'algorithme ne donne aucune date fiable.

Le cours

1. Les quatre phases du balayage Le chemin critique se cherche par un algorithme en quatre temps : on numérote les tâches dans un ordre topologique, on calcule les dates au plus tôt, puis les dates au plus tard, et on repère enfin les tâches de marge nulle. Le même algorithme convient à un projet de dix tâches comme à un planning de mille. • Phase 1 : un ordre topologique h(k) tel que h augmente le long de toute flèche. • Phase 2 : DTo(k) = FTo(p), puis FTo(k) = DTo(k) + d(k). • Phase 3 : FTa(k) = DTa(s), puis DTa(k) = FTa(k) - d(k). • Phase 4 : marge nulle, donc chemin critique. • Notations : DTo et FTo = début et fin au plus tôt ; DTa et FTa = début et fin au plus tard. 2. Pseudo-code du balayage Le programme se lit ligne par ligne ; les deux boucles encadrent les deux sens de lecture, et la dernière boucle isole le chemin critique. • Initialiser DTo(k) = 0 et FTo(k) = 0 pour toute tâche k. • Pour h croissant : pour chaque tâche k de rang h, DTo(k) des FTo(p), p prédécesseur de k, puis FTo(k) DTo(k) + d(k). • FTa(Z) FTo(Z), puis pour h décroissant : FTa(k) des DTa(s), s successeur de k, et DTa(k) FTa(k) - d(k). • Écrire dans L toute tâche k telle que DTa(k) - DTo(k) = 0 : la liste L est le chemin critique. Rang h Tâches de ce rang Précédents Durée du rang 0 A, B aucun 4 et 5 1 C A 6 2 D, I C 8 et 5 3 E D, B 7 4 F E 5 5 G F 4 6 H G 2 7 Z H, I 0 3. Pièges d'implémentation • Parcourir les tâches dans l'ordre du tableau et non dans l'ordre topologique : une date est alors calculée avant ses prédécesseurs. • Oublier d'initialiser à 0 : les dates affichées sont celles de l'exécution précédente. • Prendre le minimum au lieu du maximum des fins au plus tôt des prédécesseurs : les dates au plus tôt sont sous-estimées (voir l'exemple 2). • Chercher le chemin critique parmi les tâches de durée maximale : c'est un indice, pas une preuve.

Dans ce chapitre