Graphentheorie im Projektmanagement

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Warum ein Zeitplan ein Graph ist

Jeder Projektplan trifft zwei Arten von Aussagen. Die erste betrifft Arbeit: Diese Aufgabe dauert neun Tage. Die zweite betrifft Reihenfolge: Diese Aufgabe kann erst beginnen, wenn jene abgeschlossen ist. Schreiben Sie hundert von jeder Sorte auf, und Sie haben keine Liste geschrieben, sondern einen Graphen. Die Aufgaben sind die Knoten, die Reihenfolgebedingungen sind die gerichteten Kanten, und die Dauern sind Gewichte.

Das ist keine Sichtweise auf Projektpläne. Es ist das, was ein Projektplan ist, und wer das erkennt, kann andere Fragen stellen. Eine Aufgabenliste sagt Ihnen, wie viel Arbeit es gibt. Nur der Graph sagt Ihnen, wie lange das Projekt dauert, und das ist eine andere und meist viel größere Zahl, weil Arbeit, die nicht parallel laufen kann, nacheinander laufen muss.

Die Folgen sind unmittelbar und etwas überraschend. Die Dauer eines Projekts ist weder die Summe seiner Vorgangsdauern noch die größte davon. Sie ist die Länge des längsten Pfades durch das Netz. Deshalb umfasst das Projekt in diesem Artikel zweiundsiebzig Tage Arbeit und ist trotzdem nach neununddreißig fertig. Deshalb hilft zusätzliches Personal nicht automatisch, deshalb ist die Aufgabe, um die sich alle sorgen, oft nicht die entscheidende, und deshalb kann ein Plan in sich widersprüchlich sein, auf eine Weise, die kein Einsatz der Welt behebt.

Die Verfahren in diesem Artikel entstanden innerhalb eines Jahres, beide unter kommerziellem und militärischem Druck, und beide von Leuten, die wussten, dass sie ein Graphenproblem lösten. 1959 veröffentlichten James Kelley bei Remington Rand und Morgan Walker bei DuPont die Methode des kritischen Pfades, entwickelt, um Stillstand und Wiederanlauf von Chemieanlagen zu planen, bei denen jeder Leerlauftag echtes Geld kostete. Im selben Jahr veröffentlichte das Special Projects Office der US Navy PERT, gebaut für das Polaris-Raketenprogramm, bei dem nicht die Kosten das Problem waren, sondern die schiere Unsicherheit von Arbeit, die noch niemand gemacht hatte. Beide Arbeiten beschreiben Vorgangsnetze, und beide berechnen den längsten Pfad.

Im Folgenden bauen wir ein kleines Projekt ausdrücklich auf, dreizehn Vorgänge mit echten Dauern, und beantworten daran jede Standardfrage der Terminplanung: wie lange, was ist kritisch, was darf sich verschieben, wie sicher ist der Termin, was kostet es, schneller zu werden, und was passiert, wenn nicht genug Personen da sind. Jede Zahl wurde berechnet, und jedes Ergebnis wurde mit einer zweiten Methode nachgerechnet, bevor es aufgeschrieben wurde.

2. Vorgänge, Abhängigkeiten und die vier Beziehungstypen

Es gibt zwei Konventionen, ein Projekt als Graph zu zeichnen, und es lohnt sich, beide zu kennen, weil die ältere noch in Lehrbüchern auftaucht.

Beim Vorgangsknotennetz (Activity-on-Node, AoN) ist jeder Vorgang ein Knoten und jeder Pfeil eine Abhängigkeit. So arbeitet moderne Software, und so arbeitet dieser Artikel durchgehend. Beim Vorgangspfeilnetz (Activity-on-Arrow, AoA) ist jeder Vorgang ein Pfeil, und die Knoten sind Ereignisse, also die Zeitpunkte, zu denen eine Menge von Vorgängen abgeschlossen ist. AoA war die ursprüngliche Konvention von PERT und CPM und hat einen echten Nachteil: Bestimmte Abhängigkeitsmuster lassen sich nur ausdrücken, indem man Scheinvorgänge der Dauer null einfügt, die nur existieren, damit die Logik stimmt. AoN braucht keine Scheinvorgänge, und das ist ein Grund, warum es AoA in der Praxis verdrängt hat.

Die Abhängigkeit selbst ist nicht immer die einfache. Vier Beziehungstypen sind Standard:

• Ende-Anfang (FS): B kann erst beginnen, wenn A endet. Der Standardfall und der einzige Typ in diesem Artikel.
• Anfang-Anfang (SS): B kann erst beginnen, wenn A begonnen hat. Nützlich für begleitende Arbeit, etwa Dokumentation, die der Entwicklung ein paar Tage hinterherläuft.
• Ende-Ende (FF): B kann erst enden, wenn A endet.
• Anfang-Ende (SF): B kann erst enden, wenn A begonnen hat. Selten, und meist ein Zeichen, dass der Plan eigentlich etwas anderes meint.

Beziehungen können außerdem einen Zeitabstand (Lag) tragen, also eine Verzögerung auf der Bedingung: Beton muss drei Tage aushärten, bevor darauf gebaut wird, also trägt die Kante einen Zeitabstand von drei, obwohl niemand arbeitet. Zeitabstände sind Kantengewichte, und alles in diesem Artikel funktioniert mit ihnen unverändert. Ein negativer Zeitabstand, Vorlauf genannt, lässt einen Vorgang beginnen, bevor sein Vorgänger endet. Das ist zulässig, und es ist auch ein verbreiteter Weg, einen Plan zu bauen, der sich tatsächlich nicht ausführen lässt.

Eine Regel ist wichtiger als all das: Der Graph muss azyklisch sein. Wenn A auf B wartet und B auf A, gibt es keine Reihenfolge, und Abschnitt 4 zeigt genau, wie das aussieht, wenn ein Planungswerkzeug darauf stößt.

3. Das Projekt, das diesen Artikel begleitet

Das Beispiel ist die Markteinführung einer mobilen App: dreizehn Vorgänge, sechzehn Abhängigkeiten, Dauern in Arbeitstagen. Es ist klein genug, um es von Hand zu prüfen, und strukturiert genug, um alles Wichtige zu zeigen, insbesondere mehrere Pfade fast gleicher Länge, denn dort passiert das meiste Interessante.

Lesen Sie die Struktur, nicht die Beschriftungen. Die Anforderungen (A) eröffnen drei parallele Stränge: die Produktentwicklung über das Datenbankschema (C), die Designarbeit (B) und die Marketingarbeit (G). Der Entwicklungsstrang teilt sich nach der Backend-API (D) erneut in Frontend (E), Zahlungen (F) und Sicherheitsprüfung (I) und läuft dann zweimal zusammen, zuerst beim Integrationstest (H) und dann beim Betaprogramm (J). Das Marketing stößt erst bei der Einreichung (L) wieder dazu.

An diesen Zusammenführungen ballt sich die Schwierigkeit. Ein Vorgang mit mehreren Vorgängern wartet auf den langsamsten, und wer der langsamste ist, steht bei unsicheren Dauern nicht im Voraus fest. Die Abschnitte 9 und 11 handeln im Kern beide davon, was an einer Zusammenführung passiert.

4. Ist der Plan überhaupt ausführbar?

Bevor Sie fragen, wie lange ein Projekt dauert, fragen Sie, ob es sich überhaupt durchführen lässt. Ein Vorgangsnetz beschreibt nur dann einen gültigen Plan, wenn es ein gerichteter azyklischer Graph ist. Enthalten die Abhängigkeiten einen Zyklus, gibt es keine Reihenfolge, in der die Arbeit erledigt werden kann, und der Plan ist nicht verspätet, sondern unmöglich.

Der Test ist eine topologische Sortierung, und Kahns Algorithmus ist die Variante, die man kennen sollte, weil sein Scheitern so aufschlussreich ist. Nehmen Sie wiederholt irgendeinen Vorgang ohne unerledigte Vorgänger, geben Sie ihn aus und entfernen Sie ihn. Für dieses Projekt ergibt das die Reihenfolge A, B, C, D, E, F, G, H, I, J, K, L, M, alle dreizehn Vorgänge, also ist der Plan ausführbar.

Nehmen wir nun an, jemand fügt eine einzige, vernünftig klingende Abhängigkeit hinzu: Das Datenbankschema (C) soll erst festgelegt werden, wenn der Integrationstest (H) die echten Abfragemuster gezeigt hat. Fügen Sie die Kante von H nach C hinzu und rechnen Sie neu. Kahns Algorithmus gibt vier Vorgänge aus und bleibt dann stehen: A, B, G und K, die einzige Arbeit, die nicht in der Schleife steckt. Die übrigen neun sind blockiert, jeder wartet auf einen anderen. Der Algorithmus scheitert nicht einfach, die Menge, die er nicht ausgeben konnte, ist die Verklemmung, und genau das ist die Diagnose, die ein Planer braucht.

Das zählt in der Praxis, weil echte Pläne von vielen Leuten zusammengesetzt werden, von denen jeder lokal sinnvolle Bedingungen hinzufügt, und niemand den ganzen Graphen im Kopf hat. Zirkuläre Abhängigkeiten sind häufig, und der Graph findet sie in linearer Zeit.

Die topologische Ordnung leistet mehr, als den Plan zu prüfen. Weil sie garantiert, dass jeder Vorgänger vor seinen Nachfolgern steht, lässt sich der ganze Zeitplan in einem einzigen Durchlauf über die Vorgänge berechnen, ohne Iteration und ohne Suche. Deshalb war die Methode des kritischen Pfades schon auf der Hardware von 1959 praktikabel, und deshalb ist sie bei Projekten mit hunderttausend Aufgaben weiterhin sofort fertig.

5. Der kritische Pfad: zwei Durchläufe über den Graphen

Die Methode des kritischen Pfades berechnet vier Zahlen für jeden Vorgang und leitet alles andere daraus ab.

Die Vorwärtsrechnung geht die Vorgänge in topologischer Reihenfolge durch und berechnet, wie früh jeder stattfinden kann. Der früheste Anfang eines Vorgangs ist das späteste der frühesten Enden seiner Vorgänger, und sein frühestes Ende ist dieser Wert plus seine Dauer. Die Anforderungen beginnen an Tag 0 und enden an Tag 4. Das Datenbankschema beginnt dann an Tag 4 und endet an Tag 7. Die Backend-API beginnt an Tag 7 und endet an Tag 16. Die Frontend-Entwicklung wartet sowohl auf die API (Ende an Tag 16) als auch auf das UI-Design (Ende an Tag 14), beginnt also an Tag 16, nicht 14. Nach einem Durchlauf ist das größte früheste Ende die Projektdauer: 39 Arbeitstage.

Die Rückwärtsrechnung geht dieselbe Reihenfolge rückwärts und berechnet, wie spät jeder Vorgang stattfinden kann, ohne den Endtermin zu verschieben. Das späteste Ende eines Vorgangs ist der früheste der spätesten Anfänge seiner Nachfolger. Der Launch muss an Tag 39 enden, also an Tag 38 beginnen; die Einreichung muss bis Tag 38 enden, beginnt also an Tag 36; und so weiter zurück bis zum Anfang.

Die Lücke zwischen beiden ist der Gesamtpuffer, also wie weit sich ein Vorgang verschieben darf, bevor sich das Projektende bewegt. Die Vorgänge ohne Puffer bilden den kritischen Pfad.

Der kritische Pfad ist A → C → D → E → H → J → L → M, und seine Länge sind genau die 39 Tage, die die Vorwärtsrechnung ergeben hat. Das ist kein Zufall, sondern ein Satz: Die Projektdauer ist gleich der Länge des längsten Pfades, und die Vorgänge ohne Puffer sind genau die, die auf einem längsten Pfad liegen. Wenn zwei Pfade gleich lang und am längsten sind, wie in Abschnitt 10, sind beide kritisch.

Zwei Folgerungen sollte man klar aussprechen. Erstens: Verzögert sich ein kritischer Vorgang um einen Tag, verzögert sich das Projekt um einen Tag, ohne Ausnahme und ohne Abfederung. Zweitens: Einen unkritischen Vorgang zu beschleunigen, bewirkt gar nichts für den Endtermin. Die Marketing-Website könnte an einem einzigen Tag fertig sein, und der Launch läge trotzdem auf Tag 39. Aufwand abseits des kritischen Pfades kauft Sicherheitsspielraum, keine Zeit.

Sie können diese beiden Durchläufe Schritt für Schritt an einem selbst gezeichneten Netz im Visualisierer für die Methode des kritischen Pfades ausführen. Es lohnt sich zu sehen, was CPM mathematisch ist. Einen längsten Pfad zu finden, ist in einem allgemeinen Graphen NP-schwer, denn damit ließe sich das Hamiltonpfad-Problem lösen. Auf einem gerichteten azyklischen Graphen wird es einfach, linear in der Zahl der Vorgänge und Abhängigkeiten, gerade weil eine topologische Ordnung existiert. Der gesamte praktische Wert von CPM beruht auf der Azyklizität, die Abschnitt 4 geprüft hat.

6. Puffer, und wem er wirklich gehört

Der Puffer ist die nützlichste Zahl in einem Zeitplan und die am beständigsten falsch verwendete. Die Verwirrung rührt daher, dass es zwei Arten davon gibt.

Gesamtpuffer ist, wie weit sich ein Vorgang verzögern darf, ohne den Projektendtermin zu verschieben. Freier Puffer ist, wie weit er sich verzögern darf, ohne den frühesten Anfang eines seiner Nachfolger zu verschieben. In diesem Projekt hat die Sicherheitsprüfung (I) 7 Tage Gesamtpuffer und 7 Tage freien Puffer, weil das Betaprogramm, das sie speist, ohnehin auf den Integrationstest wartet. Die Inhalte (G) haben 22 Tage Gesamtpuffer, aber keinen freien Puffer: Verzögern Sie sie auch nur um einen Tag, beginnt die Marketing-Website einen Tag später.

Genau dieser Unterschied ist die Falle. Die Inhalte und die Marketing-Website zeigen je 22 Tage Gesamtpuffer, und ein Projektleiter, der den Zeitplan Zeile für Zeile liest, sieht 44 Tage scheinbaren Spielraum. Es sind 22. Der Puffer gehört dem Pfad A → G → K → L → M, der in einem 39-Tage-Projekt 17 Tage lang ist, und die beiden Vorgänge teilen ihn sich.

Das Modell macht das greifbar. Verbrauchen Sie die gesamten 22 Tage bei den Inhalten, endet das Projekt immer noch an Tag 39, aber der Gesamtpuffer der Marketing-Website fällt von 22 auf null: Sie ist kritisch geworden. Verzögern Sie sie um einen weiteren Tag, rückt das Projekt auf Tag 40. Nichts wurde überschritten, bei keiner einzelnen Aufgabe ging etwas schief, und doch verschob sich der Termin, weil der Spielraum weiter vorne schon verbraucht war.

Die praktische Regel lautet: Der Gesamtpuffer ist eine Eigenschaft eines Pfades, der freie Puffer eine Eigenschaft eines Vorgangs. Der freie Puffer ist der Teil, den sonst niemand beanspruchen kann, und er ist die Zahl, die Sie einem Team als echten Spielraum nennen sollten. In diesem Projekt haben nur vier Vorgänge überhaupt welchen: B mit 2 Tagen, F mit 1, I mit 7 und K mit 22.

7. Der kritische Pfad ist nicht immer kritisch

Der kritische Pfad lädt zu einem bequemen Schluss ein: Behalten Sie diese acht Vorgänge im Blick, dann ist das Projekt unter Kontrolle. Die Pfadstruktur dieses Projekts zeigt, warum das nicht genügt.

Es gibt fünf Pfade. Der kritische ist 39 Tage lang. Der nächste ist 38 Tage lang, über die Zahlungen statt über das Frontend. Der dritte ist 37 Tage lang, über das UI-Design statt über Datenbank und API. Diese beiden sind nicht kritisch, aber ihr Puffer beträgt einen und zwei Tage, weniger als der Rundungsfehler der meisten Schätzungen.

Praktiker sprechen hier vom beinahe kritischen Pfad als Problem, und es hat eine harte Folge: Ein Plan kann mehrere Pfade haben, die alle praktisch kritisch sind, und ein Projektleiter, der nur den offiziellen beobachtet, wird von einer Verzögerung auf einem scheinbar sicheren Pfad überrascht. Zwei Tage Puffer bei einer zehntägigen Designaufgabe sind kein Spielraum, sondern Rauschen.

Die nützliche Disziplin ist, Pfade nach Puffer zu ordnen, statt sie in kritisch und unkritisch aufzuteilen. In diesem Projekt sagt die Rangfolge 39, 38, 37, 32, 17 etwas, das eine rote Markierung nicht sagen kann: Drei der fünf Pfade brauchen aktive Steuerung, zwei nicht. Abschnitt 9 beziffert genau, wie oft jeder von ihnen am Ende den Termin bestimmt.

8. PERT: eine Wahrscheinlichkeit für den Termin

CPM nimmt an, dass jede Dauer bekannt ist. Niemandes Dauern sind bekannt. PERT, 1959 für das Polaris-Programm entwickelt, begegnet dem, indem es pro Vorgang drei Schätzungen statt einer verlangt: eine optimistische Zeit a, eine wahrscheinlichste Zeit m und eine pessimistische Zeit b.

Daraus berechnet es für jeden Vorgang eine erwartete Dauer und eine Varianz:

t_e = (a + 4m + b) / 6   und   σ² = ((b − a) / 6)²

Die Gewichte stammen daher, dass die Dauer jedes Vorgangs durch eine Betaverteilung angenähert wird. Sie ist flexibel genug, um schief zu sein, und an beiden Enden beschränkt, anders als eine Normalverteilung, die negative Dauern zuließe. Die Formeln sind Näherungen, und sie wurden teils deshalb gewählt, weil man sie 1959 von Hand berechnen konnte.

Die Summe entlang des kritischen Pfades ergibt eine erwartete Projektdauer von 39 Tagen mit einer Gesamtvarianz von 3,778, also einer Standardabweichung von 1,944 Tagen. Dann wird der zentrale Grenzwertsatz bemüht: Eine Summe mehrerer unabhängiger Vorgangsdauern ist annähernd normalverteilt, auch wenn die einzelnen Vorgänge es nicht sind, und so lassen sich Wahrscheinlichkeiten direkt an der Kurve ablesen.

Das Ergebnis ist weit nützlicher als ein Datum. Innerhalb von 40 Tagen fertig zu werden, hat die Wahrscheinlichkeit 69,7 %; innerhalb von 41 Tagen 84,8 %; innerhalb von 42 Tagen 93,9 %. Umgekehrt gesagt: Sich auf 39 Tage festzulegen heißt, sich auf einen Münzwurf festzulegen. Drei Tage Reserve heben die Sicherheit auf etwa 94 %, ein vierter Tag auf 98 %.

Der PERT-Visualisierer führt diese Rechnung interaktiv aus, einschließlich der Fertigstellungswahrscheinlichkeit für jeden Zieltermin. Diese neue Perspektive ist der eigentliche Beitrag von PERT. Ein Zeitplan, der ein einzelnes Datum liefert, lädt zur Frage „Schaffen wir das?“ ein, auf die es keine ehrliche Antwort gibt. Ein Zeitplan, der eine Verteilung liefert, lädt zur Frage „Wie viel Sicherheit wollen Sie, und was darf sie kosten?“ ein, und darauf gibt es eine.

9. Der Merge-Bias: warum PERT zu optimistisch ist

PERT hat einen Fehler. Er wurde wenige Jahre nach der Veröffentlichung erkannt und wird bis heute routinemäßig ignoriert. Das Problem ist, dass PERT die Verteilung des kritischen Pfades berechnet und sie dann als Verteilung des Projekts behandelt. Das ist nicht dasselbe.

Das Projekt wartet nicht auf den kritischen Pfad. Es wartet auf den Pfad, der sich am Ende als längster herausstellt. Laufen mehrere Pfade in einem Vorgang zusammen, beginnt dieser Vorgang, wenn der langsamste von ihnen eintrifft, und der Erwartungswert eines Maximums ist größer als das Maximum der Erwartungswerte. Das ist die Jensensche Ungleichung, und in der Projektplanung heißt sie Merge-Bias. Van Slyke wies ihn 1963 mit Monte-Carlo-Simulation nach, und MacCrimmon und Ryavec analysierten 1964 die Größe des Fehlers.

Um ihn zu messen, wurde jeder Vorgang dieses Projekts 200.000-mal aus der Betaverteilung gezogen, deren Mittelwert genau seiner erwarteten PERT-Dauer entspricht. Jeder Unterschied im Ergebnis ist also allein der Merge-Bias und keine andere Annahme. Die simulierte mittlere Dauer beträgt 39,34 Tage gegenüber den 39,00 von PERT. Nützlicher noch: Die Wahrscheinlichkeit, innerhalb von 39 Tagen fertig zu werden, beträgt 43,8 %, nicht die 50 %, die PERT nahelegt.

Die Pfadstatistik erklärt, woher das kommt. Über alle Simulationen hinweg war der nominelle kritische Pfad nur in 64,0 % der Läufe der längste. Der Pfad über die Zahlungen gewann in 26,1 % der Fälle, der Designpfad in 9,9 %. Jedes dritte Projekt wird aus einem Grund zu spät fertig, den die Analyse des kritischen Pfades nie erwähnt hat.

Ein Drittel Tag Verzerrung klingt vernachlässigbar, und bei diesem Projekt ist es das auch. Im Allgemeinen ist es das nicht, und die Verzerrung wächst genau in den Situationen, die große Programme ausmachen: viele parallele Pfade ähnlicher Länge, viele Zusammenführungen und hohe Varianz. Ein Zeitplan mit zwanzig fast gleich langen Pfaden, die in einem Meilenstein zusammenlaufen, kann um Wochen verzerrt sein.

Daraus folgen zwei praktische Antworten. Erstens: Wenn das Netz nennenswert parallel ist, sollten Sie es simulieren und nicht die Varianz entlang eines Pfades fortpflanzen. Die Rechnung umfasst ein paar Zeilen und dauert Sekunden. Zweitens: Nennen Sie ein Quantil, nicht den Mittelwert. Das P80 für dieses Projekt liegt bei 41,1 Tagen und das P90 bei 42,0. Auf diese Zahlen kann sich ein Team festlegen. Der Mittelwert ist die Zahl, die es in der Hälfte der Fälle verfehlt, und etwas öfter als in der Hälfte, sobald man den Merge-Bias mitzählt.

10. Crashing: Zeit kaufen ist ein minimaler Schnitt

Angenommen, 39 Tage sind zu lang. Viele Vorgänge lassen sich gegen Geld verkürzen: mehr Personal, Überstunden, ein schnellerer Lieferant. In der Terminplanung heißt das Crashing, und jeder Vorgang bekommt zwei zusätzliche Zahlen: um wie viele Tage er höchstens verkürzt werden kann und was ein Tag kostet, seine Kostensteigung.

Der naive Ansatz ist, den billigsten kritischen Vorgang zu verkürzen. Das funktioniert genau einmal. Die Frontend-Entwicklung hat mit 350 $ pro Tag die niedrigste Kostensteigung auf dem kritischen Pfad, also bringt ihre Verkürzung das Projekt für 350 $ von 39 auf 38 Tage. Als Nächstes folgt das Datenbankschema mit 400 $, das auf 37 führt.

Dann versagt die naive Regel. Bei 37 Tagen sind zwei Pfade gleichzeitig kritisch: der ursprüngliche und der Pfad über die Zahlungen, die jetzt beide 37 Tage lang sind. Die Frontend-Entwicklung erneut zu verkürzen, spart nichts, weil die Zahlungen weiter in voller Länge laufen und das Projekt weiter 37 Tage dauert. Um einen Tag zu gewinnen, müssen Sie jeden kritischen Pfad gleichzeitig verkürzen.

Die Struktur ist folgende. Eine Menge von Vorgängen, deren Verkürzung jeden kritischen Pfad verkürzt, ist eine Menge, die jeden Pfad vom Projektanfang bis zum Projektende trifft (im kritischen Teilnetz). Genau das ist die Definition eines s-t-Schnitts. Geben Sie jedem Vorgang eine Kapazität gleich seinen Kosten pro Tag, dann ist der billigste Weg, einen Tag zu kaufen, der minimale Schnitt dieses Netzes. Nach dem Max-Flow-Min-Cut-Theorem lässt er sich in polynomieller Zeit finden, und genau diese Beobachtung veröffentlichten Fulkerson und Kelley beide 1961.

Wenn Ihnen das Flussargument nicht vertraut ist, lohnt es sich, zuerst das Max-Flow-Min-Cut-Theorem zu lesen, denn Crashing ist eine seiner saubersten Anwendungen außerhalb der Netzwerktechnik. Weil Vorgänge Knoten und keine Kanten sind, wird jeder in eine Eingangs- und eine Ausgangskopie geteilt, verbunden durch einen Bogen mit seiner Kostensteigung, während die echten Abhängigkeiten unendliche Kapazität erhalten. Der minimale Schnitt muss dann aus Vorgängen bestehen, und die kann man tatsächlich kaufen.

Angewandt auf das Projekt ergibt das den dritten Schritt: Von 37 auf 36 Tage zu kommen, kostet 650 $ und verlangt, dass Frontend-Entwicklung und Zahlungen gemeinsam verkürzt werden. Keiner der beiden bringt allein einen Tag, also hätte keine Regel der Art „nimm die billigste kritische Aufgabe“ dieses Paar je gefunden. Der Integrationstest funktioniert zwar allein, weil er auf beiden kritischen Pfaden liegt, kostet aber 800 $ gegenüber den 650 $ des Paares.

Bis zur Grenze fortgesetzt, ergibt sich die vollständige Zeit-Kosten-Kurve: 27 Tage sind die kürzeste erreichbare Dauer, bei Gesamtkosten der Beschleunigung von 11.950 $. Die Kurve ist konvex, das heißt, jeder weitere Tag kostet mindestens so viel wie der vorige. Das ist eine allgemeine Eigenschaft dieser Konstruktion und eine nützliche Plausibilitätsprüfung für jede Crashing-Analyse, die man Ihnen vorlegt.

Die Kurve, nicht der Endpunkt, ist das Ergebnis. Sie verwandelt einen Streit darüber, ob das Team „schneller werden“ kann, in eine Preisliste: drei Tage für 1.400 $, sechs Tage für 3.650 $, zwölf Tage für 11.950 $. Ob sich einer davon lohnt, ist eine geschäftliche Frage, aber jetzt ist es eine Frage mit Zahlen darin.

11. Ressourcen: wo die Theorie nicht mehr ausreicht

Alles bisher setzt voraus, dass zwei Vorgänge, die parallel laufen können, das auch tun. Das setzt unbegrenzt viele Personen voraus, und kein Projekt hat unbegrenzt viele Personen. Wer welche Schichten arbeitet, statt welche Aufgaben wann laufen, ist das verwandte Dienstplanproblem, das in der Schichtplanung für Mitarbeitende durchgerechnet wird.

Geben Sie jedem Vorgang einen Personalbedarf und betrachten Sie den CPM-Zeitplan erneut. Beginnt alles so früh wie möglich, erreicht der Bedarf in diesem Projekt einen Höchstwert von sieben Personen von Tag neun bis Tag vierzehn, wenn Backend-API, UI-Design und Marketing-Website gleichzeitig laufen. Hat das Team fünf Personen, ist der Zeitplan eine Fiktion.

Mit Ressourcengrenzen wird aus dem Vorranggraphen das ressourcenbeschränkte Projektplanungsproblem (RCPSP), und der Schwierigkeitssprung ist nicht graduell. CPM läuft in linearer Zeit. RCPSP ist NP-schwer, bewiesen von Blazewicz, Lenstra und Rinnooy Kan 1983, und es ist in der Praxis ebenso schwer wie in der Theorie: Instanzen mit 60 Vorgängen aus der Standard-Benchmarkbibliothek PSPLIB blieben jahrelang ungelöst.

Die Zahlen verdienen einen zweiten Blick. Mit fünf Personen endet das Projekt weiterhin nach 39 Tagen: Die Spitze von sieben war ein Artefakt der Planung, und Arbeit in den Puffer zu verschieben, fängt sie vollständig ab. Mit vier liegt das Optimum bei 49 Tagen, eine Überschreitung um 26 %, die in der Netzanalyse nirgends auftaucht. Beide Zahlen wurden durch erschöpfendes Branch and Bound über alle aktiven Zeitpläne bestätigt, was nur machbar ist, weil das Projekt dreizehn Vorgänge hat.

Mit dem Visualisierer für ressourcenbeschränkte Planung können Sie eine Kapazität festlegen und zusehen, wie sich der Zeitplan dehnt. Weil exakte Lösungen nicht skalieren, arbeitet die Praxis mit Prioritätsregeln: Plane wiederholt den zulässigen Vorgang ein, der nach einer bestimmten Regel am höchsten eingestuft ist. Die Wahl der Regel zählt mehr, als es scheint. Bei Kapazität vier liefert minimaler Gesamtpuffer 49 Tage, was hier zufällig optimal ist, während frühester spätester Start, längste Dauer zuerst und meiste Nachfolger zuerst alle 53 ergeben. Dasselbe Projekt, dieselbe Bedingung, ein Unterschied von 8 % durch eine Modellierungsentscheidung, die die meisten Werkzeuge stillschweigend für Sie treffen.

Der tiefere Punkt ist, dass der kritische Pfad unter Ressourcenbeschränkungen seine Bedeutung verliert. Zwei Vorgänge ohne jede Abhängigkeit können trotzdem nicht gleichzeitig laufen, also kann die Kette, die den Endtermin tatsächlich bestimmt, Paare von Vorgängen enthalten, die nichts verbindet außer einer gemeinsamen Person. Die klassischen Pufferwerte beschreiben nicht mehr, was sich verschieben darf.

12. Kritische Kette, kurz gefasst

Diese Beobachtung ist der Ausgangspunkt des Critical Chain Project Management, das Eliyahu Goldratt 1997 vorstellte. Die kritische Kette ist die längste Folge von Vorgängen, die sowohl Anordnungsbeziehungen als auch Ressourcenkonflikte berücksichtigt, und genau sie muss man beobachten, wenn Personal knapp ist.

Ihre zweite Idee betrifft den Ort, an dem Sicherheitszeit gehalten wird. Einzelschätzungen sind meist gepolstert, und das Polster wird dann ohnehin verbraucht, sei es, weil sich Arbeit auf die verfügbare Zeit ausdehnt, sei es, weil ein bequemer Starttermin ausgeschöpft wird. Die kritische Kette nimmt das Polster aus den einzelnen Vorgängen und bündelt es in ausdrücklichen Puffern: ein Projektpuffer am Ende der Kette und Zuführungspuffer dort, wo unkritische Pfade in sie einmünden. Das Bündeln ist statistisch stichhaltig, wenn auch aus einem anderen Grund als der Merge-Bias: Die Standardabweichung einer Summe unabhängiger Dauern wächst wie die Quadratwurzel ihrer Anzahl, also kann ein gemeinsamer Puffer kleiner sein als die einzelnen Reserven, die er ersetzt, und trotzdem denselben Schutz bieten.

Die Methode ist ernsthaft umstritten. Herroelen und Leus haben unter anderem argumentiert, dass ihre Planungsversprechen schwächer sind als dargestellt und dass Regeln zur Puffergröße wie „die halbe Kettenlänge“ keine analytische Grundlage haben. Die Einsicht zum Bündeln von Puffern ist stichhaltig; der Rahmen darum ist eine Managementmethode und kein Satz, und es lohnt sich, beides auseinanderzuhalten.

13. Was leicht ist und was schwer

Die Projektplanung hat eine ungewöhnlich scharfe Komplexitätsgrenze, und wer weiß, wo sie verläuft, weiß, welche Versprechen ein Werkzeug halten kann.

Leicht, also polynomiell und bei jeder realistischen Größe sofort erledigt. Zyklen erkennen und eine topologische Ordnung erzeugen. Vorwärts- und Rückwärtsrechnung und damit die Projektdauer, der kritische Pfad und jeder Pufferwert. Die relevanten Pfade nach Puffer aufzählen. Der minimale Schnitt für einen Tag Crashing und durch Wiederholung die ganze Zeit-Kosten-Kurve. Monte-Carlo-Simulation der Dauerverteilung. All das ist linear oder fast linear, und ein Projekt mit hunderttausend Vorgängen ist kein Problem.

Schwer, also NP-schwer, ohne dass ein polynomieller Algorithmus zu erwarten ist. Planung unter Ressourcenbeschränkungen in praktisch jeder Variante: feste Kapazität, mehrere Ressourcenarten, mit oder ohne Unterbrechung. Ressourcenglättung, die nach dem gleichmäßigsten Profil statt nach dem kürzesten Zeitplan fragt. Zeit-Kosten-Abwägungen mit diskreten Optionen pro Vorgang statt einer stetigen Steigung, womit die Flussformulierung verloren geht. Alle Pfade aufzählen, deren Zahl mit der Zahl der Vorgänge exponentiell wachsen kann.

Das Muster ist fast eine Faustregel: Nach einem optimalen Zeitplan allein in der Zeit zu fragen, ist leicht, und eine gemeinsam genutzte, begrenzte Ressource macht es schwer. Die beiden Ausnahmen in der schweren Liste bestätigen die Regel, statt sie zu brechen, denn keine fragt nach einem einzelnen Optimum: Die Pfadaufzählung fragt nach allen Antworten, und die diskrete Abwägung verlangt bei jedem Vorgang eine Wahl aus einem Menü. Zeitbedingungen sind eine Halbordnung, und Halbordnungen sind genau das, was gerichtete azyklische Graphen gut beherrschen. Eine gemeinsame Ressource erzeugt Bedingungen zwischen Vorgängen ohne jede Abhängigkeit, und die azyklische Struktur, die alles lösbar machte, beschreibt das Problem nicht mehr.

Deshalb liefert Planungssoftware einen exakten kritischen Pfad und einen näherungsweise ressourcengeglätteten Plan, meist ohne das zu sagen. Das Erste ist ein Satz; das Zweite ist eine Heuristik, deren Qualität niemand angibt. Das ist nur eine Ecke eines viel größeren Feldes: Operations Research umfasst die Optimierungsverfahren, die die schwierigere Hälfte dieser Liste braucht.

14. Modellierungsfehler und wie man sie vermeidet

Fünf Fehler erklären die meisten schlechten Zeitpläne, und keiner davon hat mit schlechtem Schätzen zu tun.

Puffer als eigene Reserve behandeln. Der Gesamtpuffer wird entlang eines Pfades geteilt. Zwei Teams, denen jeweils drei Wochen Spielraum auf demselben Pfad zugesagt wurden, verbrauchen zusammen sechs und wundern sich, wenn sich der Termin bewegt. Nennen Sie den Teams den freien Puffer und behalten Sie den Gesamtpuffer als Planungszahl.

Nur den kritischen Pfad beobachten. Ein Pfad mit zwei Tagen Puffer ist nicht sicher, er ist beinahe kritisch, und in diesem Projekt entscheidet der nominelle kritische Pfad das Ergebnis nur in zwei von drei Läufen. Ordnen Sie Pfade nach Puffer und steuern Sie alles, was wenige Tage von null entfernt ist.

Den Mittelwert als Termin nennen. Die erwartete Dauer ist schon vor dem Merge-Bias ungefähr ein Münzwurf und danach etwas schlechter. Wenn ein Termin in einen Vertrag geht, sollte er ein Quantil sein, und das Quantil sollte genannt werden.

Unabhängigkeit annehmen. Sowohl die Varianzsumme von PERT als auch die Simulation in Abschnitt 9 nehmen unabhängige Vorgangsdauern an. Meist sind sie es nicht: Derselbe optimistische Schätzer hat mehrere davon geliefert, dasselbe Team führt mehrere aus, und ein schlechter Lieferant trifft mehrere auf einmal. Korrelation bläht die Varianz der Summe weit über das hinaus auf, was eine der beiden Methoden ausweist, also behandeln Sie die Streuung als Untergrenze und nicht als Schätzung.

Planen, als wären Personen unbegrenzt. Ein CPM-Termin ohne Ressourcengrenzen ist eine untere Schranke, kein Plan. Prüfen Sie das Ressourcenprofil, bevor Sie den Termin veröffentlichen; in diesem Projekt betrug der Unterschied zwischen Prüfen und Nichtprüfen zehn Tage.

Ein sechster verdient Erwähnung, weil er unsichtbar ist: eine Abhängigkeit, die nicht echt ist. Pläne sammeln Bedingungen an, die aus Bequemlichkeit hinzugefügt wurden, Reihenfolgen, die widerspiegeln, wie das Team zufällig organisiert ist, statt etwas Technisches. Eine zusätzliche Kante kann den längsten Pfad nur verlängern oder unverändert lassen, nie verkürzen, also ist jede unnötige Abhängigkeit eine einseitige Wette gegen den Zeitplan. Den kritischen Pfad Kante für Kante zu prüfen und bei jeder zu fragen, ob sie eine echte Bedingung ist, ist oft die billigste verfügbare Verkürzung, und anders als Crashing kostet sie nichts.

16. Quellen

Die Arbeiten hinter den Methoden in diesem Artikel, in chronologischer Reihenfolge.

1. Clark, W. (1922). The Gantt Chart: A Working Tool of Management. Ronald Press.
2. Kelley, J. E. und Walker, M. R. (1959). “Critical-path planning and scheduling.” Proceedings of the Eastern Joint Computer Conference, 160–173.
3. Malcolm, D. G., Roseboom, J. H., Clark, C. E. und Fazar, W. (1959). “Application of a technique for research and development program evaluation.” Operations Research, 7(5), 646–669.
4. Fulkerson, D. R. (1961). “A network flow computation for project cost curves.” Management Science, 7(2), 167–178.
5. Kelley, J. E. (1961). “Critical-path planning and scheduling: mathematical basis.” Operations Research, 9(3), 296–320.
6. Ford, L. R. und Fulkerson, D. R. (1962). Flows in Networks. Princeton University Press.
7. Van Slyke, R. M. (1963). “Monte Carlo methods and the PERT problem.” Operations Research, 11(5), 839–860.
8. MacCrimmon, K. R. und Ryavec, C. A. (1964). “An analytical study of the PERT assumptions.” Operations Research, 12(1), 16–37.
9. Klingel, A. R. (1966). “Bias in PERT project completion time calculations for a real network.” Management Science, 13(4), B194–B201.
10. Wiest, J. D. (1967). “A heuristic model for scheduling large projects with limited resources.” Management Science, 13(6), B359–B377.
11. Elmaghraby, S. E. (1977). Activity Networks: Project Planning and Control by Network Models. Wiley.
12. Blazewicz, J., Lenstra, J. K. und Rinnooy Kan, A. H. G. (1983). “Scheduling subject to resource constraints: classification and complexity.” Discrete Applied Mathematics, 5(1), 11–24.
13. Kolisch, R. und Sprecher, A. (1997). “PSPLIB: a project scheduling problem library.” European Journal of Operational Research, 96(1), 205–216.
14. Goldratt, E. M. (1997). Critical Chain. North River Press.
15. Brucker, P., Drexl, A., Möhring, R., Neumann, K. und Pesch, E. (1999). “Resource-constrained project scheduling: notation, classification, models, and methods.” European Journal of Operational Research, 112(1), 3–41.
16. Herroelen, W. und Leus, R. (2001). “On the merits and pitfalls of critical chain scheduling.” Journal of Operations Management, 19(5), 559–577.
17. Demeulemeester, E. und Herroelen, W. (2002). Project Scheduling: A Research Handbook. Kluwer Academic Publishers.
18. Herroelen, W. und Leus, R. (2005). “Project scheduling under uncertainty: survey and research potentials.” European Journal of Operational Research, 165(2), 289–306.
19. Kolisch, R. und Hartmann, S. (2006). “Experimental investigation of heuristics for resource-constrained project scheduling: an update.” European Journal of Operational Research, 174(1), 23–37.
20. Hartmann, S. und Briskorn, D. (2010). “A survey of variants and extensions of the resource-constrained project scheduling problem.” European Journal of Operational Research, 207(1), 1–14.
21. Trietsch, D. und Baker, K. R. (2012). “PERT 21: fitting PERT/CPM for use in the 21st century.” International Journal of Project Management, 30(4), 490–502.