Modelle und Verfahren für Time-Cost Trade-Off Probleme
©2013
Masterarbeit
100 Seiten
Zusammenfassung
Unsere erfahrenen Projektleiter haben heutzutage ernsthafte Bedenken, ob nicht jedes Projekt ein Misserfolg werden könnte. Um einen Misserfolg vermeiden zu können, sollte die Projektplanung so gefördert werden, dass das Projekt zum richtigen Zeitpunkt in der richtigen Qualität und zu den richtigen Kosten abgeschlossen wird. Wir müssen uns die Frage stellen, wie eine Abwägung oder ein sog. Trade-Off zwischen diesen gegenläufig voneinander abhängigen Zielgrößen, d.h. zwischen Zeit, Qualität und Kosten, in einem Projekt ermöglicht wird. Eine Abwägung zwischen allen konkurrierenden Zielgrößen, vor allem zwischen Zeit und Kosten eines Projektes - in der Literatur Time-Cost Trade-Off genannt - ist dann möglich, wenn in der frühen Phase der Planung zugehörige Probleme erkannt bzw. definiert, modelliert und die entsprechenden Lösungsansätze dafür repräsentiert werden.
Ein Time-Cost Trade-Off Problem (TCTP) verfolgt das Ziel, die Zielfunktion des betrachteten Problems zu optimieren, sodass die Projektdauer- bzw. Budgetrestriktionen nicht überschritten werden. Im Allgemein lassen sich TCTP in zwei Arten unterteilen, nämlich Deadline und Budget Problem. Beim Deadline Problem sind die Vorgangsdauer so festzulegen, dass das Projektende spätestens zum Zeitpunkt der Deadline eintritt und die aus der Projektdurchführung resultierenden Kosten minimiert werden. Beim Budget Problem ist die Minimierung der Projektdauer angestrebt ist, während die resultierenden Kosten das beschränkte Budget nicht überschreiten dürfen.
Die vorliegende Arbeit beschäftigt sich mit Modellen und Verfahren für Time-Cost Trade-Off Probleme. In diesem Zusammenhang soll diese Arbeit zunächst die Grundlagen der Projektplanung zum besseren Verständnis eines Planungsproblems schaffen. Darauf aufbauend werden dann Planungsprobleme dargestellt und es findet in Bezug auf die vorgestellten Time-Cost Trade-Off Probleme eine Präsentation der linearen bzw. nichtlinearen Kosten-Zeit Funktionen statt.
Ein Time-Cost Trade-Off Problem (TCTP) verfolgt das Ziel, die Zielfunktion des betrachteten Problems zu optimieren, sodass die Projektdauer- bzw. Budgetrestriktionen nicht überschritten werden. Im Allgemein lassen sich TCTP in zwei Arten unterteilen, nämlich Deadline und Budget Problem. Beim Deadline Problem sind die Vorgangsdauer so festzulegen, dass das Projektende spätestens zum Zeitpunkt der Deadline eintritt und die aus der Projektdurchführung resultierenden Kosten minimiert werden. Beim Budget Problem ist die Minimierung der Projektdauer angestrebt ist, während die resultierenden Kosten das beschränkte Budget nicht überschreiten dürfen.
Die vorliegende Arbeit beschäftigt sich mit Modellen und Verfahren für Time-Cost Trade-Off Probleme. In diesem Zusammenhang soll diese Arbeit zunächst die Grundlagen der Projektplanung zum besseren Verständnis eines Planungsproblems schaffen. Darauf aufbauend werden dann Planungsprobleme dargestellt und es findet in Bezug auf die vorgestellten Time-Cost Trade-Off Probleme eine Präsentation der linearen bzw. nichtlinearen Kosten-Zeit Funktionen statt.
Leseprobe
Inhaltsverzeichnis
2
4.7 Anwendung des Genetischen Algorithmus für TCTP ... 83
Fazit und Ausblick... 85
Anhang A: Umsetzung der TCTP im MATLAB ... 88
Anhang B: Umsetzung der TCTP im Excel Solver ... 91
Anhang C: Umsetzung des GA für TCTP im MATLAB ... 92
Abbildungsverzeichnis ... 94
Tabellenverzeichnis ... 95
Symbolverzeichnis ... 96
Literaturverzeichnis...99
3
Einleitung
Einleitung
Unsere erfahrenen Projektleiter haben heutzutage ernsthafte Bedenken darüber, ob nicht jedes
Projekt ein Misserfolgt werden könnte. Um einen Misserfolg vermeiden zu können, sollte die
Projektplanung so gefördert wird, dass das Projekt zum richtigen Zeitpunkt in der richtigen
Qualität und zu den richtigen Kosten abgeschlossen wird. Wir müssen uns die Frage stellen,
wie eine Abwägung oder ein sogennanter Trade-Off zwischen diesen gegenläufig voneinander
abhängigen Zielgrößen, d.h. zwischen Zeit, Qualität und Kosten in einem Projekt ermöglicht
wird. Eine Abwägung zwischen allen konkurrierenden Zielgrößen, vor allem zwischen Zeit
und Kosten eines Projektes, die in der Litaratur Time-Cost Trade-Off gennant, ist dann
möglich, wenn in der frühen Phase der Planung zugehörige Probleme erkannt bzw. definiert,
modelliert und die entsprechenden Lösungsansätze dafür repräsentiert werden.
Ein Time-Cost Trade-Off Problem (TCTP) verfolgt das Ziel, die Zielfunktion des
betrachteten Problems zu optimieren, sodass die Projektdauer- bzw. Budgetrestriktion nicht
überschritten werden. Im Allgemein lassen sich TCTP in zwei Arten unterteilen, nämlich
Deadline und Budget Problem. Beim Deadline Problem sind die Vorgangsdauern so
festzulegen, dass das Projektende spätestens zum Zeitpunkt des Projektendtermins eintritt und
die aus der Projektdurchführung resultierenden Kosten minimiert werden. Beim Budget
Problem ist die Minimierung der Projektdauer angestrebt ist, während die resultierenden
Kosten das beschränkte Budget B nicht überschreiten dürfen.
Die vorliegende Arbeit beschäftigt sich mit Modellen und Verfahren für Time-Cost Trade-
Off Probleme. In diesem Zusammenhang soll diese Arbeit zunächst die Grundlagen der
Projektplanung zum besseren Verständnis eines Planungsproblems schaffen. Im ersten
Kapitel wird daher die unterschiedlichen Netzpläne sowie die Netzplantechniken für die
Einführung in die Projektplanungsprobleme erläutert. Anschließend wird im zweiten Kapitel
ein Überblick über einige der wichtigsten in der Literatur anzutreffenden Probleme im
Rahmen einer Klassifikation der Planungsprobleme gegeben. Es werden hierbei auf eine
allgemeine Beschreibung der vorgestellten Planungsprobleme eingegangen und zwischen den
No Trade-Off und Trade-Off Problemen sowie zwischen den Time-Cost, Time-Resource und
den Resource-Resource Trade-Off Problemen differenziert. Im Bezug auf die vorgestellten
Time-Cost Trade-Off Probleme werden im dritten Kapitel die lineare bzw. nichtlineare
Kosten-Zeit Funktionen behandelt. In der Literatur zum TCTP findet man lineare, konvexe,
4
konkave und diskrete Kosten-Zeit Funktionen für die Vorgänge eines Projektes. Im Kapitel 4
werden dann die in der Literatur zu TCTP vorliegenden Lösungsverfahren entsprechend der
im Kapitel 3 beschriebenen Kosten-Zeit Funktionen erörtert.
Ein Überblick zu den wesentlichen Ergebnissen und ein Ausblick auf weiterführende
Forschungsmöglichkeiten schließen die Arbeit.
5
1 Projektmanagement Grundlagen und
Begriffe
1.1 Grundbegriffe des Projektmanagements
Im Lauf der vergangenen Jahrzehnte hat die Bedeutung von Projektmanagement und
Projektplanung sowie deren Rollen bei der Projektdurchführung zugenommen. Jedes Projekt,
das durch seinen eigenen Lebenszyklus läuft, ist in der Gegenwart ohne Projektplanung
sinnlos. In der Literatur zum Projektmanagement findet man dementsprechend, dass eine
phasenorientierte Betrachtung des Projektlebenszyklus von besonderer Bedeutung für die
Projektplanung ist, wobei das Projektmanagement im Rahmen der Managementaufgabe in
Phasen der Projektkonzeption, Projektspezifikation, Projektplanung und Projektrealisation
gegliedert ist (vgl. Zimmermann et al., 2010, S.9). Bevor der Begriff der Projektplanung
umfassend erläutert wird, fange ich zunächst zum besseren Verständnis mit Definitionen von
Projekt bzw. Projektmanagement an.
Definition 1.1 (Projektmanagement) Die DIN 69901 definiert Projektmanagement als
Gesamtheit von Führungsaufgaben, -organisation, -techniken und -mittel für die Abwicklung
eines Projekts. Im Allgemein ist Projektmanagement die Anwendung von Wissen, Können,
Werkzeugen und Techniken auf Projektaktivitäten, um Projektanforderungen zu erfüllen (vgl.
Duncan, 1996, S.6).
Die Definition des Projektmanagements wird jedoch mit folgendem Projektbegriff ergänzt.
Definition 1.2 (Projekt) Im Handbuch Projektmanagement präsentieren Kuster et al. (2011)
den Projektbegriff als ,,ein einmaliges, bereichsübergreifendes Vorhaben, das zeitlich
begrenzt, zielgerichtet, interdisziplinär und so wichtig, kritisch und dringend ist, dass es nicht
einfach in der bestehenden Linienorganisation bearbeitet werden kann, sondern besondere
organisatorische Vorkehrungen getroffen werden müssen" (Kuster et al., 2011 S.5).
Im Bezug auf die oben gennanten Eigenschaften des Projekts, besonders Zielorientierung
des Projekts, veranschaulicht Abbildung 1 die parallel zu erreichenden Projektziele. Diese
generellen konkurrierenden Projektzielgrößen werden in fast allen Publikationen über
Projektmanagement als Magisches Dreieck des Projektmanagements dargestellt. Bei der
Dreieckdarstellung (vgl. Fischer, 2008, S.25) nimmt man das Qualitäts- und Quantitätsziel
zusammen.
6
Abbildung 1. Magisches Dreieck im Projektmanagement
Grafik Quelle:
http://www.realtime-solutions.de
Wie Abbildung 1 dargestellt, existieren zwischen den konkurrierenden Zielgrößen Zeit,
Kosten und Qualität unverzichtbare wechselseitige Abhängigkeiten. Sind grundsätzlich
geringere Kosten für das Projekt wichtig, werden i.d.R keine höhere Qualität erwartet werden.
Will man das Projekt so früh wie möglich beenden, muss man auf geringe Projektkosten
verzichten. Wollen wir aber eine nachhaltige Projektplanung entwerfen, dann müssen wir die
Zielgrößen untrennbar voneinander betrachten, d.h um einen Projekterfolg zu erzielen,
müssen alle Zielgrößen im Gleichgewicht gehalten werden.
Eine Balancierung zwischen allen Zielgrößen (vor allem zwischen Dauer und Kosten eines
Projekts) ist dann möglich, wenn in der frühen Phase der Planung zugehörige Probleme
erkannt bzw. definiert, modelliert und entsprechende Lösungsansätze dafür repräsentiert
werden. Hier handelt es sich um die Aufgaben der Projektplanung, die auf die Struktur-, Zeit-,
Ressourcen- und Kostenanalyse bezogen sind. Daraus ergeben sich die für die Ausführung
eines Projekts benötigten Informationen, wie die Zeitbeziehungen zwischen Projektvorgänge,
die Dauer der Projektvorgänge, die erforderlichen Ressourcen sowie die mit der
Durchführung der Vorgänge verbundenen Kosten. Nach der Ermittlung der benötigten
Informationen können die Probleme graphisch modelliert werden und dadurch einen
Überblick über das Projekt gegeben werden. Anschließend können durch die
Netzplantechniken (s. Abschnitt 4.1) weitere Informationen wie die frühest- und
spätestmöglichen Start- und Endzeitpunkte sowie Pufferzeiten zur Zeit- bzw. Terminplanung
ermittelt werden.
7
1.2 Grundlagen der Projektplanung
Jedes Projekt besteht aus verschiedenartigen Teilprojekten, Unterprojekten, Arbeitspaketen
sowie Projektvorgängen, die im Rahmen einer Strukturanalyse identifiziert werden können.
Ein Projekt wird durch Vorgänge, Ereignisse sowie Zeitbeziehungen charakterisiert.
Defnition 1.3 (Vorgang) ,,Bei den Vorgängen eines Projekts handelt es sich um
zeitbeanspruchende Geschehen mit ausgezeichneten Start- und Endereignissen, bei deren
Ausführung i.d.R. Ressourcen (z.B. Arbeitskräfte, Maschinen, Verbrauchsgüter) ge- oder
verbraucht und Kosten verursacht werden" (Zimmermann et al., 2010, S.44).
Wenn z.B. die Erstellung einer CAD-Zeichnung als ein Vorgang definiert wird, werden ein
Konstrukteur als Arbeitskraft, ein PC mit CAD-Programm als Betriebsmittel sowie Papiere
als Verbrauchsgüter zur Realisierung dieses Vorgangs in einem bestimmten Zeitintervall
beansprucht. Jeder Vorgang wird durch Ereignisse und Ausführungsdauer charakterisiert.
Definition 1.4 (Ereignis) ,,Ein Ereignis kennzeichnet das Erreichen eines bestimmten
Projektzustands" (Zimmermann et al., 2010, S.46).
Wenn z.B. der Entwurf einer CAD-Zeichnung zum Zeitpunkt t beginnt oder abgeschlossen
ist, dann handelt es sich um Ereignisse. Hierbei besitzt dieser Vorgang (Erstellung einer
CAD-Zeichnung) zwei Ereignisse, nämlich ein Start- und ein Endereignis.
Definition 1.5 (Meilensteine) ,,Bestimmte Ereignisse, die von besonderer Wichtigkeit für ein
Projekt sind, werden auch als Meilsteine bezeichnet." (Scholl, 2001, S.226)
Neben den Vorgängen und den Ereignissen eines Projekts spielen die allgemeinen
Zeitbeziehungen zwischen Vorgängen eine wichtige Rolle. Eine Zeitbeziehung wird durch
eine Anordnungsbeziehung und einen Zeitabstand gekennzeichnet. Unter Anordnungs-
beziehung versteht man im Projektmanagement die Art und Weise, wie einzelne Vorgänge
aus der Projektstruktur mit- und zueinander in Beziehung stehen. Die Anordnungs-
beziehungen zwischen einzelnen Projektvorgängen resultieren aus logischen, technologischen
oder ablauforganisatorischen Gründe, z.B. der Mechaniker kann sofort mit dem Aufbau eines
Prototyps anfangen, sobald die dazugehörige CAD-Zeichnung durch den Konstrukteur
beendet ist. Hier wird der Vorgang ,,Aufbau eines Prototyps" als Nachfolger von Vorgang
,,Erstellung der CAD-Zeichnung" bezeichnet. Analog wird Vorgang ,,Erstellung der CAD-
Zeichnung als Vorgänger von Vorgang ,,Aufbau eines Prototyps" angesehen.
8
Durch die Verknüpfung zwischen zwei Vorgängen i und j können die vorliegenden
Anordnungsbeziehungen zwischen Vorgängen modelliert werden. Daher soll bereits bestimmt
werden, welches Start- oder Endereignis eines Vorgangs i mit welchem Start- oder
Endereignis seines Nachfolgers j verbunden werden soll. Somit lassen sich insgesamt in
Tabelle 1 vier verschiedene Arten von Verknüpfungstypen (Anordnungsbeziehungen)
erkennen. Die linke Seite jedes quadratischen Knotens (Vorgang) wird hier als das
Startereignis und die rechte Seite als das Endereignis des Vorgangs bezeichnet (vgl.
Zimmermann et al., 2010, S.46).
Tabelle 1. Anordnungsbeziehungen zwischen zwei Vorgängen
i und j
Verknüpfungstyp
Schematischer Verknüpfungstyp
Bemerkung
Ende-Start (es)
i
j
es
Nach dem Ende des Vorgangs i
kann Vorgang j gestartet werden
Start-Start (ss)
i
j
ss
Nach dem Start des Vorgangs i
kann Vorgang j gestartet werden
Start-Ende (se)
i
j
se
Nach dem Start des Vorgangs i
kann Vorgang j beendet werden
Ende-Ende (ee)
i
j
ee
Nach dem Ende des Vorgangs i
kann Vorgang j beendet werden
Außer Anordnungsbeziehungen (ss, se, es, ee) haben die zeitlichen Abstände besondere
Bedeutung für eine Zeitbeziehung zwischen Vorgängen. Es ist zu erwähnen, dass durch die
zeitlichen Abstände die Terminrestriktionen oder sonstige ablauforganisatorischen
Gegebenheiten berücksichtigt werden können. Es werden zwei Arten von Zeitabständen
betrachtet, nämlich Mindest- und Höchstabstände.
Die zeitlichen Mindest- und Höchstabstände
(
,
) kennzeichnen zeitliche
Abstände, die beim Mindestabstand nicht unterschritten und beim Höchstabstand nicht
überschritten werden dürfen. Durch die Zeitabstände können die frühesten oder spätesten
Start- bzw. Endzeitpunkte einzelner Vorgänge bestimmt werden. Durch die Kombination der
Zeitabstände und der Anordnungsbeziehungen entstehen insgesamt acht verschiedene Arten
von Zeitbeziehungen, die in Tabelle 2 zusammengefasst sind (vgl. Zimmermann et al., 2010,
S.47):
9
Tabelle 2. Zeitbeziehungen zwischen zwei Vorgängen
i und j
Symbolzeichen
Bemerkung Beschreibung
Mindestabstand zwischen i und j
vom Typ Ende-Start
Vorgang j kann frühestens
Zeiteinheiten (ZE)
nach dem Ende des Vorgangs
i beginnen.
Mindestabstand zwischen i und j
vom Typ Start-Start
Vorgang j kann frühestens
Zeiteinheiten (ZE)
nach dem Start des Vorgangs
i beginnen.
Mindestabstand zwischen i und j
vom Typ Start-Ende
Vorgang j kann frühestens
Zeiteinheiten (ZE)
nach dem Start des Vorgangs
i beendet werden.
Mindestabstand zwischen i und j
vom Typ Ende-Ende
Vorgang j kann frühestens
Zeiteinheiten (ZE)
nach dem Ende des Vorgangs
i beendet werden.
Höchstabstand zwischen i und j
vom Typ Ende-Start
Vorgang j kann spätestens
Zeiteinheiten (ZE)
nach dem Ende des Vorgangs i beginnen.
Höchstabstand zwischen i und j
vom Typ Start-Start
Vorgang j kann spätestens
Zeiteinheiten (ZE)
nach dem Start des Vorgangs
i beginnen.
Höchstabstand zwischen i und j
vom Typ Start-Ende
Vorgang j kann spätestens
Zeiteinheiten (ZE)
nach dem Start des Vorgangs i beendet werden.
Höchstabstand zwischen i und j
vom Typ Ende-Ende
Vorgang j kann spätestens
Zeiteinheiten (ZE)
nach dem Ende des Vorgangs i beendet werden.
Grundsätzlich ist ein zeitlicher Abstand nach unten bzw. nach oben beschränkt. Diese
Beschränkungen werden durch Mindestabstand als untere Schranke und durch Höchstabstand
als obere Schranke charakterisiert. Mit anderen Worten ermöglichen die Zeitabstände einen
Zeitintervall für die Vorgänge, in dem die Start- oder Endzeitpunkte der Vorgänge eintreten
können. Werden und als die Start- bzw. Endzeitpunkt des Vorgangs i definiert, werden
zusammenfassend im Folgenden die Zeiträume, in den der Vorgang j als Nachfolger von
Vorgang i begonnen bzw. abgeschlossen werden darf, gegeben (vgl. De Reyck und Herroelen,
1997, S.4).
+
+
(1.1)
+
+
(1.2)
+
+
(1.3)
+
+
(1.4)
10
Ein Zeitintervall kann jedoch in einem Fall nur einen Zeitpunkt repräsentieren. Dies gilt,
wenn ein Zeitabstand zwischen zwei Vorgängen i und j exakt eingehalten werden soll. Er
kann durch Einführung einer Gleichung
=
= , {
,
,
,
}
realisiert werden (Zimmermann et al., 2010, S.48).
Mit der Identifizierung der Vorgänge und der Ereignisse bzw. mit der Bestimmung der
Zeitbeziehungen ist eine Projektplanung noch nicht abgeschlossen, sondern es sind bisher nur
die Voraussetzungen für die Erledigung weiterer Planungsaufgaben erfüllt. Bezüglich der
Grundlagen der Projektplanung werden im Folgenden zunächst die vorliegenden Netzpläne
und weiterhin aufbauend auf den Neztplänen die deterministischen Netzplantechniken, die
häufig bei Time-Cost Trade-Off Probleme angewendet werden, beschrieben.
11
1.3 Netzpläne in der Projektplanung
Zur graphischen Darstellung eines Projekts ist ein Netzplan von besonderer Bedeutung. Die
theoretischen Grundlagen der Netzpläne basieren auf der Graphentheorie. Bei einem Graph
sind die Menge von Knoten als Punkte (Kreise oder Rechtecke) durch Kanten als
Verbindungslinien miteinander verbunden. Dadurch kann man bei einem Projekt die
dazugehörigen Vorgänge und Ereignisse sowie deren Beziehungen miteinander mit Hilfe
eines Netzplans darstellen.
Im Folgenden wird zwei verschiedene Formen eines Netzplans betrachtet: Vorgangs-
Knoten-Netzwerke und Vorgangs-Pfeil-Netzwerke.
1.3.1 Vorgangs-Knoten-Netzwerke (VKN)
Bei Vorgangs-Knoten-Netwerke entspricht jedem Projektvorgang im Netzplan ein Knoten.
Ein Pfeil kennzeichnet eine Anordnungsbeziehung zwischen zwei aufeinander liegenden
Vorgängen. Im Vorgangs-Knoten-Netzwerk dürfen zwei Knoten (Vorgänge) nur durch einen
Pfeil verbunden sein. Die Bewertung der Pfeile entspricht dem zeitlichen Abstand zwischen
Vorgängen. In Abbildung 2 ist ein Vorgangs-Knoten-Netzwerk mit vier Vorgängen und
unterschiedlichen Anordnungsbeziehungen
(
,
,
,
) dargestellt.
1
3
2
4
3 ZE
5 ZE
3 ZE
2 ZE
Abbildung 2. Ein Vorgangs-Knoten-Netzwerk
Eine der Netzplantechniken, die auf Vorgangs-Knoten-Netzwerken basiert, heißt MPM-
Netzplantechnik (vgl. Abschnitt 1.4.1).
1.3.2 Vorgangs-Pfeil-Netzwerke (VPN)
Bei Vorgangs-Pfeil-Netzwerken werden die Vorgänge durch Pfeile dargestellt, während die
Ereignisse durch Knoten repräsentiert sind. Durch einen gerichteten Pfeil können zwei
Knoten miteinander verbunden werden. Mit anderen Worten besitzt jeder Vorgang zwei
Ereignisse, ein Ereignis als Knoten am Amfang des Vorgangs, dass den Start des Vorgangs
12
repräsentiert (Startereignis), während sich ein anderer Knoten am Ende des Vorgangs
befindet und den Abschluss des Vorgangs kennzeichnet (Endereignis).
Die Bewertung eines Pfeils entspricht gerade der Dauer des zugehörigen Vorgangs
(Vorgangsdauer). An jeden Pfeil des Vorgangs-Pfeil-Netzwerks werden auch die
Vorgangsnummer geschrieben. Eine der Netzplantechniken, die auf Vorgangs-Pfeil-Netzwerk
basiert ist, heißt die CPM-Netzplantechnik (vgl. Abschnitt 1.4.2).
Abbildung 3 veranschaulicht ein Vorgangs-Pfeil-Netzwerk mit fünf Vorgängen und vier
Ereignissen.
Abbildung 3. Ein Vorgangs-Pfeil-Netzwerk
Wir wissen, dass zwischen je zwei Knoten in einem Netzplan entweder ein Pfeil oder keine
Verbindung existiert. Daher kann man die Beziehungen zwischen Knoten als binäre
Beziehungen im Rahmen einer Adjazenzmatrix definieren, sodass ,,1" eine Verbindung von
einem Knoten
zu Knoten repräsentiert, während Null keine Verbindung zwischen zwei
Knoten kennzeichnet. Ein Netzplan kann demnach durch eine
× -Matrix repräsentiert
werden, wobei n die Anzahl der Knoten ist. Wenn z.B. von Knoten i zum Knoten
eine
Beziehung existiert, wird in die i-ten Zeile bei der Spalte j eine 1 eingetragen, ansonsten eine
Null (vgl. Elmaghraby 1977, S.5). Abbildung 4 stellt eine Adjazenzmatrix des Vorgangs-
Pfeil-Netzwerks aus Abbildung 3 dar.
Abbildung 4. Die Adjazenzmatrix für die Abbildung 3
13
1.4 Netzplantechniken
Wie bereits erwähnt, soll das Projekt vor der Anwendung der Netzplantechnik zunächst im
Rahmen einer Strukturanalyse systematisch in Teilprojekte, Unterprojekte, Arbeitspakete und
Projektvorgänge zerlegt werden. Zwischen einzelnen Projektvorgängen existieren logisch
bzw. technologisch bedingte Zeitbeziehungen (vgl. Abschnitt 1.2). Ferner werden die
Ausführungsdauern, benötigte Mengen an Ressourcen und die Kosten der einzelnen
Vorgängen durch die Zeit-, Ressourcen- und Kostenanalyse bestimmt. Mit Hilfe von
Netzplantechniken kann jetzt eine Projektanalyse durchgeführt und den einzelnen
Projektvorgängen Informationen wie bspw. der frühest- und spätestmögliche Start- bzw.
Endzeitpunkt unter Berücksichtigung der Zeitbeziehungen sowie der vorhandenen
Ressourcenkapazitäten zugewiesen werden. Die frühest möglichen Start- und Endzeitpunkte
der Vorgänge bzw. der Ereignisse werden in einer Vorwärtsrechnung ermittelt, während die
spätest möglichen Start und Endzeitpunkte der Vorgänge bzw. der Ereignisse durch
Rückwärtsrechnung bestimmt werden. Zuletzt werden detaillierte Informationen über den
zeitlichen Ablauf des Projekts sowie über die resultierenden Ressourcenbedürfnisse und
Kosten ausgewertet, ob die zur Verfügung stehenden Ressourcenkapazitäten ausreichen, um
das betrachtete Projekt rechtzeitig fertigzustellen, oder bspw. mehrere Ressourcen eingesetzt
werden müssen, um den vorgegebenen Projektendtermin einhalten zu können (vgl.
Zimmermann et al., 2010, S.43).
Mit Hilfe der sogenannten Netzplantechnik hatte die Projektplanung Mitte der fünfziger
Jahre angefangen und verbreitete sich etwa ab 1955. Im Jahr 1956 entwickelte das Chemie-
unternehmen Du Pont de Nemours Co. die Critical Path Method (CPM) für die
Qualitätssicherung und Instandhaltung von Chemieanlagen. Die Program Evaluation and
Review Technique (PERT) wurde später im Jahr 1958 unter Leitung der US Navy für das
Polaris-Raketenprogramm entwickelt. Zugleich wurde die Metra Potential Method (MPM)
durch die französische Gruppe Metra entworfen. Heutzutage ist die Anwendung der
Netzplantechniken zur Durchführung komplexer Projekte, wie bspw. Schiffsbau,
Flugzeugbau, Anlagenbau usw. sehr nützlich (vgl. Berner et al., 2008, S.100). Im Bezug auf
das Thema dieser Arbeit werden im Folgenden zwei deterministische Netzplantechniken
MPM und CPM, die häufig bei Time-Cost Trade-Off Probleme angewendet werden,
betrachtet.
14
1.4.1 Metra Potential Methode (MPM)
Eine theorie- und praxisorientierte Netzplantechnik ist die Metra-Potential-Methode (MPM).
Aufbauend auf einem Vorgangs-Knoten-Netzwerk behandelt sie deterministische Angaben.
Jeder Projektvorgang ist im MPM-Netzplan einem Knoten zugeordnet, während die Pfeile die
zeitlichen Mindest- und Höchstabstände Start-Start-Beziehungen zwischen den Vorgängen
darstellen. Die Bewertung jedes Pfeils
entspricht dem zeitlichen Abstand zwischen zwei
Vorgängen i und j.
In einem MPM-Netzplan
= , ; werden die Menge aller Projektvorgänge (Knoten)
durch
{0,1, ... , ,
+ 1} mit ,
1 repräsentiert, wobei der Projektstart bzw. das
Projektende mit Ausführungsdauer Null durch Vorgang
0 und Vorgang + 1 gekenn-
zeichnet sind. Neben der Knotenmenge V sind die Pfeilmenge E mit zugehörigen
Bewertungen
für alle
,
spezifiziert.
Beim MPM-Netzplan wird angenommen, dass das Projekt zum Zeitpunkt Null beginnt.
Sei
der Startzeitpunkt eines Vorgangs i ist daher der Startzeitpunkt des fiktiven Projekt-
starts gleich Null, d.h.
= 0. Da alle anderen Projektvorgäge nach dem Projektstart
eintreten sollen, gilt demnach
0 für die Eintrittszeitpunkte aller Projektvorgänge.
Außerdem ist die Ausführungsdauer des letzten Projektvorgangs (der fiktive Vorgang des
Projektendes) gleich Null, dann bestimmt dessen Entrittzeitpunkt
gerade die
Projektdauer.
Zur Einhaltung des zeitlichen Mindest- bzw. Höchstabstandes zwischen zwei Vorgänge i
und j
(
,
) in einem MPM-Netzplan darf die Differenz zwischen den
Eintrittszeitpunkten der beiden Vorgänge beim Mindestabstand nicht kleiner als
Zeiteinheiten und beim Höchstabstand nicht größer als
Zeiteinheiten sein, d.h. hier
gilt (vgl. Abb. 5):
-
(1.5)
+
+
(1.6)
15
Abbildung 5. Zeitliche Abstände zwischen zwei Vorgängen
i und j
Wenn die Differenz
-
kleiner als die Dauer des Vorgangs i ist, dann liegt eine
Überlappung innerhalb des Zeitintervalls [ , min
+
,
+
] vor. Der Endzeitpunkt der
Überlappung wird durch
min
+
,
+
gewährleistet, d.h. mit dem Abschluss eines
Vorgangs i oder j wird auch die Überlappung beendet. Zur Beschränkung oder Vermeidung
einer Überlappung zwischen zwei Vorgängen müssen die entsprechenden zeitlichen Abstände
zwischen beiden Vorgängen eingehalten werden. Hingegen kann durch die Überlappungen
die Projektdauer verkürzt werden. Die Überlappung der Vorgänge könnte zusätzliche Kosten
für das Projekt verursachen.
Die zeitlichen Mindestabstände können zusätzlich zur Realisierung weiterer praktischer
Annahmen im MPM-Neztplan angewendet werden, z.B zur Einhaltung des zeitlichen
Mindestabstandes zwischen dem Projektstart und einem Vorgang aufgrund gegebener
Bereitstellungstermine, oder zur Einhaltung des zeitlichen Mindestabstandes zwischen einem
Vorgang und dem Projektende aufgrund gegebener Restriktionen.
Es ist auch zu erwähnen, dass in MPM-Netzplänen die zeitlichen Mindest- und
Höchstabstände ineinander umgerechnet werden können. Ein zeitlicher Mindestabstand
zwischen dem Beginn der Vorgänge i und j entspricht einem negativen zeitlichen
Höchstabstand zwischen dem Beginn der Vorgänge j und i, d.h.
= -
.
Ein Pfeil von Knoten i nach Knoten j mit der Bewertung
=
entspricht dem
zeitlichen Mindestabstand zwischen dem Beginn zweier Vorgänge i und j in MPM-
Netzplänen. Zur Visualisierung des zeitlichen Höchstabstandes zwischen dem Beginn zweier
Vorgänge i und j ist ein Pfeil von Knoten j nach Knoten i mit der Bewertung
=
=
-
hinzuzufügen. Durch die Einführung der Zeitbeziehungen im MPM-Netzplan können
16
Zyklen entstehen. Es dürfen jedoch keine Zyklen mit positiver Länge in einem MPM-
Netzplan existieren. Unter dem Begriff ,,Zyklus" in einem Netzplan wird ein in sich
geschlossener Weg verstanden, d.h eine Pfeilfolge mit demselben Start- und Endknoten. Ein
Weg liegt vor, wenn ein Pfeil oder mehrere aufeinander folgende Pfeile (Pfeilfolge), die von
einem Anfangsknoten ausgehen, über unterschiedliche Knoten den Endknoten erreichen.
Die Länge eines Weges in einem Netzplan hat besondere Bedeutung für Projekte. Ich
bezeichne mit
,
,
1 die Länge des Weges k zwischen Knoten 0 als Projektstart und
Knoten
+ 1 als Projektende. Durch die Ermittlung der Länge eines längsten Weges
zwischen 0 und
+ 1 (
,
) kann eine untere Schranke für die Projektdauer ermittelt
werden, d.h.
,
= max {
,
, ... ,
,
} . Die Länge eines Weges zwischen Knoten
0 und Knoten
+ 1 (
,
) wird durch die Summe aller Pfeilbewertungen auf diesem Weg
ermittelt.
Beispiel 1.1
Wir betrachten in Abbildung 6 einen MPM-Netzplan. Gesucht wird der früheste Projektend-
termin. Die Dauer des Projektstarts bzw. des Projektendes ist Null, d.h.
=
= 0.
Weg 1:
0,1,4, 6
,
= 0 + 3 + 6 = 9
Weg 2:
0,1,3, 5,6
,
= 0 + 3 + 5 + 5 = 13
Weg 3:
0,2, 5,6
,
= 0 + 6 + 5 = 11
,
= max
,
,
,
,
,
= max{9,13,11} = 13 ZE
Abbildung 6. Ein MPM-Netzplan
17
Zur Aufzählung aller Wege in einem Netzwerk kann man das vorliegende Netzwerk in Form
eines Baumes umstruktuieren. Jeder Knoten in der Baumstruktur repräsentiert den
zugehörigen Vorgang im MPM-Netzplan. Zum Aufbau der Baumstruktur liegt zunächst der
Anfangsknoten des Projekts (der Projektstart) an der Wurzel des Baumes. In der nächsten
Hierarchieebene liegen die unmmitelbaren Nachfolger vom Anfangsknoten. Für die nächsten
Ebenen müssen die unmittelbaren Nachfolger von den Knoten letzter Ebene hinzugefügt
werden. Dadurch entstehen die Äste. Man kann hier auf diese Art und Weise fortfahren, bis in
allen Ästen der Endknoten des Projekts erreicht wird (vgl. Abb. 7).
0
1
2
3
4
5
5
6
6
6
Abbildung 7. Die Baumstruktur eines Projekts
Mit
( ) wird die Menge der unmittelbaren Nachfolger von Knoten
in N, während
die Menge der unmittelbaren Vorgänger von Knoten i durch
( ) gekennzeichnet ist,
bezeichnet. Zum Beispiel sind Vorgang 3 und 4 die unmittelbaren Nachfolger von Knoten 1,
d.h.
(1) = {3,4}, während die Menge der unmittelbaren Vorgänge von Knoten 1 nur
Knoten 0 enthält, d.h.
(1) = {0}.
In der Literatur zur Netzplantechnik existieren jedoch weitere Algorithmen zur
Bestimmung der längsten Wege in einem Netzwerk. Einer der vorliegenden Algorithmen
heißt Label-Correcting-Algorithmus, der aufbauend auf dem Bellmanschen Optimalitäts-
prinzip zur Bestimmung längster Wege in MPM-Netzplänen angewendet werden kann. Eine
ausführliche Einführung ins Bellmanschen Optimalitätsprinzip bzw. in den Label-Correcting
Algorithmus geben Zimmermann et al. (2010).
Die Länge eines längsten Weges zwischen dem Anfangsknoten und dem Endknoten
entspricht der kürzesten Projektdauer des betrachteten Projektes. Mit anderen Worten kann
das Projekt frühestens nach der Abwicklung der längsten Pfeilfolge von Projektvorgängen
beendet werden. Ferner sind die Vorgänge eines Projektes durch die frühesten Start- bzw.
Endzeitpunkte (
,
) charakterisiert. Durch die Berechnung der Länge eines längsten
18
Weges zwischen dem Knoten 0 und Knoten i kann der früheste Startzeitpunkt
1
des
Vorgangs
{0} ermittelt werden, d.h.
=
. Da zur Ausführung jedes Vorgangs i
genau
Zeiteinheiten benötigt ist, ergibt sich daher der früheste Endzeitpunkt
2
eines
Vorgangs
aus dem frühesten Startzeitpunk von i zuzüglich seiner Vorgangsdauer ,
d.h.
=
+
.
Beispiel 1.2 (Fortsetzung von Beispiel 1.1)
Tabelle 3. Die frühesten Start- bzw. Endzeitpunkte der Vorgänge eines Projekts
i
0
1
2
3
4
5
6
0
0
0
3
3
8
13
0
3
6
5
6
5
0
0
3
6
8
9
13
13
Der früheste Startzeitpunkt eines Vorgangs i besagt, dass Vorgang i frühestens zum Zeitpunkt
gestartet werden kann, d.h. der zeitliche Mindestabstand zwischen Knoten 0 und Knoten i
entspricht dem frühesten Startzeitpunkt des Vorgangs i (
=
). Für den frühesten
Endzeitpunkt eines Vorgangs i gilt
=
. Für den spätesten Start- bzw. Endzeitpunkt
der Vorgänge werden die zeitlichen Höchstabstände repräsentiert werden.
Der späteste Startzeitpunkt
3
eines Vorgangs i besagt, dass Vorgang i spätestens zum
Zeitpunkt
gestartet werden darf. Mit anderen Worten entspricht der späteste Startzeitpunkt
eines Vorgangs i dem zeitlichen Höchstabstand zwischen dem Beginn des Vorgangs 0 und
Vorgangs i, d.h.
=
= -
= -
. Zusammenfassend ist der späteste
Startzeitpunkt
eines Vorgangs i gleich die negative Länge eines längsten Weges von
Knoten i nach Knoten 0. Aus dem spätesten Startzeitpunkt eines Vorgangs i zuzüglich der
Vorgangsdauer ergibt sich der späteste Endzeitpunkt
eines Vorgangs i (
=
+
).
Beispiel 1.3 (Fortsetzung von Beispiel 1.1)
Tabelle 4. Die spätesten Start- bzw. Endzeitpunkte der Vorgänge eines Projekts
i
0
1
2
3
4
5
6
0
0
2
3
7
8
13
0
3
6
5
6
5
0
0
3
8
8
13
13
13
Die Aufgaben der Zeit- bzw. Terminplanung eines Projekts ist nicht nur die Ermittlung der
frühest- und spätestmöglichen Start- oder Endzeitpunkte der Projektvorgänge, sondern
1
Earliest Start time
2
Earliest Completion time
3
Latest Start time
19
beinhalten auch die Bestimmung unterschiedlicher Pufferzeiten für alle Vorgänge. Wenn z.B.
ein Vorgang verzögert werden kann, ohne dass die maximale Projektdauer übrschritten wird,
dann handelt sich um die Pufferzeit. Im Allgemein lassen sich die Pufferzeiten in drei Arten
unterscheiden: Gesamtpufferzeit, freie Pufferzeit und freie Rückwärtspufferzeit.
Wenn sich ein Vorgang um die entsprechende Zeitspanne verzögert, ohne den Endtermin
des Projekts zu erhöhen, dann handelt sich um die Gesamtpufferzeit
4
eines Vorgangs
\{0}.
ergibt sich aus der Differenz zwischen dem spätesten und dem frühesten Start-
oder Endzeitpunkt eines Vorganges i, d.h.
=
-
=
-
.
Wenn sich ein Vorgang um die entsprechende Zeitspanne verzögert, ohne den frühest-
möglichen Beginn jedes Nachfolgers
,
( ) von Vorgang i nach vorne zu
verschieben, dann handelt sich um die freie Pufferzeit
5
eines Vorgangs i.
ergibt
sich aus der Differenz zwischen dem frühesten Zeitpunkt eines Nachfolgers j von Vorgang i
abzüglich des zeitlichen Mindestabstandes zwischen i und j, und dem frühesten Startzeitpunkt
des Vorgangs i, d.h.
= min
( )
-
-
.
Wenn sich ein Vorgang um die entsprechende Zeitspanne verzögert, ohne den spätest-
möglichen Beginn jedes Vorgängers
,
( ) von Vorgang i nach vorne zu
verschieben, dann handelt sich um die freie Rückwärtspufferzeit
6
eines Vorgangs i.
ergibt sich aus der Differenz zwischen dem spätesten Zeitpunkt des Vorgangs i und dem
spätesten Startzeitpunkt eines Vorgängers h von Vorgang i zuzüglich des zeitlichen
Mindestabstandes zwischen h und i, d.h.
=
- max
( )
(
+
).
Durch die Bestimmung der verschiedenen Pufferzeiten kann herausgefunden werden,
welche Vorgänge um die bestimmte Zeitspanne verzögert werdan dürfen, ohne den
Projektendtermin zu gefährden. Die Verzögerung der Vorgänge, die sich auf einem längsten
Weg von dem Projektstart (Knoten 0) nach Projektende (Knoten
+ 1) befinden,
beeinflussen das früheste Projektende
. Mit anderen Worten besitzen kritische
Vorgänge keine Zeitspanne, um die verzögert werden können. Für alle kritischen Vorgänge
gilt daher
=
=
= 0.
4
Total Float
5
Early Free Float
6
Late Free Float
20
Beispiel 1.4 (Fortsetzung von Beispiel 1.1)
Tabelle 5. Die verschiedenen Pufferzeiten eines Projekts
i
0
1
2
3
4
5
6
0
0
2
0
4
0
0
0
0
2
0
4
0
0
0
0
2
0
4
0
0
1.4.2 Critical Path Methode (CPM)
Eine der in der Praxis häufig angewendeten Netzplantechniken ist die Critical Path Methode
(CPM). Diese Methode behandelt deterministische Angaben und basiert auf einem Vorgangs-
Pfeil-Netzwerk mit Knotenmenge (Ereignismenge) V und Pfeilmenge (Menge der Vorgänge)
E, d.h. jedem Vorgang entspricht ein Pfeil, wobei die Ereignisse durch die Knoten dargestellt
werden.
Alle Anordnungsbeziehungen bei der CPM-Netzplantechnik stammen aus zeitlichen
Mindestabstände vom Ende-Start Typ, d.h. ein Vorgang kann frühestens nach dem Abschluss
aller seinen Vorgänger beginnen. Jeder Vorgang ist mit genau zwei Ereignissen, Start- und
Endereignis ( ,
), die innerhalb eines Zeitintervalls eintreten sollen, verbunden. Ferner
besitzt ein CPM-Netzplan eine Quelle als Projektstart und eine Senke als Projektende. Die
Ausführungsdauer jedes Vorgangs ( ) sind durch die Bewertung des dazugehörigen Pfeils
repräsentiert. Im CPM-Netzplan befindet sich immer mindestens ein Weg zwischen dem
Projekstart und dem Projektende.
Es ist zu erwähnen, dass zwischen zwei Ereignissen im CPM-Netzplan nur ein Pfeil
existieren darf. Folglich könne Probleme bei der Veranschaulichung des CPM-Netzplans
auftreten, z.B. zur Modellierung paralleler Vorgänge zwischen zwei Ereignissen. Daher
kommen sog. Scheinvorgänge mit Dauer Null zum Einsatz. In der Literatur findet man
mehrere Regeln zur Abbildung der besonderen Anordnungsbeziehungen zwischen Vorgängen
in einem CPM-Netzplan (vgl. Zimmermann et al., 2010, S.79 ff.).
Nach der Konstruktion eines CPM-Netzplans müssen in weiteren Schritte die frühesten
und spätesten Start- und Endzeitpunkte einzelner Vorgänge bestimmt werden.
= {1, ... , }
ist die reale Vorgangsmenge (Pfeilmenge) und
= {1, ... ,
} die Ereignissmenge
(Knotenmenge), wobei Knoten 1 als die Quelle und Knoten m als die Senke bezeichnet
werden. Hierbei sind Start- bzw. Endereignis des Vorgangs
durch
und
symbolisiert. Der früheste Eintrittszeitpunkt eines Ereignisses e (
) wird durch die
21
Ermittlung der Länge eines längsten Weges von der Quelle zum Ereignis e bestimmt. Für die
Quelle oder Knoten 1 gilt
= 0, d.h. das Projekt soll zum Zeitpunkt Null gestartet werden.
Für die Senke (Knoten m) gilt
. Mit anderen Worten kann das Projekt frühestens
zum Zeitpunkt
und spätestens zum Zeitpunkt beendet werden. Der späteste
Eintrittszeitpunkt für die Senke (Knoten m) entspricht daher der Projektdauer, d.h.
= .
Wenn die Projektdauer nicht vorgegeben ist, gilt
=
. Ausgehend vom spätesten
Zeitpunkt
kann für die verbleibenden Knoten
{1, ... ,
- 1} der spätesten
Eintrittszeitpunkt
ermittelt werden. Aus der Differenz zwischen dem spätesten Zeitpunkt
und der Länge eines längsten Weges von e zum Projektende m ergibt sich der spätesten
Eintrittszeitpunkt
, d.h.
=
-
.
Zur Bestimmung der frühestmöglichen Start- und Endzeitpunkte (
,
) eines Vorgangs
in einem CPM-Netzplan können die ermittelten frühesten Eintrittszeitpunkte
(
) des
Startereignisses
( ) des Vorgangs i (
) verwendet werden:
=
(1.7)
=
+
(1.8)
Analog dazu können die spätestmöglichen Start- und Endzeitpunkte (
,
) eines Vorgangs
in einem CPM-Netzplan durch die ermittelten spätesten Eintrittszeitpunkte
(
) des
Endereignisses
( ) des Vorgangs i (
) bestimmt werden:
=
-
(1.9)
=
(1.10)
Abbildung 8. Die frühesten bzw. spätesten Eintrittszeitpunkte eines Vorgangs
i
22
Das Verfahren zur Ermittlung der Pufferzeiten in CPM-Netzplänen läuft genauso wie das
Verfahren in MPM-Netzplänen. Die gesamte Pufferzeit
eines Vorgangs i ergibt sich also
aus der Differenz dem spätesten und dem frühesten Startzeitpunkt des Vorgangs
.
=
-
(1.11)
Die freie Pufferzeit
und die freie Rückwärtspufferzeit
eines Vorgangs i werden
durch folgende Gleichungen ermittelt:
=
-
(1.12)
=
-
(1.13)
Zu dem
modifizierten Eintrittszeitpunkt
kann mindestens ein realer Vorgang mit Startereignis
e so früh wie möglich beginnen, während zu dem modifizierten Eintrittszeitpunkt
alle realen
Vorgänge vor Ereignis e abgeschlossen sein müssen (vgl. Zimmermann et al., 2010, S.90).
Beispiel 1.5
Abbildung 9. Ein CPM-Netzplan
Tabelle 6. Früheste bzw. späteste Eintrittszeitpunkte der Ereignisse eines CPM-Netzplans
1 2 3 4
0 3 8 13
0 3 8 13
Tabelle 7. Früheste bzw. späteste Start- und Endzeitpunkte der Vorgänge eines CPM-Netzplans
1
2
3
4
5
0
0
3
3
8
3
6
8
9
13
0
2
3
7
8
3
8
8
13
13
Details
- Seiten
- Erscheinungsform
- Originalausgabe
- Jahr
- 2013
- ISBN (PDF)
- 9783961161294
- ISBN (Paperback)
- 9783961166299
- Dateigröße
- 1.5 MB
- Sprache
- Deutsch
- Institution / Hochschule
- Technische Universität Clausthal – Unternehmensforschung
- Erscheinungsdatum
- 2017 (Mai)
- Note
- 2,3
- Schlagworte
- Projektplanung Netzplantechniken Trade-Off Time-Cost Ressourcenplanung Kosten-Zeit Funktionsmodelle CPM MPM Zeitrestriktion Projektmanagement
