Kritischer Pfad Rechner

Pseudocode

Zwei Durchläufe über das Vorgangsnetz in topologischer Ordnung: vorwärts für den frühestmöglichen Zeitpunkt jedes Vorgangs, rückwärts für den spätesten, ohne das Projekt zu verzögern.

CPM(vorgänge, abhängigkeiten):
    ordnung = topologischeSortierung(vorgänge)

    // Vorwärtsdurchlauf: frühester Start und frühestes Ende
    für jeden Vorgang a in ordnung:
        FA[a] = max(FE[p] für p Vorgänger von a), sonst 0
        FE[a] = FA[a] + dauer[a]
    T = max(FE[a] über alle a)      // Projektdauer

    // Rückwärtsdurchlauf: spätester Start und spätestes Ende
    für jeden Vorgang a in umgekehrt(ordnung):
        SE[a] = min(SA[s] für s Nachfolger von a), sonst T
        SA[a] = SE[a] - dauer[a]

    puffer[a] = SA[a] - FA[a]
    kritischer Pfad = Vorgänge mit Puffer 0

Der kritische Pfad ist der längste Weg durch das Netz, nicht der kürzeste, was daraus ein Maximierungsproblem auf einem DAG macht und kein Kürzeste-Wege-Problem. Da das Netz azyklisch ist, sind beide Durchläufe schlicht dynamische Programmierung in topologischer Ordnung, eine Prioritätswarteschlange wird nicht gebraucht. Puffer null bedeutet, dass der Vorgang keinerlei Spielraum hat: verzögere ihn um einen Tag und das gesamte Projekt verschiebt sich um einen Tag.

Durchgerechnetes Beispiel, Schritt für Schritt

Plane ein Projekt aus vier Vorgängen, bei dem zwei Aufgaben parallel laufen können, aber beide fertig sein müssen, bevor die dritte beginnt.

Beispielgraph: Vorgänge mit Dauern A (3 Tage), B (2 Tage), C (4 Tage) und D (2 Tage). Abhängigkeiten: A und B müssen C vorausgehen, und C geht D voraus.

1. Vorwärtsdurchlauf, A und B. Keiner hat einen Vorgänger, beide beginnen also zum Zeitpunkt 0. A endet bei 3, B endet bei 2. Sie laufen parallel.
2. Vorwärtsdurchlauf, C. C wartet auf beide, sein frühester Start ist also das Maximum aus 3 und 2, mithin 3. Er dauert 4 Tage und endet bei 7. Beachte, dass B einen Tag früher fertig war und schlicht wartet.
3. Vorwärtsdurchlauf, D. D beginnt bei 7 und endet bei 9. Nichts folgt darauf, die Projektdauer beträgt also 9 Tage.
4. Rückwärtsdurchlauf. Von 9 aus zurückgerechnet: D muss spätestens bei 7 beginnen, also muss C bei 7 enden und bei 3 beginnen. Damit müssen A und B beide bei 3 fertig sein, was A einen spätesten Start von 0 und B einen von 1 gibt.
5. Puffer berechnen. A hat spätesten Start 0 gegenüber frühestem Start 0, also Puffer 0. B hat spätesten Start 1 gegenüber frühestem Start 0, also Puffer 1. C und D haben beide Puffer 0.

Das Projekt dauert 9 Tage und der kritische Pfad lautet A nach C nach D. B besitzt einen Tag Puffer, kann also einen Tag später beginnen oder einen Tag überziehen, ohne den Endtermin zu berühren. Das ist der praktische Nutzen: es sagt einer Projektleitung genau, wo sie ihre Aufmerksamkeit bündeln muss. B zu verkürzen bringt nichts, während das Verkürzen von A, C oder D das gesamte Projekt verkürzt, jedenfalls bis der kritische Pfad wechselt und stattdessen über B verläuft.

Komplexität und woher sie kommt

Zeit: O(V + E) · Speicher: O(V)

Eine topologische Sortierung kostet O(V + E), und jeder der beiden Durchläufe besucht jeden Vorgang einmal und jede Abhängigkeitskante einmal, ist also ebenfalls O(V + E). Der Speicher besteht aus vier Zahlen je Vorgang, frühester und spätester Start und frühestes und spätestes Ende, mithin O(V). Das gesamte Verfahren ist linear, weshalb es auf Projektnetze mit Hunderttausenden Vorgängen skaliert. Das Abhängigkeitsnetz muss ein gerichteter azyklischer Graph sein: eine zirkuläre Abhängigkeit besitzt keine topologische Ordnung und entsprechend keinen gültigen Terminplan, die Zyklenerkennung ist also eine echte Voraussetzung und keine Formalität.

Wann Methode des kritischen Pfades (CPM) passt und wann nicht

CPM setzt bekannte Dauern und unbegrenzte Ressourcen voraus. Lockert man eine der beiden Annahmen, ändert sich das Problem.

Häufige Fehler

• Im Vorwärtsdurchlauf das Minimum statt des Maximums nehmen. Ein Vorgang kann erst beginnen, wenn alle Vorgänger fertig sind, der früheste Start ist also das Maximum über die Endzeitpunkte der Vorgänger. Das Minimum zu nehmen liefert einen unmöglich kurzen und stillschweigend falschen Terminplan.
• Annehmen, der kritische Pfad sei eindeutig. Mehrere Wege können als längste gleichauf liegen, und dann hat jeder Vorgang auf allen von ihnen Puffer null. Nur einen zu verkürzen bringt nichts, weil der andere kritische Pfad den Endtermin weiterhin bestimmt.
• Vergessen, dass der kritische Pfad wandert. Verkürze einen kritischen Vorgang weit genug, und ein anderer Weg wird zum längsten. Crashing muss nach jeder Änderung neu bewertet werden, statt en bloc aus der ursprünglichen Analyse angewandt zu werden.
• Ressourcengrenzen ignorieren. CPM nimmt an, dass A und B tatsächlich gleichzeitig laufen können. Brauchen beide dieselbe Maschine oder dieselbe Person, ist der Terminplan Fiktion und es braucht stattdessen RCPSP.
• Es auf einem Netz mit Zyklus ausführen. Eine zirkuläre Abhängigkeit bedeutet, dass keine topologische Ordnung existiert und kein Terminplan gültig ist. Erkenne den Zyklus und melde ihn, statt aus einer Teilordnung Zahlen zu erzeugen.

Häufig gestellte Fragen

Was ist die Critical-Path-Methode?

CPM findet den längsten Weg durch ein Netz aus Vorgängen und Abhängigkeiten, was die kürzestmögliche Projektdauer bestimmt. Vorgänge auf diesem Weg haben Puffer null, jede Verzögerung dort verzögert also das gesamte Projekt. Berechnet wird sie mit einem Vorwärtsdurchlauf für die frühesten und einem Rückwärtsdurchlauf für die spätesten Zeitpunkte.

Was ist Puffer oder Pufferzeit in CPM?

Puffer ist die Zeit, um die ein Vorgang verzögert werden kann, ohne den Projektendtermin zu verschieben, berechnet als spätester Start minus frühester Start. Vorgänge mit Puffer null sind kritisch. Im obigen Beispiel hat Vorgang B einen Tag Puffer, während A, C und D keinen haben.

Wie ist die Zeitkomplexität der Critical-Path-Methode?

O(V + E), wobei V die Vorgänge und E die Abhängigkeiten sind. Es ist eine topologische Sortierung gefolgt von zwei linearen Durchläufen über das Netz, das skaliert also mühelos auf sehr große Projektpläne.

Was ist der Unterschied zwischen CPM und PERT?

CPM verwendet eine einzige deterministische Dauer je Vorgang und konzentriert sich darauf, den kritischen Pfad und die Puffer zu bestimmen. PERT verwendet drei Schätzungen je Vorgang, optimistisch, wahrscheinlichst und pessimistisch, um eine erwartete Dauer und eine Varianz zu berechnen, womit sich die Wahrscheinlichkeit für einen Termin angeben lässt. Die Netzanalyse selbst ist dieselbe.

Kann sich der kritische Pfad während eines Projekts ändern?

Ja, und das ist die wichtigste praktische Falle. Wird ein kritischer Vorgang verkürzt oder überzieht ein unkritischer seinen Puffer, kann ein anderer Weg zum längsten werden. Die Analyse muss mit den tatsächlich bekannten Dauern wiederholt werden, statt zum Planungszeitpunkt als feststehend behandelt zu werden.