Metoda Ścieżki Krytycznej: Znalezienie Łańcucha, Którego Nie Można Przesunąć

Projekt jest grafem, a nie listą

Metoda Krytycznej Ścieżki, niezależnie opracowana w DuPont i Remington Rand pod koniec lat 50-tych, modeluje projekt jako graf skierowany acykliczny (DAG): każda czynność jest węzłem z określoną długością trwania, a krawędź od zadania A do zadania B oznacza, że B nie może rozpocząć się przed zakończeniem zadania A. Harmonogram projektu to nie sekwencja, lecz sieć tych zależności – niektóre czynności mogą wykonywać równolegle, inne muszą czekać, a termin ukończenia jest ustalany przez najdłuższą ścieżkę zależnych zadań, która trwa od początku do końca.

Przebieg w przód: kiedy może rozpocząć się jakakolwiek czynność?

Przenosząc się po grafie Diraca w kolejności topologicznej, czas rozpoczęcia (ES) każdej czynności jest najpóźniejszym czasem zakończenia poprzedzających ją czynności, a czas zakończenia (EF) tej czynności to prosta suma czasu rozpoczęcia i jej trwania. Ten przebieg w przód rozprzestrzenia możliwie najszybszy harmonogram przez cały sieć i informuje o najwcześniejszym możliwym terminie ukończenia projektu – EF ostatniej czynności.

Wsteczny przejazd: jak późno może rozpocząć się każda czynność?

Teraz przesuwamy się wstecz od ustalonej daty zakończenia projektu. Ostatni termin ukończenia (LF) każdej czynności to najwcześniejszy czas, w którym może zostać zakończona, biorąc pod uwagę terminy rozpoczęcia następujących po niej czynności. Ostatni termin rozpoczęcia (LS) jest równy LF pomniejszonemu o jej czas trwania. Ten przejazd odpowiada na inne pytanie: jak bardzo można przesunąć początek każdej czynności, zanim zacznie wpływać negatywnie na ogólną datę zakończenia?

forward pass (topological order):
  ES(task) = max( EF(pred) for pred in predecessors ), 0 if none
  EF(task) = ES(task) + duration(task)

backward pass (reverse topological order):
  LF(task) = min( LS(succ) for succ in successors ), projectFinish if none
  LS(task) = LF(task) − duration(task)

slack(task) = LS(task) − ES(task)     // = LF(task) − EF(task)
critical path = every task with slack(task) == 0

Przebieg (Slack) i ścieżka, której nie można przesunąć

Odejmowanie ES od LS daje wartość przebiegu (również zwana marginesem zapasowym) dla każdego zadania: o ile dni można je opóźnić bez przesunięcia daty zakończenia projektu. Zadania z dodatnim przebiegiem mają rezerwy czasowe - zadanie z przebiegiem 2 dni może rozpocząć się o dwa dni później, a projekt nadal zakończy się na terminie. Zadania z zerowym przebiegiem nie mają żadnych rezerw: każde opóźnienie w nich powoduje opóźnienie całego projektu. Połączone ze sobą, zadania z zerowym przebiegiem tworzą ścieżkę krytyczną – zgodnie z konstrukcją, jest to najdłuższa możliwa trasa przez graf zależności i dlatego najkrótszy czas, jaki projekt może zrealizować. Projekt może mieć więcej niż jedną ścieżkę krytyczną, jeśli dwie lub więcej łańcuchów o równym najdłuższemu czasie trwania.

PERT: Przekształcanie jednej wartości czasu trwania w prawdopodobieństwo

METE (Program Ewaluacji i Kontroli) zakłada, że każda zadanie ma pojedyncze, znane czas trwania, co rzadko jest prawdą w praktyce. Program Ewaluacji i Kontroli (PERT), opracowany dla programu Polaris US Navy około tej samej pory, zamiast tego prosi o trzy szacunki na zadanie - optymistyczny (o), najbardziej prawdopodobny (m) i pesymistyczny (p) – a następnie łączy je przy użyciu przybliżenia rozkładu beta w celu uzyskania oczekiwanego czasu trwania i wariancji:

oczekiwane czas trwanie: te = (o + 4m + p) / 6 wariancja: v = ((p − o) / 6)² wariancja projektu ≈ suma wariancji zadań na ścieżce krytycznej P(wykonanie ≤ termin) ≈ Φ( (termin – Σte) / √(Σv) ) // przybliżenie normalne Sumowanie oczekiwanego czasu trwania i wariancji wzdłuż ścieżki krytycznej, a następnie zastosowanie przybliżenia normalnego wynikające z twierdzenia o granicznej całce, przekształca pojedynczy deterministyczny harmonogram w szacunek prawdopodobieństwa, że cały projekt zostanie zakończony do celu terminie – naprawdę użyteczna odpowiedź na pytanie "jak pewni jesteśmy tego terminu" zamiast pojedynczej optymistycznej liczby.

expected duration:  te = (o + 4m + p) / 6
variance:           v  = ((p − o) / 6)²

project variance ≈ sum of variances of tasks on the critical path
P(finish ≤ deadline) ≈ Φ( (deadline − Σte) / √(Σv) )   // normal approximation

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Critical Path Method i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.