Kapazitätsorientierte Terminplanung (RCPSP)

Kapazitätsorientierte Terminplanung (RCPSP) II

Es wird das "Resource-Constrained Project Scheduling Problem " (RCPSP mit erneuerbaren Ressourcen und einem Modus) mit Hilfe eines heuristischen Prioritätsregelverfahrens gelöst. Als Zielsetzung wird die Minimierung der Zykluszeit angestrebt. In dieser einfachen Variante wird angenommen, daß ein Vorgang mehrere Ressourcen gleichzeitig belegen kann.

Mindest- oder Maximalabstände zwischen den Vorgänge werden nicht berücksichtigt.

Es wird das parallele Einplanungsverfahren eingesetzt.

Das Verfahren geht im Prinzip in der Weise vor, daß beginnend mit dem Einplanungszeitpunkt t=0 alle einplanbaren Vorgänge frühestmöglich auf den Ressourcen eingeplant werden.

Ein Vorgang ist im Einplanungszeitpunkt t einplanbar , wenn

alle seine Vorgänger im Netzplan beendet sind und
wenn genügend Kapazität der Ressourcen verfügbar ist.

Nachdem alle in t einplanbaren Vorgänge eingeplant worden sind, wird der Einplanungszeitpunkt t erhöht und mit den dann einplanbaren Vorgängen fortgefahren. Die Menge der einplanbaren Vorgänge wird jeweils dynamisch aktualisiert. Bei der Auswahl des nächsten einzuplanenden Vorgangs aus der Menge der in t einplanbaren Vorgänge wird auf Prioritätsregeln zurückgegriffen. Es sind folgende Prioritätsregeln implementiert:

Kürzeste-Operationszeit-Regel (KOZ)
Anzahl direkter Nachfolger im Netzplan
Gesamtpufferzeit (GP)
Kapazitätsbedarf
Positionswert (RPW)
Gesamtanzahl aller Nachfolger im Netzplan

Das Verfahren führt erst eine Durchlaufterminierung (ohne Beachtung) der Kapazitäten durch. Falls nicht die exakte Lösung mit AMPL gesucht wird, kann die Abfrage des maximalen Endtermins einfach bestätigt werden. Dann kann die Heuristik gestartet werden.

Online-Optimierung mit dem Neos-Server und Gurobi

Man kann für jedes Problem auch die optimale Lösung bestimmen lassen, indem man die AMPL-Schnittstelle des online verfügbaren Neos-Servers nutzt.

Da das Optimierungsmodell (siehe Günther/Tempelmeier (2016), Abschnitt 11.1.4) mit frühestmöglichen und unter Berücksichtigung der Kapazitäten spätestzulässigen Terminen SEZ arbeitet, wird zu diesem Zweck ein Schätzwert für den maximalen Endtermin des Projekts abgefragt. Wird dieser zu niedrig gesetzt, dann findet das Optimierungsmodell keine zulässige Lösung. Wird er zu hoch angesetzt, dann werden u.U. zu viele Binärvariablen erzeugt und die Studentenversion von AMPL kann nicht verwendet werden.

Im Produktions-Management-Trainer wählt man unter Optionen -> AMPL-Datei (Neos) erzeugen. Es erscheint dann ein Dateiauswahlfenster, in dem man den Namen der zu erzeugenden AMPL-Dateien festlegt. Hat man z.B. "SPLP" angegeben, dann werden die AMPL-Dateien RCPSP.MOD, RCPSP.DAT und RCPSP.RUN erzeugt. Als nächstes öffnet man die folgende Internet-Seite in einem Browser:

https://neos-server.org/neos/solvers/milp:Gurobi/AMPL.html

Auf dieser Seite sind in der "Web Submission Form" die Modelldatei (RCPSP.MOD), die Datendatei (RCPSP.DAT) und die Kommandodatei (RCPSP.RUN) anzugeben. Dann betätigt man den Button "Submit to Neos" und nach einiger Zeit wird die optimale Lösung des Problems angezeigt.

Optimierung auf dem PC mit der Studentenversion von AMPL und CPLEX

Unter https://ampl.com/try-ampl/download-a-free-demo/#windows kann man die Studentenversion von AMPL herunterladen: entweder ampl.mswin32.zip oder ampl.mswin64.zip.

In dieser ZIP-Datei befindet sich ein Unterverzeichnis, das auf den PC kopiert werden muß. Im Produktions-Management-Trainer wählt man die Option AMPL-Datei (lokal) erzeugen. Es erscheint ein Dateiauswahldialog, in dem man das AMPL-Verzeichnis angeben sollte. In diesem Verzeichnis startet man dann die Datei "ampl.exe" und gibt man den Befehl "include splp.run;" ein. Dieser Befehl startet die Lösung des Problems. Die Ergebnisse werden in der Datei RCPSP.AUS gespeichert.

Eine formale Beschreibung des Verfahrens findet sich in Drexl/Kolisch/Sprecher (1997), S. 120 (Paralleles Prioritätsregelverfahren).

Folgende Symbole werden auch bei der Durchlaufterminierung verwendet:

i	Arbeitsgangindex
AG-i	Arbeitsgang i
D(i)	Ausführungsdauer von AG-i
FAZ(i)	frühestmöglicher Anfangszeitpunkt für AG-i
FEZ(i)	frühestmöglicher Endzeitpunkt für AG-i (Endzeitpunkt = Zeitpunkt der Fertigstellung)
SAZ(i)	spätestzulässiger Anfangszeitpunkt für AG-i
SEZ(i)	spätestzulässiger Endzeitpunkt für AG-i
GP(i)	gesamte Pufferzeit für AG-i

Zusätzliche Symbole zur Berücksichtigung der Kapazitäten:

r	Index der Ressourcen
r(i)	Index der Ressource, die den Arbeitsgang i durchführt
k(i,r)	Kapazitätsbedarf des Arbeitsgangs i an Ressource r
Kap(r)	(erneuerbare) Periodenkapazität der Ressource r
t	Einplanungszeitpunkt
An	Menge der in einem Planungsschritt bereits begonnenen Arbeitsgänge
Cn	Menge der in einem Planungsschritt bereits abgeschlossenen Arbeitsgänge
Dn	Menge der in einem Planungsschritt einplanbaren Arbeitsgänge

Annahmen:

deterministische Ausführungszeiten für alle Arbeitsgänge
bekannter Vorranggraph für die Arbeitsgänge (Netzplan)

Ansichten:

Graphen-Editor zur Erzeugung eines Netzplans

Ansicht nach Berechnung der frühestmöglichen und spätestzulässigen Termine

Gantt-Diagramm und Kapazitätsbelastungen (nach der Durchlaufterminierung)

Starten man dann das heuristische Lösungsverfahren, dann erhält man folgendes Bild:

Man erkennt, daß jetzt ein zulässiger Plan erzeugt wurde, bei dem die Kapazitäten nicht überschritten werden.

Literatur:

- Günther/Tempelmeier (2016), Abschnitt 11.1.4
- Tempelmeier (2018)