Home

Kapazitätsorientierte Terminplanung (RCPSP)

Kapazitätsorientierte Terminplanung (RCPSP) (I)

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ß jeder Vorgang nur eine Ressource belegen kann. Mindest- oder Maximalabstände zwischen den Vorgänge werden nicht berücksichtigt.

Es wird das heuristische parallele Prioritätsregelverfahren eingesetzt. Eine formale Beschreibung des Verfahrens findet sich in Drexl/Kolisch/Sprecher (1997), S. 120 (Paralleles Prioritätsregelverfahren). Siehe hierzu auch Tempelmeier(2020b).

Zunächst werden die Termine ohne Berücksichtigung der Kapazitäten ermittelt und die resultierende Belastung der Ressource graphisch dargestellt. Dabei werden folgende Symbole verwendet:

i Index der Arbeitsgänge
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:

A. Dateneingabe

Zur Erzeugung eines Netzplans wird der Graphen-Editor eingesetzt, wobei ein Vorgangsknoten-Netzplan verwendet wird (MPM-Netzplantechnik).

Durch Rechtsklick auf die Knoten können die Vorgangsdauern, die Ressourcennummer und der jeweilige Ressourcenbedarf editiert werden. Schneller geht es aber in den Eingabetabellen des Moduls:

Zur Änderung eines Wertes klickt man in eine Zelle und betätigt die Leertaste oder man führt einen Doppelklick auf die Zelle aus.

B. Problemlösung

1. Einsatz des heuristischen Lösungsverfahren

Das heuristische Verfahren geht im Prinzip in der Weise vor, daß nach und nach, 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

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 im Zeitpunkt $t$ einplanbaren Vorgänge wird auf Prioritätsregeln zurückgegriffen. Es sind folgende Prioritätsregeln implementiert:

Das Verfahren führt erst eine Durchlaufterminierung (ohne Beachtung der Kapazitäten) durch. Als Ergebnis erhält man im Regelfall erheblichen Überlastungen der Ressourcen. Mit "Start" wird dann Heuristik durchgeführt. Die Zwischenergebnisse werden Schritt für Schritt protokolliert.

Zunächst werden frühestmögliche und spätestzulässige Start- und Endtermine (ohne Beachtung der Kapazitätsbeschränkungen) bestimmt:

Anhand einer Graphik kann man die Zulässigkeit dieser Termine überprüfen:

Durch einen Rechtsklick auf das Diagramm wird ein Menü zur Speicherung der Graphik eingeblendet. Wählt man SVG, dann wird eine skalierbare Graphik erzeugt und in dem aktuellen Standard-Browser angezeigt. SVG-Graphiken dieser Art lassen sich leicht in Webseiten einbetten.

Als nächstes kann man das heuristische Lösungsverfahren durchführen, wobei man in den Optionen einstellen kann, ob das Verfahren vollständig durchlaufen oder Schritt für Schritt interaktiv durchgeführt werden soll. Im letztgenannten Fall sieht das so aus:

Es bedeuten: Cn - eingeplant, An - begonnen, aber noch nicht fertig, Dn - einplanbar. Siehe hierzu auch Tempelmeier(2020b).

2. Exakte Lösung des Problems

Hier gibt es mehrere Möglichkeiten: 

a) 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. 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. "RCPSP" 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.

b) Optimierung auf dem lokalen 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-Dateien 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 den Befehl "include RCPSP.run;" ein. Dieser Befehl startet die Lösung des Problems. Die Ergebnisse werden in der Datei RCPSP.AUS gespeichert.

c) Optimierung auf dem lokalen PC mit GAMS

Unter https://ampl.com/try-ampl/download-a-free-demo/#windows kann man die Studentenversion von GAMS herunterladen. Ist GAMS auf dem Rechner installiert, dann kann mit dem Menüpunkt "GAMS-Datei erzeugen" für das aktuell betrachtete Problem das GAMS-Modell in einer Datei, z.B. "RCPSP.GMS", gespeichert werden. Diese Datei kopiert man dann in das GAMS-Arbeitsverzeichnis (...\Documents\GAMS\Studio\workspace\) und löst die Probleminstanz mit der GAMS Studio Software. Im Produktions-Management-Trainder kann dann mit dem Menüpunkt "GAMS-Lösung importieren" Lösungsdatei, z.B. "rcpsp.out" eingelesen werden. Dabei ist darauf zu achten, daß vor dem Importieren die im PMT-Modul geladenen Daten des Beispiels nicht verändert werden.

d) Nur für Python-Nutzer: Optimierung mit Python auf dem lokalen PC (Voraussetzung: Installiertes Python und Python-MIP)

Python-Menü

Wählt man den letzten Menüpunkt "Optimierung mit Python-MIP aus" aus, dann wird das mathematische Optimierungsmodell in einer für Python-MIP lesbaren Form erzeugt und gelöst. Die optimale Lösung wird dann wie üblich angezeigt.

Falls Python nicht installiert ist, dann wird dieser Menüpunkt nicht angezeigt.

Literatur:

- Günther/Tempelmeier (2020a), Abschnitt 11.1.4
- Tempelmeier (2020b)

Datenschutz | © 2021 POM Prof. Tempelmeier GmbH | Imprint