RCPSP Löser

Pseudocode

RCPSP ist CPM plus begrenzte Ressourcen, und dieser eine Zusatz hebt es von linear auf NP-schwer. Der praktische Ansatz ist eine serielle Planungsheuristik, gesteuert von einer Prioritätsregel.

RCPSP(vorgänge, abhängigkeiten, kapazitäten):
    ordnung = topologischeSortierung(vorgänge)
    ordnung nach einer Prioritätsregel sortieren
    // z. B. geringster Puffer oder längste Dauer zuerst

    für jeden Vorgang a in der priorisierten Ordnung:
        t = max(ende[p] für p Vorgänger von a)
        solange eine Ressource r in
              [t, t + dauer[a]) ausgelastet ist:
            t = t + 1        // verschieben, bis es passt
        start[a] = t; ende[a] = t + dauer[a]
        Ressourcen von a für dieses Intervall belegen

    Projektdauer = max(ende[a])

Der Unterschied zu CPM ist, dass der Start eines Vorgangs nicht mehr allein von seinen Vorgängern bestimmt wird: er kann nach hinten rutschen, weil ein völlig unabhängiger Vorgang gerade die Maschine belegt. Das zerstört genau jene Eigenschaft, die CPM linear machte, denn die Entscheidung über einen Vorgang wirkt nun auf Vorgänge, zu denen keinerlei Abhängigkeit besteht. Deshalb reicht keine noch so ausgefeilte dynamische Programmierung über die topologische Ordnung.

Durchgerechnetes Beispiel, Schritt für Schritt

Plane vier Vorgänge, die um eine einzige Ressource mit Kapazität 1 konkurrieren, und vergleiche das Ergebnis mit der CPM-Vorhersage.

Beispielgraph: Vorgänge A (3 Tage), B (2 Tage), C (4 Tage) und D (2 Tage), wobei A und B C vorausgehen und C D vorausgeht. Alle benötigen dieselbe Maschine, von der nur eine Einheit existiert.

1. Was CPM sagen würde. Ohne Ressourcengrenze laufen A und B ab Zeitpunkt 0 parallel, C beginnt bei 3 und D endet bei 9. Projektdauer: 9 Tage.
2. Die Ressourcengrenze anwenden. A und B brauchen beide die Maschine, und es gibt nur eine. Sie können sich nicht mehr überlappen, einer muss also warten. Die Priorisierung entscheidet, welcher.
3. Prioritätsregel: längste Dauer zuerst. A dauert 3 und B dauert 2, also kommt A zuerst und belegt die Maschine von 0 bis 3. B muss warten und läuft von 3 bis 5.
4. C einplanen. C setzt voraus, dass A und B fertig sind, also Zeitpunkt 5, und die Maschine ist dann frei. C läuft von 5 bis 9.
5. D einplanen. D folgt auf C und läuft von 9 bis 11. Die Projektdauer beträgt 11 Tage.

Mit unbegrenzten Ressourcen dauert das Projekt 9 Tage, mit einer einzigen Maschine 11. Die beiden Zusatztage stammen aus keiner Abhängigkeit, sondern rein aus der Ressourcenkonkurrenz. Beachte außerdem, dass der Begriff des kritischen Pfades hier schlüpfrig wird: die den Endtermin bestimmende Kette enthält nun Bs Warten auf die Maschine, was gar keine Vorgängerbeziehung ist. Deshalb fallen CPM-Terminpläne bei knappen Ressourcen systematisch zu optimistisch aus.

Komplexität und woher sie kommt

Zeit: NP-schwer; serielle Heuristik O(V^2 · R) · Speicher: O(V · R)

Die serielle Planungsheuristik verarbeitet jeden der V Vorgänge einmal und muss für jeden gegebenenfalls den Startzeitpunkt vorschieben, wobei die Verfügbarkeit der R Ressourcen geprüft wird, was bei direkter Implementierung im schlechtesten Fall in der Größenordnung O(V hoch 2 mal R) liegt. Das ist schnell und skaliert auf Tausende Vorgänge. Was es nicht leistet, ist eine Optimalitätsgarantie. Exaktes RCPSP ist NP-schwer und gilt als eines der härtesten Planungsprobleme des Operations Research: Benchmarkinstanzen mit nur 60 Vorgängen blieben jahrelang ungelöst. Exaktes Branch and Bound ist je nach Struktur bis etwa 30 bis 60 Vorgänge machbar, darüber hinaus greift man zu Metaheuristiken wie genetischen Algorithmen oder Tabu-Suche.

Wann RCPSP (Ressourcenbeschränkte Projektplanung) passt und wann nicht

Wähle danach, ob Ressourcen tatsächlich beschränkend wirken und ob du eine Optimalitätsgarantie brauchst.

Häufige Fehler

• Mit CPM planen und Ressourcen nachträglich ergänzen. Ein CPM-Terminplan unterstellt unbegrenzte Parallelität. Ressourcengrenzen im Nachhinein einzupassen verlängert das Projekt fast immer, wie im Beispiel, in dem aus 9 Tagen 11 werden. Ressourcen gehören von Anfang an ins Modell und nicht als nachträgliche Korrektur.
• Annehmen, der kritische Pfad bedeute weiterhin dasselbe. Bei begrenzten Ressourcen kann die den Endtermin bestimmende Folge Wartezeiten aus Konkurrenz enthalten, die keine Vorgängerbeziehungen sind. Das passende Gegenstück ist die Critical Chain, die sowohl Abhängigkeiten als auch Ressourcenkonflikte einbezieht.
• Eine einzige Prioritätsregel verwenden und es dabei belassen. Verschiedene Regeln, etwa geringster Puffer, längste Dauer zuerst oder meiste Nachfolger, erzeugen verschiedene Terminpläne, und keine dominiert die anderen. Lasse mehrere laufen und behalte den besten; das ist billig und verbessert das Ergebnis meist spürbar.
• Vergessen, dass Ressourcen nicht erneuerbar sein können. Erneuerbare Ressourcen wie Maschinen oder Personen werden am Vorgangsende wieder frei. Nicht erneuerbare wie Budget oder Material werden dauerhaft verbraucht. Letztere wie Erstere zu modellieren erzeugt Terminpläne, die das Budget mehrfach ausgeben.
• Erwarten, dass große Instanzen exakt lösbar sind. RCPSP zählt zu den klassischen harten Problemen. Benchmarkinstanzen mit 60 Vorgängen widerstanden exakten Verfahren jahrelang. Hat dein Projekt Hunderte Aufgaben, plane mit Heuristiken und validiere per Simulation, statt dem Optimum nachzujagen.

Häufig gestellte Fragen

Was ist RCPSP?

Das ressourcenbeschränkte Projektplanungsproblem sucht einen Terminplan, der sowohl die Vorgängerbeziehungen zwischen Vorgängen als auch die begrenzte Verfügbarkeit erneuerbarer Ressourcen einhält und dabei üblicherweise die Projektdauer minimiert. Es ist CPM ohne die Annahme unbegrenzter Ressourcen.

Warum ist RCPSP NP-schwer, wo CPM doch linear ist?

Weil Ressourcengrenzen Vorgänge koppeln, zwischen denen keinerlei Abhängigkeit besteht. Bei CPM hängt der Start eines Vorgangs nur von seinen Vorgängern ab, was zwei Durchläufe in topologischer Ordnung genügen lässt. Mit Ressourcen kann das Verschieben eines Vorgangs einen völlig unbeteiligten Vorgang mitverschieben, und diese globale Wechselwirkung lässt den Suchraum explodieren.

Was ist der Unterschied zwischen CPM und RCPSP?

CPM nimmt an, dass beliebige Vorgänge ohne wechselseitige Abhängigkeit gleichzeitig laufen können. RCPSP fügt Ressourcenkapazitäten hinzu, die diese Parallelität verhindern. Im obigen Beispiel dauert dasselbe Projekt unter CPM 9 Tage und unter RCPSP mit einer Maschine 11, und die zwei Tage Differenz sind reine Ressourcenkonkurrenz.

Was ist eine Prioritätsregel im RCPSP?

Sie ist die Heuristik, die entscheidet, welcher Vorgang zuerst eingeplant wird, wenn mehrere bereit sind und um dieselbe Ressource konkurrieren. Übliche Regeln sind geringster Puffer, längste Dauer zuerst, meiste Nachfolger oder frühester spätester Endtermin. Keine ist immer die beste, in der Praxis lässt man daher mehrere laufen und behält den besten Terminplan.

Wofür wird RCPSP verwendet?

Für die Planung von Fertigungslinien mit begrenzten Maschinen, die Zuteilung von Kolonnen und Geräten im Bauwesen, die Planung von Projektportfolios, die sich Spezialpersonal teilen, und allgemein für jede Planung, in der Aufgaben um endliche Kapazität konkurrieren, statt frei parallel laufen zu können.