Multi-Start-Verfahren zur Lösung von Ressourcennivellierungsproblemen


Diplomarbeit, 2007

154 Seiten, Note: 2,3


Leseprobe

INHALTSVERZEICHNIS

1 Einleitung

2 MPM-Netzplantechnik

3 Ressourcennivellierungsprobleme

4 Heuristiken
4.1 Prioritätsregelverfahren
4.2 Prioritätsregelverfahren mit Basisintervall
4.3 PACK-Verfahren

5 Multi-Start Verfahren
5.1 Greedy Randomized Adaptive Search Procedure
5.2 Roulette-Wheel-Selection
5.3 Regret-based Biased Random Sampling

6 Implementierung der Verfahren
6.1 Ergebnisse
6.1.1 Ergebnisse für ubo10c mit d ∗ 1.25
6.1.2 Ergebnisse für ubo10c mit d ∗ 1.50
6.1.3 Ergebnisse für ubo100c mit d ∗ 1.25
6.1.4 Ergebnisse für ubo100c mit d ∗ 1.50
6.1.5 Ergebnisse mit Nachkontrolle
6.1.6 Ergebnisse für ubo10c mit d*1.25 und Nachkontrolle
6.1.7 Ergebnisse für ubo10c mit d*1.50 und Nachkontrolle
6.1.8 Ergebnisse für ubo100c mit d*1.25 und Nachkontrolle
6.1.9 Ergebnisse für ubo100c mit d*1.50 und Nachkontrolle
6.2 Analyse der Ergebnisse

7 Zusammenfassung und Ausblick

Abbildungsverzeichnis

Tabellenverzeichnis

Symbolverzeichnis

Abkürzungsverzeichnis

Literaturverzeichnis

Danksagung

An dieser Stelle möchte ich mich sehr herzlich bei allen bedanken, die für das Gelingen der vorliegenden Arbeit am Institut für Wirtschaftswissenschaft der TU Clausthal beigetragen haben. Bedanken möchte ich mich besonders bei Herrn Prof. Dr. Jürgen Zimmermann für die Unterstützung bei der Erstellung der Arbeit und für die umfassende und gute fachliche Betreuung. Des Weiteren danke ich Frau Prof. Dr. Barbara Hammer für die Übernahme des Korreferats.

Besonderer Dank gebührt meinen Eltern. Sie standen mir während meines gesamten Studiums in jeder Hinsicht zur Seite.

1 Einleitung

Ein Projekt bezeichnet nach DIN 69901 ein Vorhaben, dass sich im Regel- fall dadurch auszeichnet, dass es einmalig ist und innerhalb einer festgeleg- ten Zeitspanne eine vorgegebene Zielvorgabe erreichen soll. Die Einmaligkeit bezieht sich hierbei auf die Zielvorgabe, die Begrenzungen, z.B. finanziell, zeitlich oder personell, die Abgrenzung gegenüber anderen Vorhaben oder die Organisationsform. Des Weiteren bezeichnet ein Projekt eine Gesamt- heit vieler verschiedener Vorgänge, die das Ziel haben, die Anforderungen des Auftraggebers zu erfüllen. Beispiele für solche Vorhaben sind Bau- und Sanierungsprojekte oder Produktentwicklungsprojekte. Bei diesen Arten von Projekten sind die jeweils erwünschten Ziele und der angestrebte Zeitrahmen bekannt, wohingegen der Lösungsweg vorerst unbekannt ist und für jedes Pro- jekt einzeln ermittelt werden muss.

Durch zahlreiche Konkurrenten auf dem Markt und den dadurch hervorgerufenen Wettbewerbsdruck sind Unternehmen gezwungen, ihre Projekte möglichst ressourcenschonend und mit minimalen Kosten durchzuführen. Hierzu wurden in der Vergangenheit viele graphentheoretische Verfahren angewandt, die versucht haben, den Ressourcenverbrauch über die Dauer des Projektes möglichst gering zu halten.

In neueren Verfahren der ressourcenbeschränkten Projektplanung wird nun versucht, mittels heuristischer Algorithmen die Ressourceninanspruchnahme über die Dauer des Projektes zu minimieren. Da die Bereitstellungskosten für Ressourcen häufig nicht linear, sondern quadratisch ansteigen (vgl. Glei- chung 6) ist es von Vorteil Ressourcenschwankungen zu vermeiden. Durch die Nivellierung der Ressourceninanspruchnahme, über die Dauer des Projektes, wird somit versucht Spitzenwerte im Ressourcenverbrauch zu vermeiden um optimale Ergebnisse zu erzielen.

Das Ziel dieser Arbeit ist die Veränderung der heuristischen Single-Mode- Verfahren in Multi-Start-Verfahren zur Ressourcennivellierung von Projek- ten. Danach soll überprüft werden, ob die erhöhte Anzahl an Lösungsberech- nungen der Multi-Start-Verfahrens zu signifikanten Lösungsverbesserungen gegenüber den Single-Mode-Verfahren führen.

Es ist zu vermuten, dass die erhöhte Anzahl an Recheniterationen der Multi- Start-Verfahren zu einer Verbesserung der Lösung gegenüber den Single- Mode Varianten führt, da die Wahrscheinlichkeit, dass eine Lösung aus dieser Lösungsmenge einen besseren Zielfunktionswert als die Lösung des Single- Mode Verfahrens besitzt, mit wachsender Iterationszahl ansteigen sollte. Des Weiteren soll überprüft werden wie gut sich die einzelnen Ressourcenni- vellierungsverfahren und Prioritätsregeln zur Lösung der Ressourcennivellie- rungsprobleme eignen.

Zu Beginn dieser Arbeit erfolgt eine Erläuterung von MPM-Netzplänen (vgl. Kapitel 2). Diese Netzplantechnik, die auf Vorgangs-Knoten-Darstellung be- ruht, ist wird oft beim Zeitmanagement, sowie der Darstellung und der Or- ganisation von Projekten verwendet. Hiernach folgt eine Einführung in die Grundlagen der ressourcenbeschränkten Projektplanung unter dem Gesichts- punkt der Ressourcennivellierung (vgl. Kapitel 3). Anschließend werden vier verschiedene Prioritätsregeln vorgestellt, die in dieser Arbeit verwendet wer- den. Anschließend werden mehrere unterschiedlich komplexe Prioritätsregel- verfahren und deren Algorithmen vorgestellt und nachfolgend an jeweils ei- nem Beispiel erläutert. Danach werden drei bekannte Single-Mode-Verfahren zu Multi-Start-Verfahren umgewandelt, die mittels Prioritätsregeln versu- chen, verschiedene Lösungen für ein Projekt zu ermitteln, deren Ressourcen bestmöglich nivelliert sind. Von den Lösungen, die mit den Verfahren berech- net werden, wird immer die jeweils beste Lösung gespeichert, so dass nach Beendigung des Testlaufs die beste Lösung in der Ergebnissdatei gespeichert werden kann.

Der Schwerpunkt dieser Arbeit ist die Implementierung der drei Multi-Start- Verfahren mit den vier bekannten Prioritätsregeln, eine Einplanung nach dem PACK-Verfahren3 und eine abschließende Nachkontrolle mittels der Pro- grammiersprache C. Anschließend werden die implementierten Verfahren zur Ressourcennivellierung von Projekten unter verschiedenen Einflussfaktoren auf mehrere unterschiedlich komplexe vorgegebene Testsets angewendet. Die Lösungen der Multi-Start-Verfahren zur Ressourcennivellierung werden danach auf ihre Qualität überprüft, um festzustellen, ob und inwieweit MultiStart-Verfahren durch ihre erhöhte Anzahl von Iterationen bessere Lösungen bieten als Single-Mode-Verfahren.

Ein Fazit und ein Ausblick schließen die Arbeit ab.

2 MPM-Netzplantechnik

Die Metra-Potential-Methode (MPM) ist eine Netzplantechnik der Projekt- organisation zur Überwachung und zum Zeitmanagement von Projekten. Ein MPM-Netzplan stellt dabei das Vorgangsknotennetzwerk N = 〈V, E, δ〉 eines Projektes dar. V ist hier die Knotenmenge, E die Pfeilmenge und δ : E → Z die Bewertung der Pfeile der Menge E. Den einzelnen Vorgängen des Projekts werden hierbei die Knoten des Netzplans zugeordnet und die Zeitrestriktio- nen zwischen den Vorgängen werden durch die Pfeile dargestellt. Eine wichti- ge Eigenschaft der Netzpläne sind dessen Zyklen, die die Länge eines Weges, auf dem der Start- und Endknoten identisch ist, darstellen. Die Zyklen eines Netzplans dürfen keine positive Länge haben, da eine solche Zeitbeziehung nicht definiert ist.

Trotz der verschiedenen Zeitbeziehungen, die zwischen zwei Vorgängen exis- tieren können, geht man in MPM-Netzplänen immer von Start-Start- Beziehungen aus. Hierbei stellen die Pfeile zwischen zwei Vorgängen die Abstände zwischen den jeweiligen Startzeitpunkten dar (siehe Abbildung 1).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Start-Start-Beziehung der Vorgänge i und j

Ein Projekt besteht aus V = {1, ..., n} Vorgängen. Die Vorgänge i ∈ V haben jeweils eine Vorgangsdauer pi ∈ Z≥0, die sich aus der Bearbeitungsdauer des Vorgangs und einer eventuellen Maschinenumrüstzeit zusammensetzt. Die Menge V wird durch zwei fiktive Vorgänge 0 und n + 1 erweitert, wobei Vor- gang 0 den Projektbeginn und Vorgang n + 1 das Projektende kennzeichnen. Beide Vorgänge haben, da sie ja lediglich Scheinvorgänge sind, die Vorgangs- dauer p0 = pn+1 = 0. Neben der Vorgangsdauer besitzt jeder Vorgang i auch einen Startzeitpunkt Si ∈ R≥0, wobei der Startzeitpunkt des fiktiven Vorgangs 0 mit S0 = 0 fest vorgegeben ist. Der Startzeitpunkt des Vorgangs n + 1 muss immer kleiner-gleich der maximalen Projektdauer d des Projektes sein und ist somit Sn+1 ≤ d.

Ein Vektor von Startzeitpunkten S = (S0, S1, ..., Sn+1) mit Si ∈ R≥0 für alle Vorgänge i ∈ V \ {0} = {1, ..., n, n + 1} und S0 = 0 eines Projektes wird Schedule genannt.

Den Endzeitpunkt des Vorgangs i gibt die Variable Ci = Si + pi an, die sich aus dem Startzeitpunkt und der Vorgangsdauer des Vorgangs i zusammensetzt. Dabei ist zu beachten, dass laufende Vorgänge nicht unterbrochen werden können, sondern am Stück ausgeführt werden müssen. Wäre dies nicht der Fall, könnte es bedingt durch die Start-Start-Beziehungen zu Komplikationen kommen. Da das Ende eines Vorgangs durch eine Unterbrechung nicht klar vorhersagbar ist, können dadurch nicht erlaubte Überschneidungen bei der Ausführung der Vorgänge auftreten.

Die Zeitrestriktionen, die zwischen den Startzeitpunkten von zwei Vorgängen auftreten können, sind ein zeitlicher Mindestabstand sowie ein zeitlicher Höchstabstand. Der zeitliche Mindestabstand

Abbildung in dieser Leseprobe nicht enthalten

ist der Abstand, der zwischen dem Start des Vorgangs i und seinem Nachfolger j mindestens eingehalten werden muss und wird durch einen Pfeil von Vorgang i zu Vorgang j dargestellt.

Als zweite Zeitrestriktion wird der zeitliche Höchstabstand dmaxij mit

Abbildung in dieser Leseprobe nicht enthalten

definiert, der besagt, dass der Vorgang j spätestens dmaxij Zeiteinheiten nach Start des Vorgangs i starten muss. Der zeitliche Höchstabstand wird hierbei durch einen Pfeil von Vorgang j zu Vorgang i dargestellt. Die Zeitrestriktionen können durch einzuhaltende Transportzeiten oder Endfertigungstermine bedingt sein (siehe Abbildung 2).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Mindest- und Höchstabstände im MPM-Netzplan

Somit ist ein MPM-Netzplan ein bewerteter Digraph mit einer Quelle 0 und einer Senke n+1, d.h. einem Startknoten mit nur auslaufenden Pfeilen und ei- nem Endknoten mit nur einlaufenden Pfeilen mit Ausnahme des Rückwärts- pfeils von n + 1 zu 0, der die maximale Projektdauer d angibt. Mit Hilfe des längsten Weges zwischen dem Knoten 0 und dem Knoten i kann man nun den frühesten Startzeitpunkt ESi eines Vorgangs i bestimmen. Da- zu ermittelt man die längsten Wege d0i mit i ∈ V vom Projektstart 0 zu allen anderen Knoten i und macht sich die Eigenschaft des festen Startzeitpunktes von Vorgang 0, nämlich S0 = 0 zunutze. Da Vorgang i nicht starten kann, bevor alle Zeitrestriktionen erfüllt sind, gibt d0i = dmin0 i den Mindestabstand vom Projektstart zu dem Vorgang i an, so dass der früheste Startzeitpunkt wie folgt definiert werden kann:

Abbildung in dieser Leseprobe nicht enthalten

Anhand Gleichung 3 ist ersichtlich, dass ESn+1 die kürzest mögliche Projekt- dauer ist. Zur Bestimmung des spätesten Startzeitpunkts LSi wird ähnlich vorgegangen, nur das in diesem Fall der längste Weg di0 von Vorgang i zum Projektanfang 0 gesucht ist. Die negative Länge des längsten Weges von Vor- gang i zum Projektanfang entspricht somit dem spätesten Startzeitpunkt des

Vorgangs i und wird in Gleichung 4 definiert.

Abbildung in dieser Leseprobe nicht enthalten

Eine weitere wichtige Zeitbeziehung ist die gesamte Pufferzeit T Fi (total float), die beschreibt, um welche Zeitspanne der Start von Vorgang i ∈ V \ {0} maximal verzögert werden kann, ohne dass sich die maximale Projektdauer LSn+1 erhöht. Folglich ergibt sich die maximale Pufferzeit aus der Differenz des spätesten Startzeitpunktes LSi und des frühesten Startzeitpunktes ESi des Vorgangs i ∈ V \ {0}.

Abbildung in dieser Leseprobe nicht enthalten

Gleichung 5 definiert den Total-Float, mit dem man außerdem ermitteln kann, welche Vorgänge zu ihrem frühsten Startzeitpunkt gestartet werden müssen. Hat beispielsweise ein Vorgang i ∈ V \ {0} eine Pufferzeit von TFi = 0, so muss dieser zu seinem frühesten Startzeitpunkt ausgeführt wer- den, damit sich die gesamte Projektdauer nicht verzögert. Diese Vorgänge werden als kritisch bezeichnet. Hieran ist erkennbar, dass alle Vorgänge, die auf dem längsten Weg vom Projektanfang zum Projektende liegen, bei mi- nimaler Projektdauer kritisch sind.

Das Ziel ist es, die einzelnen Vorgänge des Projektes so einzuplanen, dass eine bestimmte Zielvorgabe erreicht wird. In dieser Arbeit ist das zu erreichende Ziel eine bestmögliche Ressourcennivellierung für das Projekt.

3 Ressourcennivellierungsprobleme

Der Begriff Ressourcen wird in der Wirtschaft sehr oft als Oberbegriff für verschiedene Arten von Kapazitäten gebraucht. Dies können z.B. Arbeiter, Maschinenkapazitäten oder verfügbare Rohstoffe sein. Bei der nachfolgend betrachteten Ressourcennivellierung (resource levelling) werden lediglich die erneuerbaren Ressourcen einbezogen. Dies können z.B. Maschinenkapazitäten sein, da diese nach der Ressourceninanspruchnahme nicht verbraucht sind, sondern dem Anwender wieder zur Verfügung stehen.

Die Gründe für die Durchführung von Ressourcennivellierungen bei Projekten können folgendermaßen sein:

- Einhalten von Kapazitätsgrenzen der Ressource
- Vermeiden von täglichen Schwankungen im Ressourcenverbrauch
- Sicherstellen einer gleichmäßigen Nutzung der Ressource für das Projekt

Die Nivellierung des Ressourcenverbrauchs über die Dauer des Projektes führt zu einer möglichst gleichmäßigen Ressourceninanspruchnahme über die Projektdauer. Hierdurch können Probleme wie hohe Ressourcenschwankun- gen, wie sie bei ES-Schedules entstehen können, vermieden werden. Da diese dazu führen könnten, dass vorgegebene Grenzen wie z.B. die Verfügbarkeit von Ressourcen oder ein beschränktes Kostenbudget überschritten werden. Die Menge von Ressourcen wird mit R bezeichnet. Sie enthält die erneu- erbaren Ressourcen k ∈ R, die während der Durchführung des Projektes benötigt werden. Jeder einzelne Vorgang i ∈ V benötigt während seiner Ausführung rik ≤ Z≥0 Einheiten der Ressource k ∈ R, wobei zu beachten ist, dass rik ≤ Rk für alle i ∈ V und k ∈ R ist.

Die Ressourcennivellierung gehört zu den ressourcenabhängigen Zielen. Hier- bei wird versucht, die Ressourcen k ∈ R durch Verschieben der Vorgänge im [ ] betrachteten Zeitintervall 0, d gleichmäßig auszulasten.

Durch eine ungleichmäßige Auslastung von Ressourcen kann es zu Über- schreitungen eines bestimmten vorgegeben Ressourcenniveaus kommen. Selbst bei nicht vorgegebenen Grenzen ist es vorteilhaft, eine gleichmäßige Auslastung der Ressourcen anzustreben, da dies einen gleichmäßigeren Ablauf des Projektes ermöglicht und hohe Kosten vermeidet.

Bei dem hier betrachteten Beispiel der Ressourcennivellierung werden die Kostenfaktoren nicht in Betracht gezogen, sondern lediglich die reinen Res- sourceninanspruchnahmen herangezogen, so dass als Zielfunktion die Funk- tion RL [15, S.123] der Ressourcennivellierung benutzt werden kann.

Abbildung in dieser Leseprobe nicht enthalten

In der Zielfunktion in Gleichung 6 wird der anfallende Ressourcenverbrauch des berechneten Schedules quadriert und für jeden Zeitpunkt der gesamten Projektdauer über alle verwendeten Ressourcen aufsummiert. Hierbei ist deutlich erkennbar, dass Spitzen im Ressourcenverbrauch unerwünscht sind. Durch das Quadrat von rk in Gleichung 6 haben auch kleine Unterschiede im Ressourcenverbrauch eine große Auswirkung auf den Zielfunktionswert. Um die Resultate dieser Zielfunktion zu minimieren, wird versucht, die Ressourcen über die gesamte Dauer des Projektes möglichst gering zu halten. Dies ist die Aufgabe der Ressourcennivellierung, die in dieser Arbeit bestmöglich mittels Multi-Start-Verfahren gelöst werden soll.

4 Heuristiken

Das Wort Heuristik stammt aus dem altgriechischen Sprachschatz und be- deutet finden bzw. entdecken (abgeleitet vom [alt]griechischen zu deutsch ”heurisko“ ”ichfinde“).MittelsHeuristikenwerdenVerfahrenbeschrieben, die für Optimierungsprobleme in kurzer Zeit gute Lösungen ermitteln. Diese Lösung ist zwar nicht immer die optimale Lösung, liegt jedoch sehr nahe am optimalen Wert. Über die genaue Entfernung, der anhand heuristischer Methoden ermittelten guten Lösung zur optimalen Lösung, kann jedoch keine Aussage getroffen werden. Die bekannten Heuristiken sind entweder Eröffnungsverfahren oder Verbesserungsverfahren.

Eröffnungsverfahren dienen dabei der Bestimmung einer oder mehrerer zulässi- ger guter Lösungen für die Problemstellung. Bei den Verbesserungsverfahren liegen bereits eine oder mehrere Ausgangslösungen vor. Diese versucht man mit den Verbesserungsverfahren zu optimieren, bis ein vorher bestimmtes Abbruchkriterium erreicht ist. Meist werden auch Eröffnungsverfahren mit Verbesserungsverfahren kombiniert. Die Verbesserungsverfahren können da- bei in zwei Arten klassifiziert werden. Zum einen in die deterministischen Verfahren die, wenn man von einem Ausgangsproblem das immer gleich ist ausgeht, stets dieselbe Lösung liefern. Die andere Variante der Verbesserungs- verfahren sind die stochastischen Verfahren, die stochastische Elemente ent- halten, so dass bei mehrfacher Anwendung des Algorithmus auf das selbe Ausgangsproblem stets verschiedene Lösungen entstehen können.

4.1 Prioritätsregelverfahren

Ein heuristisches Verfahren zur Lösung von Ressourcennivellierungsproblemen ist das Prioritätsregelverfahren [15, S.179]. Dieses Verfahren wird auch Konstruktionsverfahren genannt, da es durch allmähliches Einplanen von Vorgängen eine Näherungslösung generiert.

Beim Prioritätsregelverfahren wird ein Teilschedule als Startschedule aus- gewählt. Normalerweise ist dies der Schedule SC = (0) mit der Menge der bisher eingeplanten Knoten C = {0} und S0 = 0 als Startzeitpunkt des Vorgangs 0. Dieser Teilschedule wird anschließend in jedem Schritt um einen Vorgang j erweitert. Die Menge C = V \ {0} ist die Menge der noch nicht ein- geplanten Vorgänge in dem Schedule. Nach jedem Einplanen eines Vorgangs müssen die ES- und LS-Werte der anderen verbleibenden Vorgänge neu berechnet werden, da sich dort durch das Einplanen der Vorgänge Verände- rungen ergeben könnten. Die neuen ES- und LS-Werte sind nach folgenden Funktionen [15, S.179] zu berechnen:

Abbildung in dieser Leseprobe nicht enthalten

Somit ergibt sich für den noch nicht eingeplanten Vorgang j ein Zeitfenster Wj(SC) = [ESj(SC),LSj(SC)] in dem dieser ausgeführt werden kann. Um den Vorgang j zu einem möglichst optimalen Zeitpunkt Sj einzuplanen, wird eine Zielfunktion zur Berechnung des Funktionswertes für jeden möglichen Startzeitpunkt t ∈ Wj (SC ) benötigt. Dazu ist die Berechnung der Differenz zwischen dem neuen potentiellen Schedule SC∪{j} und dem alten Schedule SC notwendig. Je kleiner der Wert ist, desto besser ist der jeweilige Startzeit- punkt des Vorgangs j, wodurch die Auswirkung der Einplanungsposition auf den Zielfunktionswert zu erkennen ist. Der Vorgang j wird somit immer zu dem Zeitpunkt t ∈ Wj (SC ) eingeplant, an dem der Zielfunktionswert fa mi- nimal ist. Um die durch die Einplanung des Vorgangs j zum Startzeitpunkt Sj entstandenen Erweiterungskosten für das Ressourcennivellierungsproblem zu bestimmen, wird folgende allgemeine Formel [15, S.180] verwendet:

Abbildung in dieser Leseprobe nicht enthalten

Durch Subtraktion der Kosten des alten Schedules SC von den Kosten des neuen Schedules SC∪{j} werden die Erweiterungskosten, die durch das Hin- zufügen des Vorgangs j entstehen, berechnet. Nach Festlegen des optimalen Startzeitpunkts S+j fürdenVorgangj∈CwähltmanalsStartzeitpunktSj den optimalen Zeitpunkt S+j . Des Weiteren wird der neue Vorgang zu dem bisherigen Schedule hinzugefügt SC := SC∪{j} und der Vorgang j aus der Menge der bisher nicht eingeplanten Knoten C entfernt. Der neue Vorgang im Schedule wird in der Menge der eingeplanten Knoten C ergänzt. Das feste Einplanen des Vorgangs j kann aufgrund der Zeitrestriktionen die potentiellen Startzeitpunkte anderer Vorgänge verändern, wodurch nach je- dem Einplanen eines Vorgangs überprüft werden muss, ob die ES- und LS- Werte korrigiert werden müssen. In diesem Fall müssen sie nach den Formeln (7) und (8) angepasst werden. Dies wird solange fortgeführt, bis alle Vorgänge eingeplant worden sind.

Um bei dem Prioritätsregelverfahren die Vorgänge auszuwählen, die einge- plant werden sollen, werden verschiedenste Prioritätsregeln verwendet. Für das Ressourcennivellierungsproblem gibt es mehrere Regeln, die gute Lösun- gen liefern. Diese Regeln werden in dynamische und statische Prioritätsregeln unterteilt. Bei den statischen Regeln werden die Prioritätsregelwerte zu Be- ginn des Verfahrens berechnet und nicht weiter verändert. Wohingegen bei den dynamischen Prioritätsregeln die Prioritätsregelwerte nach jedem Ein- planungsvorgang aktualisiert werden. Weiterhin sind Prioritätsregeln, die so- wohl statisch als auch dynamisch sein können, möglich. Folgende bekannte Prioritätsregeln [15, S.184] eignen sich gut für Ressourcennivellierungspro- bleme und werden später in den Multi-Start-Verfahren verwendet. GRD-Regel (Greatest Resource Demand)

Abbildung in dieser Leseprobe nicht enthalten

Vorgang j mit dem größten Ressourcenbedarf wird gewählt.

GRDT-Regel (Greatest Resource Demand per Time unit)

Abbildung in dieser Leseprobe nicht enthalten

Vorgang j mit dem größten Ressourcenbedarf pro Zeiteinheit wird gewählt.

LST-Regel (Latest Start Time)

Abbildung in dieser Leseprobe nicht enthalten

Vorgang j mit kleinstem, spätesten Startzeitpunkt wird gewählt.

MST-Regel (Minimum Slack Time)

Abbildung in dieser Leseprobe nicht enthalten

Vorgang j mit der kleinsten Gesamtpufferzeit wird gewählt.

Eine Kombination dieser Prioritätsregeln ist möglich, indem zuerst nach dem einen Verfahren auswählt und die resultierende Menge mit einem zweiten Verfahren betrachtet wird. So wäre z.B. eine Auswahl über das Verfahren MST-GRD möglich, bei dem zuerst alle Vorgänge j ∈ C mit kleinster Ge- samtpufferzeit aus der Menge C gewählt werden. Danach wendet man die GRD-Regel auf diese ausgewählten Vorgänge an und bestimmt die Vorgänge mit dem größten Ressourcenverbrauch aus der Menge. Oft gibt es jedoch kei- ne Regel oder Regelkombination, die eindeutig besser als alle anderen Regeln ist. Aus diesem Grund kann man das Verfahren nicht nur einmal, sondern mehrfach mit verschiedenen Prioritätsregelkombinationen auf das Problem anwenden und wählt aus der Lösungsmenge die beste Lösung aus.

Algorithmus:

Initialisierungsphase:

S0 := 0, C := {0} und C := V \ {0} FOR ALL i ∈ V

FOR ALL j ∈ V

Bestimme die längsten Wege dij . END FOR;

END FOR;

FOR ALL i ∈ V \ {0} ESi := d0i;

LSi := −di0; END FOR;

FOR ALL i ∈ C

IF LSi = ESi THEN // (fixer Vorgang)

Si := ESi, C := C ∪ {i}, C := C \ {i}; END FOR;

Hauptphase:

WHILE C = [Abbildung in dieser Leseprobe nicht enthalten]

Selektiere je nach Prioritätsregel i ∈ C mit höchster Priorität. Ermittle die Entscheidungszeitpunkte Di(SC ).

Wähle die größte Minimalstelle S+i vonfa aufDi(SC).

Si := S+i , C := C ∪ {i} und C := C \ {i}. FOR ALL i ∈ C

Bestimme die ES- und LS-Werte neu. ESi(SC) := max{d0i,Sj + dji}; LSi(SC ) := min {−di0, Sj − dij } ; END FOR;

FOR ALL i ∈ C

IF LSi = ESi THEN: // (fixer Vorgang)

Si := ESi, C := C ∪ {i} und C := C \ {i}; END FOR;

END WHILE; RETURN S.

Beispiel:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Projekt-Netzplan mit 9 realen Vorgängen Legende:

Zur Veranschaulichung des Algorithmus und der Funktionsweise des Prio- ritätsregelverfahrens [15, S.179] folgt ein explizites Beispiel anhand des in Abbildung 3 dargestellten Projektnetzplans mit 9 realen Vorgängen, einer erneuerbaren Ressource R und einer maximalen Projektdauer von d =27 Ta- gen. Als Prioritätsregel wird die GRD -Regel (Greatest Resource Demand) angewendet. Zuerst bestimmt man die frühesten- und spätesten Startzeit- punkte sowie den Ressourcenverbrauch der einzelnen Vorgänge des Projektes (siehe Tabelle 1).

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: ESi, LSi, pi, ri · pi und T Fi-Werte für i = 0, ..., 10

Im Initialisierungsschritt des Algorithmus setzt man den Startzeitpunkt S0 := 0, die Menge der bereits eingeplanten Vorgänge auf C := {0} und den Schedule auf SC := (0).

Anhand der GRD -Regel wird der Vorgang 7 mit dem größten Ressourcen- verbrauch ausgewählt. Als Menge von Entscheidungszeitpunkten erhält man D7(SC) = {15,17}.

Die Erweiterungskosten für t = 15 und t = 17 sind fa(SC,7,15) = fa(SC,7,17) = 64 − 0 = 64.

Weil die Erweiterungskosten für beide Zeitpunkte gleich sind, wird der Vorgang zu seiner größten Minimalstelle, also zu S7 = 17 eingeplant. Somit beträgt C := {0, 7} und C := {1, 2, 3, 4, 5, 6, 8, 9, 10}.

Da der Vorgang zu seinem spätesten Startzeitpunkt eingeplant wurde, müssen nun die frühesten Startzeitpunkte der Vorgänge 9 und 10 aktualisiert werden. Dabei ergibt sich ES9 := 22 und ES10 := 27. Für die Vorgänge i = 9, 10 gilt dadurch ESi = LSi. Dies bedeutet, dass die Vorgänge nun fixiert sind und ihre Startzeitpunkte auf S9 = 22 und S10 = 27 gesetzt werden. Des Weiteren werden C und C zu C := {0, 7, 9, 10} und C := {1, 2, 3, 4, 5, 6, 8} geändert. Beim zweiten Durchlauf der Hauptphase wird Vorgang 2 mit einem Ressour- cenverbrauch von 12 ausgewählt. Die Menge der Entscheidungszeitpunkte beträgt hier D2(SC) = {0,2}. Für die Erweiterungskosten gilt: fa(SC,2,0) = fa(SC,2,2) = 145 − 109 = 36 für t ∈ {0, 2} .

Somit wird dieser Vorgang wieder zu seiner größten Minimalstelle S2 = 2 eingeplant. Dadurch, dass Vorgang 2 seinem LS-Wert zugeordnet wurde, muss der ES-Wert von Vorgang 5 zu ES5 = 9 aktualisiert werden, wodurch seine ES- und LS-Werte wieder identisch sind. Der Vorgang ist fix und wird deshalb zu seinem LS-Wert eingeplant. Daraufhin aktualisiert man wieder C und C zu C := {0, 2, 5, 7, 9, 10} und C := {1, 3, 4, 6, 8}.

In der dritten Schleife der Hauptphase wird der Vorgang 3 mit einem Ressour- cenverbrauch von 9 ausgewählt. Seine Menge von Entscheidungszeitpunkten ist

Abbildung in dieser Leseprobe nicht enthalten

Die Erweiterungskosten betragen

Abbildung in dieser Leseprobe nicht enthalten

Vorgang 3 wird also zu S3 = 6 eingeplant, sowie die Vorgangsmengen C und C zu C := {0, 2, 3, 5, 7, 9, 10} und C := {1, 4, 6, 8} aktualisiert. Durch den

Mindestabstand dmin13 = 6 zwischen Vorgang 1 und Vorgang 3 ist der LS- Wert von Vorgang 1 auf LS1 = 0 zu aktualisieren. Somit sind dessen ES- und LS-Werte identisch und Vorgang 1 wird fix und muss zu S1 = 0 starten. Wiederum wird C und C zu C := {0, 1, 2, 3, 5, 7, 9, 10} und C := {4, 6, 8} aktualisiert.

Beim vierten Durchlauf der Hauptphase wird Vorgang 4 mit einem Res- sourcenverbrauch von 8 gewählt. Die Menge der Entscheidungszeitpunkte ist hierbei

Abbildung in dieser Leseprobe nicht enthalten

und die Erweiterungskosten betragen für t = 3

Abbildung in dieser Leseprobe nicht enthalten

und für t ∈ {5, 6, 8}

Abbildung in dieser Leseprobe nicht enthalten

Vorgang 4 wird somit zu S4 = 8 eingeplant und man aktualisiert die Vor- gangsmengen C := {0, 1, 2, 3, 4, 5, 7, 9, 10} sowie C := {6, 8}. Da Vorgang 4 zu seinem spätesten Startzeitpunkt eingeplant wurde, müssen die frühesten Startzeitpunkte von Vorgang 6 und 8 zu ES6 = 17 und ES8 = 24 aktualisiert werden. Da jetzt für beide Vorgänge i = 6, 8 ESi = LSi gilt, sind diese auch fixiert und werden zu S6 = 17 und S8 = 24 eingeplant. Es folgt eine weitere Aktualisierung von C := {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} und C := [Abbildung in dieser Leseprobe nicht enthalten].

Somit wurden alle Vorgänge der Menge C abgearbeitet und die Schleife der Hauptphase bricht nach dem vierten Durchlauf ab, so dass der nach der GRD -Regel fertig berechnete Schedule S := (0, 0, 2, 6, 8, 9, 17, 17, 24, 22, 27) zurückgegeben wird. Die Ressourcenkosten für diesen Schedule betragen 354 Einheiten. Abbildung 4 zeigt das Ressourcenprofil des im Beispiel berechne- ten Schedules.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Ressourcenprofil des Schedules beim Prioritätsregelverfahren

4.2 Prioritätsregelverfahren mit Basisintervall

Beim letzten Beispiel wurde zur Berechnung der Erweiterungskosten stets die Funktion fa(SC , j, t) herangezogen, die die Erweiterungskosten anhand der bis zuletzt eingeplanten Vorgänge berechnet. Wenn jedoch ein anderer Vorgang l ∈ C vor unserem Vorgang j eingeplant wird, könnte sich das der Berechnung zugrunde liegende Ressourcenprofil verändern, so dass sich die Erweiterungskosten des Vorgangs j zu dem vorherigen Verfahren unterschei- den würde.

Im folgenden Verfahren gibt es nun die Möglichkeit einen bestimmten Anteil dieses Vorgangs l ∈ C in die Berechnung der Erweiterungskosten für Vorgang j mit einzubeziehen. Um dies zu realisieren, wird ein Basisintervall [15, S.187] für einen Vorgang eingeführt, dass die Zeitpunkte angibt, zu denen ein bisher noch nicht eingeplanter Vorgang sich auf jeden Fall in Ausführung befindet. Diese Zeitpunkte des Vorgangs sind dabei unabhängig von seinen Startzeitpunkten. Das Basisintervall erstreckt sich in diesem Fall vom spätes- ten Startzeitpunkt LSi des Vorgangs bis zu seinem frühesten Fertigstellungs- zeitpunkt ECi (ECi := ESi + pi). Somit wird ein Vorgang i unabhängig von seinem Startzeitpunkt Si in dem Basisintervall [LSi, ECi[ ausgeführt. Hat ein Vorgang i ∈ V z.B. als frühesten Startzeitpunkt ESi = 5, als spätesten Startzeitpunkt LSi = 7, sowie eine Projektdauer von pi = 6, so ist das Basi- sintervall, in dem er auf jeden Fall ausgeführt wird, [7, 11[.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5: Basisintervall [LSi, ECi[ von Vorgang i

Im vorangegangenen Beispiel wurden bereits fixierte Vorgänge eingeführt, deren frühester und spätester Startzeitpunkt identisch sind. Nun fügt man zu diesen noch teilfixierte Vorgänge i ∈ V hinzu, die die folgende Ungleichung 0 < T Fi < pi erfüllen und somit ein Basisintervall [LSi, ECi[ haben. Unter Verwendung des Basisintervalls und der fixierten und teilfixierten Vorgänge kann zur Ressourcenberechnung eine Menge von Vorgängen bestimmt werden, die zu einer bestimmten Zeit t aktiv sind.

Abbildung in dieser Leseprobe nicht enthalten

Gleichung 14 beschreibt die Menge von Vorgängen, die zum Zeitpunkt t in Ausführung sind. Daraus kann die Ressourcenverbrauchsformel wie folgt formuliert werden.

Abbildung in dieser Leseprobe nicht enthalten

Mit dieser neuen Ressourcenformel aus Gleichung 15 wird weiterhin die Formel für die Erweiterungskosten für das Ressourcennivellierungsproblem modifiziert. Die abgewandelte Formel zur Berechnung der Erweiterungskosten für das Ressourcennivellierungsproblem lautet nun:

Abbildung in dieser Leseprobe nicht enthalten

Wenn die bisher verwendete Erweiterungskostenfunktion für Ressourcennivellierungsprobleme fa durch die neue Funktion fb ersetzt wird, kann die Effizienz des Prioritätsregelverfahrens gesteigert werden.

Beispiel:

Zur Verdeutlichung der neuen Erweiterungskostenfunktion für das Ressourcennivellierungsproblem dient folgendes Beispiel, dass dem MPM-Netzplan aus Abbildung 3 zugrunde liegt und unter Zuhilfenahme des Prioritätsregelverfahrens mit Basisintervall [15, S.187] gelöst wird.

In der Initialisierungsphase setzt man erneut S0 = 0, C := {0} und SC = 0. Nun werden die teilfixierten Vorgänge anhand der Vorgangsdauern pi und der Gesamtpufferzeit T Fi der Vorgänge i ∈ V \ {0} bestimmt. Für die Vorgänge i = 1, 2, 3, 5, 9 gilt T Fi ≤ pi, womit sie teilfixiert sind. Die Ba- sisintervalle dieser Vorgänge können somit bereits in das Ressourcenprofil eingetragen werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6: Basisintervalle der teilfixierten Vorgänge

In der Hauptphase beim ersten Durchlauf nach der GRD -Regel wird Vorgang

7 als erster einzuplanender Vorgang ausgewählt. Die Entscheidungszeitpunkte dafür sind

Abbildung in dieser Leseprobe nicht enthalten

Für t = 15 und t = 17 ergeben sich die Erweitungskosten fb(SC,7,15) = fb(SC,7,17) = 64.

Folglich plant man den Vorgang zu seiner größten Minimalstelle t = 17 ein. Dadurch, dass Vorgang 7 zu seinem LS eingeplant wurde, müssen die ES-

Werte der Vorgänge 9 und 10 aktualisiert werden. Hierbei stellt sich heraus, dass für beide ESi = LSi gilt und sie somit fixiert sind und fest eingeplant werden können. Des Weiteren werden die Mengen C und C zu C := {7, 9, 10} bzw. C := {1, 2, 3, 4, 5, 6, 8} aktualisiert.

Im zweiten Durchlauf der Hauptphase wird Vorgang 2 mit den Entscheidungszeitpunkten

Abbildung in dieser Leseprobe nicht enthalten

ausgewählt. Die Erweiterungskosten betragen: für t = 0

Abbildung in dieser Leseprobe nicht enthalten

und für t = 2

Abbildung in dieser Leseprobe nicht enthalten

wodurch Vorgang 2 zu S2 = 0 einplant und C bzw. C zu C := {2, 7, 9, 10} und C := {1, 3, 4, 5, 6, 8} aktualisiert werden.

In der dritten Hauptphase wird Vorgang 5 mit den Entscheidungszeitpunkten

Abbildung in dieser Leseprobe nicht enthalten

und den damit verbundenen Erweiterungskosten für t = 7 von

Abbildung in dieser Leseprobe nicht enthalten

und für t = 9 von

Abbildung in dieser Leseprobe nicht enthalten

gewählt. Aufgrund der Erweiterungskosten entscheidet man sich für S5 = 9 und aktualisiert noch die Mengen C und C.

Beim vierten Durchlauf der While-Schleife wird Vorgang 3 gewählt. Er hat die Entscheidungszeitpunkte

Abbildung in dieser Leseprobe nicht enthalten

mit den jeweiligen Erweiterungskosten

Abbildung in dieser Leseprobe nicht enthalten

für t = 6 und

Abbildung in dieser Leseprobe nicht enthalten

für t = 8, wodurch Vorgang 3 zu S3 = 6 startet. Dadurch, dass Vorgang 3 zu S3 = 6 startet, muss Vorgang 1 spätestens zu S1 = 0 beginnen, wodurch er fix wird. Somit sind die Mengen C und C mit C := {1, 2, 3, 5, 7, 9, 10} und C := {4, 6, 8} festgelegt.

Beim fünften Durchlauf ist Vorgang 4 der Vorgang mit dem größten Ressour- cenverbrauch und wird somit gewählt. Seine Entscheidungszeitpunkte sind

Abbildung in dieser Leseprobe nicht enthalten

Im Gegensatz zu den meisten anderen Vorgängen hat Vorgang 4 mehr als nur seine ES- und LS-Werte als Entscheidungszeitpunkte. Dies ist darauf zurückzuführen, dass in dem Intervall zwischen seinem frühesten und spätes- ten Startzeitpunkt andere Vorgänge beendet werden. Bei diesen Zeitpunkten handelt es sich ebenso um günstige Einplanungszeitpunkte, da der Ressour- cenverbrauch dort wieder geringer wird. Aus diesem Grund sind diese Zeit- punkte gleichzeitig Entscheidungszeitpunkte für Vorgang 4.

Die zugehörigen Erweiterungskosten betragen somit für t = 3

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

was dazu führt, dass Vorgang 4 zu S4 = 4 startet.

Dadurch, dass Vorgang 4 zu S4 = 4 startet, muss man aufgrund dmin46 = 9

den ES-Wert von Vorgang 6 auf ES6 = 13 aktualisieren.

Im nächsten Durchlauf der Hauptphase wählt man aus den verbleibenden Vorgängen Vorgang 6 aus. Seine möglichen Entscheidungszeitpunkte sind

Abbildung in dieser Leseprobe nicht enthalten

Die dafür anfallenden Erweiterungskosten betragen für t = 13

Abbildung in dieser Leseprobe nicht enthalten

so dass S6 = 14 als Startzeitpunkt ausgewählt wird. Dieser Startzeitpunkt von Vorgang 6 führt wieder zu einer Anpassung des ES-Wertes von Vorgang

8, der wegen dmin68 = 7 auf ES8 = 21 aktualisiert werden muss. Wiederum werden C und C zu C := {1, 2, 3, 4, 5, 6, 7, 9, 10} bzw. C := {8} verändert. Im siebten Durchlauf verbleibt lediglich Vorgang 8 mit den Entscheidungs- zeitpunkten

Abbildung in dieser Leseprobe nicht enthalten

Seine Erweiterungskosten betragen für t = 21

Abbildung in dieser Leseprobe nicht enthalten

wodurch sich S8 = 21 ergibt.

Nach Aktualisierung der Mengen C und C folgt, dass C := V und C := ∅ sind, worauf die while-Schleife beim nächsten Versuch abgebrochen und der Schedule S := (0, 0, 0, 6, 4, 9, 14, 17, 21, 22, 27) zurückgegeben wird. Die Res- sourcenkosten für diesen Schedule betragen nun 298 Einheiten. Abbildung 7

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 7: Ressourcenprofil des Schedules beim Prioritätsregelverfahren mit Basisintervall zeigt das Ressourcenprofil des zuvor berechneten Beispiels.

Um die Effizienz der beiden Varianten des Prioritätsregelverfahrens zu er- mitteln, werden die gesamten Ressourcenkosten beider Schedules mittels der

Abbildung in dieser Leseprobe nicht enthalten

berechnet. Hierbei erhält man für das erste Verfahren ohne Basisintervall Res- sourcenkosten von 354 Einheiten, wogegen das Verfahren mit Basisintervall einen Schedule erzeugt, der nur 298 Einheiten benötigt. Somit erzeugt das Verfahren mit Basisintervall einen effizienteren Schedule, als das Verfahren ohne Basisintervall.

4.3 PACK-Verfahren

Auch beim PACK-Verfahren3 wird versucht, die Vorgänge des Projektes möglichst ressourcenschonend und unter Vermeidung starker Schwankungen und so genannter ”Peaks“(Spitzenwerte)einzuplanen.AlsAusgangsgrund- lage wird erneut ein Ressourcenprofil verwendet, in das man die Vorgänge einplanen kann. Das Ziel ist, die Vorgänge so einzuplanen, dass das Res- sourcenprofil am Ende möglichst einem Rechteck gleicht. Dabei dürfen die gegebenen Zeitrestriktionen jedoch nicht verletzt werden, um dieses Ziel zu erreichen. Aus der Art und Weise des Verfahrens, die einzelnen Vorgänge möglichst platzsparend in das Ressourcenprofil zu packen, resultiert der Name (PACK) für das Verfahren.

Um die einzelnen Vorgänge in das Ressourcenprofil einzuplanen, muss man zuerst wieder die Priorität, nach der die Vorgänge ausgewählt werden, be- stimmen. Im Artikel von Harris3 wurde dafür folgende Reihenfolge be- nutzt: Zuerst wird die GRD-Regel (10) zur Bestimmung der Prioritätsre- gelwerte verwendet, so dass zuerst die Vorgänge mit dem größten Ressour- cenverbrauch eingeplant werden. Gesetzt den Fall, dass mehrere Vorgänge nach dieser Regel gleichwertig sind, wird eine zweite Prioritätsregel verwen- det. Hierbei hat sich die MST-Regel (13) bewährt, die die Vorgänge nach steigenden T F -Werten einplant. Gibt es hiernach immer noch keine eindeu- tige Auswahl, tritt eine dritte Prioritätsregel in Kraft, die die Vorgänge nach dem Sequence-Step sortiert. Der Sequence-Step ist dabei die Position des Vorgangs im Netzwerk (siehe Abbildung 8). Selbst nach diesen drei Regeln kann es noch Vorgänge geben, die weiterhin dieselbe Priorität haben. Da es jedoch kein weiteres logisches Entscheidungskriterium gibt, wählt man nun die Vorgänge anhand ihrer Vorgangsnummer aus. Sind die Prioritäten für die Vorgänge bestimmt, werden sie in einer Warteschlange hintereinander nach ihrer Priorität angeordnet.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 8: Netzplan mit drei Sequence-Step Stufen

Wenn ein Vorgang eingeplant wird, muss zusätzlich die Strafe min∑ RS(j) für den vorausgehenden und nachfolgenden Vorgang an allen möglichen Ein- planungszeitpunkten dieser Vorgänge, unter Einhaltung der Zeitrestriktio- nen, berechnet werden. Diese Strafe ergibt sich aus der minimalen Summe des Ressourcenprofils über die möglichen Einplanungspositionen des Vor- gangs. Anschließend ermittelt man die Gesamtstrafe durch Aufsummieren der einzelnen Strafen der Vorgänger, Nachfolger und des einzuplanenden Vorgangs und positioniert den Vorgang an der Position mit der minima- len Gesamtstrafe, damit der Nivellierungseffekt größtmöglich wird. Somit haben die Vorgänger und Nachfolger Einfluss auf die Positionierung des Vorgangs, da die Einplanungsposition auch die späteren Einplanungspositio- nen der Vorgänger und Nachfolger beeinflussen kann. Sollte diese Auswahl aufgrund verschiedener Positionen mit einer minimalen Gesamtstrafe jedoch nicht eindeutig sein, so entscheidet man sich für die früheste Position. Dies hat den Effekt, dass der Total-Float der folgenden Vorgänge so wenig wie möglich eingeschränkt wird.

Sobald der Vorgang fest eingeplant ist erweitert man nun das Ressourcenprofil um diesen Vorgang, indem der Ressourcenverbrauch in dem zugewiesenen Abschnitt durch Addition der Ressourcen des eingeplanten Vorgangs entsprechend angepasst wird.

Zur Berechnung der Einplanungspositionen, des Ressourcenverbrauchs und somit der bestmöglichen Einplanung der Vorgänge bedient sich das PACKVerfahren einer Anordnungsmatrix (vgl. Tabelle 4 und 5) . Die Zeilen der Matrix enthalten dabei die Vorgänge. Die Spalten repräsentieren die einzelnen Tage des Projektes. Die Zellen der Matrix enthalten somit die speziellen Informationen über die Vorgänge.

Dabei gibt es drei mögliche Varianten.

0 : Der Vorgang kann hier nicht ausgeführt werden.

1 : Der Vorgang muss hier ausgeführt werden. (vgl. Basisintervall)

2 : DerVorgangkannhierausgeführtwerden.

Wenn ein Vorgang fest einplant wird, müssen zwangsläufig auch die Zellen in der Reihe des Vorgangs verändert werden. In den Zellen, in denen der Vor- gang ausgeführt werden soll, werden die Zweien durch Einsen ersetzt. Die Zellen, in denen der Vorgang dann nicht ausgeführt wird, ändert man der- art, dass aus den Zweien Nullen werden. Da sich das feste Einplanen eines Vorgangs durch die Zeitrestriktionen auch auf andere Vorgänge auswirkt und gegebenenfalls deren Total-Float einschränkt, führt man eine weitere Spal- te AC (assignment control) ein. Der Wert dieser Spalte ergibt sich aus dem Total-Float des ES-Schedules. Wird demnach ein Vorgang eingeplant, so verringert sich der AC-Wert auf Null, da keine Zuordnungsmöglichkeiten für den Vorgang mehr existieren. Da vorhergehende bzw. nachfolgende Vorgänge des fest eingeplanten Vorgangs durch seine Position und die Zeitrestriktio- nen gebunden sind, muss man weiterhin darauf achten, deren AC-Werte nach der Einplanung des Vorgangs anzupassen, da nun nicht mehr alle möglichen Ausführungszeitpunkte die Beschränkungen erfüllen.

Eine weitere Kontrollvariable, die hinzugefügt wird, ist JAC (joint assignment control), die angibt, ob ein Vorgang bereits einer bestimmten Position zugeordnet ist. Diese wird dazu verwendet, um vorhergehende und nachfolgende Vorgänge zu bestimmen, wenn ein Vorgang fest eingeplant ist. Der ursprüngliche JAC-Wert eines Vorgangs beträgt somit 1 und nach dem Einplanen des Vorgangs wird dieser Wert zu 0 aktualisiert.

Um die Vorgehensweise des PACK-Verfahrens zu veranschaulichen, wird wie in den beiden vorhergehenden Beispielen, das Resourcennivellierungsproblem anhand eines Beispiels erklärt. Hierzu setzt man erneut den MPM-Netzplan aus Abbildung 3 ein.

Beispiel:

In diesem Beispiel wird versucht, für den bekannten MPM-Netzplan aus Abbildung 3 mittels PACK-Heuristik eine gute Lösung zu finden. Am Anfang erstellt man eine Tabelle (Tabelle 2) mit den zugehörigen ESi, LSi, T Fi, pi und ri Werten.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2: ESi, LSi, T Fi, pi und ri-Werte für i = 0, ..., 10

Als nächstes wird die Anordnungsmatrix (Tabelle 4 und 5) erstellt. Die erste Spalte der Anordnungsmatrix enthält den Sequence-Step (SS) und die zwei- te Spalte den Ressourcenverbrauch (R) des Vorgangs. In der dritten Spalte steht der assignment-control Wert (AC), gefolgt von dem joint-assignment- control Wert (JAC), der Vorgangsdauer (pi) und der Vorgangsnummer (i). Die folgenden Spalten, rechts der doppelten Linie, stehen für die einzelnen Tage, die das Projekt in Anspruch nimmt. In den Zeilen der Anordnungsma- trix befinden sich nun die Daten der einzelnen Vorgänge. Wie nachfolgend ersichtlich ist wurden die Zeilen bei jedem Sequence-Step durch doppelte Linien getrennt, was lediglich der besseren Übersicht dient.

Für jeden Vorgang werden zunächst die Anfangswerte eingetragen, die aus dem Netzplan in Abbildung 3 und der Tabelle 2 bestimmt werden. Die JAC- Werte haben anfangs für alle Vorgänge den Wert 1, da es keine kritischen Vorgänge gibt. Die Spalten der Tage werden mit Einsen und Zweien auf- gefüllt, je nachdem, in welchem Zeitraum ein Vorgang aktiv sein kann und ob er fast-kritisch oder nicht-kritisch ist. Die Spalten, die weder Einsen noch Zweien enthalten, zeigen Nullen, die der Übersichtlichkeit halber weggelassen werden. Die erste Zeile unter den einzelnen Vorgängen enthält die aktuellen Koordinatenwerte RS(j) des Diagramms. Das Diagramm ist anfangs leer, da bisher kein Vorgang eingeplant ist. Die Werte sind daher zu Beginn alle 0. Als nächstes stellt man anhand der Werte von R, T Fi und SS eine Ablauflis- te auf, die die Reihenfolge angibt, in der die einzelnen Vorgänge eingeplant werden. Das erste Kriterium ist der Ressourcenverbrauch (R) des Vorgangs, der abfallend sortiert wird. Das zweite Kriterium ist der T F -Wert, der auf- steigend sortiert wird. Existieren weiterhin Uneindeutigkeiten wird als drit- tes Kriterium der Sequence-Step (SS) benutzt, der genau wie der Ressour- cenverbrauch in absteigender Reihenfolge sortiert wird. Tabelle 3 stellt die Ablaufliste für dieses Beispiel dar. Zur Übersichtlichkeit wurden die einzel- nen Abstufungen beim Ressourcenverbrauch mit doppelten Linien deutlich kenntlich gemacht.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3: Ablaufliste des Beispiels

Somit ist Vorgang 7 das erste Element in der Liste und wird im ersten Durchgang zum Einplanen ausgewählt. Er hat einen Ressourcenverbrauch von 4, einen AC-Wert von 5 und eine Dauer von 4 Tagen.

[...]

Ende der Leseprobe aus 154 Seiten

Details

Titel
Multi-Start-Verfahren zur Lösung von Ressourcennivellierungsproblemen
Hochschule
Technische Universität Clausthal  (Institut für Wirtschaftswissenschaft)
Note
2,3
Autor
Jahr
2007
Seiten
154
Katalognummer
V88683
ISBN (eBook)
9783638030328
ISBN (Buch)
9783638928366
Dateigröße
1085 KB
Sprache
Deutsch
Schlagworte
Multi-Start-Verfahren, Lösung, Ressourcennivellierungsproblemen
Arbeit zitieren
Dipl.-Wirt.-Inf. Johannes Dirk (Autor), 2007, Multi-Start-Verfahren zur Lösung von Ressourcennivellierungsproblemen, München, GRIN Verlag, https://www.grin.com/document/88683

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Multi-Start-Verfahren zur Lösung von Ressourcennivellierungsproblemen



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden