📋 Kritischer Pfad (CPM/PERT)

Der kritische Pfad ist die längste Folge abhängiger Aufgaben von Projektbeginn bis -ende, und seine Gesamtdauer entspricht der minimal möglichen Projektfertigstellungszeit. Aufgaben auf dem kritischen Pfad haben null Puffer (Slack), das heißt, jede Verzögerung bei ihnen verzögert direkt das gesamte Projekt. Der Simulator hebt diese Aufgaben und ihre verbindenden Kanten rot hervor, sodass Sie sie sofort erkennen.

Wählen Sie ein voreingestelltes Projekt aus dem Dropdown (Lehrbuch-DAG, Parallele Stränge oder Fast-Gleichstand), um einen gerichteten azyklischen Graphen von Aufgaben zu laden. Klicken Sie auf einen Knoten, um ihn auszuwählen, und ziehen Sie dann den Dauerregler, um seine Länge zu ändern und den kritischen Pfad in Echtzeit neu berechnen zu sehen. Nutzen Sie die Schritt-Taste, um den Vorwärts- und dann den Rückwärtsdurchlauf schrittweise zu animieren, oder Auto, um die vollständige Animation abzuspielen. Wechseln Sie in den PERT-Modus, um erwartete Dauern zu sehen und eine Frist festzulegen, um die Wahrscheinlichkeit einer pünktlichen Fertigstellung zu erhalten.

Puffer, auch Slack genannt, ist die Zeit, um die eine Aufgabe verzögert werden kann, ohne die Projektfertigstellung zu verzögern. Er wird berechnet als spätester Start minus frühester Start (oder gleichwertig spätestes Ende minus frühestes Ende). Aufgaben mit null Puffer sind kritisch; Aufgaben mit positivem Puffer können verzögert werden oder Ressourcen können auf kritische Aufgaben verschoben werden — eine Technik namens Ressourcenglättung, die zentral für praktisches Projektmanagement ist.

PERT modelliert jede Aufgabendauer als Beta-Verteilung, parametrisiert durch drei Zeitschätzungen: optimistisch (o, bester Fall), wahrscheinlichst (m, Modus) und pessimistisch (p, schlechtester Fall). Die erwartete Dauer ist t_e = (o + 4m + p) / 6, ein gewichteter Durchschnitt, der der wahrscheinlichsten Schätzung viermal so viel Gewicht gibt. Die Varianz für jede Aufgabe ist σ² = ((p − o) / 6)². Für den gesamten kritischen Pfad werden die Varianzen summiert (Aufgaben gelten als unabhängig), was die Pfadvarianz ergibt, die zur Berechnung des Z-Werts für die Fristwahrscheinlichkeit verwendet wird.

Sobald die erwartete Projektdauer μ und die summierte kritische-Pfad-Varianz σ² bekannt sind, verwendet die Fristwahrscheinlichkeit die Normalnäherung: Z = (Frist − μ) / σ, wobei σ = √σ². Die kumulative Normalverteilung bei Z liefert P(T ≤ Frist). Der Simulator verwendet die Abramowitz-&-Stegun-Polynomnäherung der Fehlerfunktion (erf), um dies ohne externe Bibliotheken zu berechnen. Eine Frist gleich der erwarteten Dauer ergibt etwa 50 % Wahrscheinlichkeit; die Addition von einem σ erhöht sie auf etwa 84 %.

Ja. Mehrere Pfade durch das Netzwerk können dieselbe maximale Dauer teilen, was sie alle gleichzeitig kritisch macht. Dies wird durch das Fast-Gleichstand-Preset im Simulator veranschaulicht, bei dem zwei parallele Routen nahezu gleiche Längen haben — eine kleine Änderung an einer Aufgabe auf einer der beiden Routen kann verschieben, welcher Pfad kritisch ist. Mehrere kritische Pfade zu haben, gilt als höheres Risiko, da jede Verzögerung auf einem dieser Pfade sofort das Projektende beeinflusst.

CPM wurde 1957 von Morgan Walker (DuPont) und James Kelley (Remington Rand) für die Planung von Chemieanlagen-Überholungen entwickelt. PERT wurde unabhängig und fast gleichzeitig (1957–1958) vom US Navy Special Projects Office zusammen mit Booz Allen Hamilton für das Polaris-Flottenballistikraketenprogramm entwickelt, das die Koordination Tausender Auftragnehmer und Unterauftragnehmer erforderte. Beide Methoden wurden 1959 erstmals veröffentlicht und tragen wesentlich dazu bei, dass der Zeitplan des Polaris-Programms um zwei Jahre verkürzt wurde.

CPM und PERT erfordern einen gerichteten azyklischen Graphen (DAG) — einen gerichteten Graphen ohne Zyklen — weil eine zyklische Abhängigkeit (A hängt von B ab, B hängt von A ab) die Planung logisch unmöglich machen würde. Die topologische Sortierung, die in den Vorwärts- und Rückwärtsdurchläufen verwendet wird, ist nur für DAGs gültig. Reale Projektnetzwerke sind per Definition immer DAGs: Eine Aufgabe kann nicht beginnen, bevor sie selbst beendet ist. Der Simulator erzwingt dies, indem nur die voreingestellten azyklischen Strukturen verwendet werden.

CPM ist in Werkzeuge wie Microsoft Project, Primavera P6 und Open-Source-Alternativen wie ProjectLibre eingebettet. Im Bauwesen schreibt die Association for the Advancement of Cost Engineering (AACE) CPM-Planung für große Projekte vor; bei Softwareprojekten liegt CPM der Gantt-Diagramm-Erstellung in Jira und ähnlichen Plattformen zugrunde. Die PERT-Dreipunktschätzung ist auch die Grundlage für Planning-Poker-Verfeinerungen und Referenzklassenprognosen, die beim agilen Story-Pointing verwendet werden.

CPM geht von deterministischen Dauern aus, was in der Praxis selten zutrifft. PERT begegnet dem teilweise, geht aber weiterhin von Unabhängigkeit zwischen Aufgabendauern aus (korrelierte Risiken werden ignoriert) und nähert die Verteilung der Pfaddauer als normal an, was die Verzögerungswahrscheinlichkeit unterschätzt — die sogenannte „Merge-Bias“ oder „PERT-Bias“. Monte-Carlo-Simulation (Stichprobenziehung Tausender zufälliger Szenarien) ist die moderne Abhilfe, die in risikoadjustierten Planungswerkzeugen verwendet wird. Zudem berücksichtigt keine der beiden Methoden Ressourcenbeschränkungen; dafür ist ressourcenbeschränkte Projektplanung (RCPS) nötig, die im Allgemeinen NP-schwer ist.

Resource-Constrained Project Scheduling (RCPS) fügt CPM Ressourcengrenzen hinzu, wodurch es NP-schwer wird. Critical Chain Project Management (CCPM), vorgeschlagen von Eliyahu Goldratt, verlagert Puffer von einzelnen Aufgaben an das Ende der Kette und zu Zulieferketten. Der Zeit-Kosten-Kompromiss (Crashing) erweitert CPM, indem er erlaubt, zusätzliches Geld auszugeben, um Aufgabendauern zu verkürzen, und fragt: Was ist der günstigste Weg, das Projekt um einen bestimmten Betrag zu verkürzen? Diese Erweiterungen sind aktive Forschungsgebiete im Operations Research und Management.