RCPSP (Ressourcenbeschränkte Projektplanung)

Das ressourcenbeschränkte Projektplanungsproblem (RCPSP) plant Projektvorgänge unter Beachtung sowohl von Vorrangbeziehungen als auch begrenzter erneuerbarer Ressourcen wie Arbeitskräften, Maschinen oder Budget je Periode. Anders als CPM, das unbegrenzte Ressourcen annimmt, ist RCPSP stark NP-schwer.

Funktionsweise

Prioritätsregel-Heuristiken bauen Pläne mit dem seriellen oder parallelen Plangenerierungsschema: Vorgänge werden zum frühesten Zeitpunkt eingefügt, an dem sowohl Vorrang als auch Ressourcenverfügbarkeit gelten, geordnet nach Regeln wie meiste Gesamtnachfolger oder minimaler Puffer. Exakte Ansätze nutzen Branch and Bound mit ressourcenbasierten unteren Schranken, und Metaheuristiken, besonders genetische Algorithmen mit Aktivitätslisten-Kodierung, dominieren die PSPLIB-Benchmarks.

Anwendungen

RCPSP steuert die Einsatzplanung von Baukolonnen und Geräten, die Sprintplanung von Softwareteams unter Personalgrenzen, die Terminierung von Wartungsstillständen in Raffinerien und die Produktionsplanung in der Auftragsfertigung. Es ist die klassische Brücke zwischen Graphalgorithmen und industriellem Operations Research.