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.
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. Dann kann die Heuristik gestartet werden.
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
Man kann einen Balken in dem Gantt-Diagramm anklicken und mit der Maus horizontal
verschieben. Die geänderte Kapazitätsbelastung wird im Belastungsdiagramm angezeigt.
Alle Nachfolger des ausgewählten Vorgangs (im Bild 2C) werden farbig markiert.
Falls erforderlich, werden diese Vorgänge mit in die Zukunft verschoben.
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 (2013a), Abschnitt 10.1.4
- Tempelmeier (2010)
|
