Modelle und Klassifikationen der ressourcenbeschränkten Projektplanung

Inhaltsverzeichnis

1 Einleitung

2 Grundlagen der Projektplanung
2.1 Zeitliche Anordnungsbeziehungen zwischen Aktivitäten
2.2 Planungsabhängige Zeitfenster
2.3 Ressourcen

3 Modellierung
3.1 Grundproblem der ressourcenbeschränkten Projektplanung
3.2 Berücksichtigung allgemeiner zeitlicher Anordnungsbeziehungen . .
3.3 Variable Verfügbarkeit erneurbarer Ressourcen
3.4 Kalendrierung
3.4.1 Ressourcenkalender
3.4.2 Aktivitätenkalender
3.4.3 Anordnungskalender
3.4.4 Konzeptionelles Modell

4 Klassifikationen
4.1 Nutzen von Klassifikationen
4.2 Drei-Feld-Klassifikation der Projektplanungsprobleme nach Herroelen u. a
4.2.1 Feld α: Ressourcen
4.2.2 Feld β: Aktivitäten
4.2.3 Feld γ: Zielfunktion
4.3 Drei-Feld-Klassifikation der Projektplanungsprobleme nach Brucker u.a
4.3.1 Feld α: Ressourcen
4.3.2 Feld β: Aktivitäten
4.3.3 Feld γ: Zielfunktion
4.4 Kritik an der Klassifikation nach Brucker u.a
4.4.1 Einführung der Parameter P S und M P S im α-Feld
4.4.2 Beschreibung der Aktivitäten
4.4.3 Formelschreibweise zur Beschreibung der Zielfunktion

5 Zusammenfassung

Symbolverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

Gegenstand der Projektplanung ist “die zeitliche Einplanung von Vorgängen oder Aktivitäten eines Projektes, so daß alle Nebenbedingungen der Problemstellung be- rücksichtigt werden und eine vorgegebene Zielfunktion optimiert wird.” ([Schwindt 1998, S. 5]). Praxisrelevante Projektplanungsprobleme beinhalten zu- meist Aktivitäten, deren Ausführung mit einem Bedarf an bestimmten Ressourcen (Arbeitern, Maschinen, Werkzeugen usw.) verbunden ist. Gilt es, die begrenzten Kapazitäten dieser Ressourcen in die zeitliche Planung des Projektes einzubezie- hen, spricht man von ressourcenbeschränkter Projektplanung (resource constrained project scheduling).

Die vorliegende Seminararbeit beschreibt die Modellierung ausgewählter grundle- gender Probleme der ressourcenbeschränkten Projektplanung. Des Weiteren stellt sie zwei im Bereich der Projektplanung gebräuchliche Klassifikationsschemata vor.

Die Arbeit ist wie folgt aufgebaut: In Kapitel 2 werden wesentliche Begriffe der ressourcenbeschränkten Projektplanung erläutert. Kapitel 3 befasst sich mit der Modellierung einiger elementarer Aspekte der Projektplanung. Dazu gehören neben dem Grundproblem der ressourcenbeschränkten Projektplanung auch die Berücksichtigung allgemeiner zeitlicher Anordnungbeziehungen, die Modellierung variierender Ressourcenverfügbarkeiten und die so genannte Kalendrierung. Kapitel 4 behandelt zwei Klassifikationsschemata für Projektplanungsprobleme: zum einen die Klassifikation nach Herroelen u.a. und zum anderen die Klassifikation nach Brucker u.a. Kapitel 5 beinhaltet eine abschließende Zusammenfassung.

2 Grundlagen der Projektplanung

Ein Projekt bestehe aus einer endlichen Menge V = {0, 1, . . . , n, n + 1} von Akti- vitäten (auch Vorgänge genannt). Aktivitäten können dabei einzelne Arbeitsschrit- te oder Teilprojekte repräsentieren. Bei den Aktivitäten 0 und n + 1 handelt es sich um fiktive Aktivitäten, welche den Projektanfang bzw. das Projektende re- präsentieren. Fiktive Aktivitäten verbrauchen weder Zeit noch Ressourcen (vgl. [Zimmermann 2001, S. 7]). Der Planungshorizont T des Projektes sei in gleich lange Zeitperioden (z.B. Tage) unterteilt. Die Menge aller Zeitperioden sei durch T′ = {1, . . . , T } und die Menge aller Zeitpunkte durch T = {0, . . . , T } beschrieben (vgl. [Hartmann 1999, S. 8]). Die Zeitperiode t starte zum Zeitpunkt t − 1 und ende zum Zeitpunkt t. Die Bearbeitungsdauer (processing time oder duration) einer Ak- tivität i ∈ V sei ein Vielfaches der Zeitperioden und durch pi ∈ N gegeben (vgl. [Hartmann 1999, S. 6]). Im Mehr-Modus-Fall hängt die Bearbeitungsdauer einer Ak- tivität davon ab, in welchem Modus diese Aktivität ausgeführt wird. Si beschreibe den Startzeitpunkt des Vorganges i ∈ V. Es gelte zunächst, dass eine Aktivität i ∈ V während ihrer Bearbeitung nicht unterbrochen werden darf. Dann stellt Ci := Si +pi den Endzeitpunkt (completion time) dieser Aktivität dar (vgl. [Zimmermann 2001, S. 8]). Bei Gültigkeit der Annahme, dass ein Projekt zum Zeitpunkt 0 startet (d.h. S0 = 0), liefert der Startzeitpunkt des Projektendes Sn+1 (ebenso wie der Endzeitpunkt Cn+1) die Gesamtdauer des Projektes. Ein Vektor S = (S0, S1, . . . , Sn, Sn+1) der Startzeitpunkte der Aktivitäten eines Projektes stelle einen Schedule dieses Projektes dar (vgl. [Franck 1999, S. 9]).

2.1 Zeitliche Anordnungsbeziehungen zwischen Aktivitäten

Um technischen und/oder organisatorischen Gegebenheiten Rechnung zu tragen, werden zwischen den Aktivitäten eines Projektes zeitliche Anordnungsbeziehungen formuliert. In einem Bauprojekt beispielsweise kann die Aktivität “Fenster einsetzen” nicht vor Abschluss der Aktivität “Wände aufstellen” erfolgen. Die einfachsten Modelle arbeiten mit Ende-Start-Beziehungen mit zeitlichem Mindestabstand von 0 Zeiteinheiten. Sie beschreiben damit, dass eine Aktivität i ∈ V nicht beginnen darf, bevor die Ausführung all ihrer durch die Menge Pi definierten Vorgängeraktivitäten beendet ist (vgl. [Hartmann 1999, S. 6]).

Zwischen den Aktivitäten eines Projektes bestehen jedoch häufig zeitliche Abhän- gigkeiten, die nicht alleine durch Ende-Start-Beziehungen mit zeitlichem Mindestab stand von 0 Zeiteinheiten erfasst werden können (vgl. [S. 9][Zimmermann 2001]). Daher arbeiten zahlreiche Modelle mit so genannten allgemeinen zeitlichen Anord- nungsbeziehungen (Generalised Precedence Relations) (vgl. [Neumann u. a. 2003, S. 2ff.], [Demeulemeester und Herroelen 2002, S. 40ff.]). Allgemeine zeitliche Anrdnungsbeziehungen berücksichtigen sowohl Mindestabstände dminij als auch Höchstabstände dmaxij zwischen jeweils zwei Aktivitäten i, j ∈ V,i = j. Damit lassen sich neben den zeitlichen Beziehungen zwischen den Aktivitäten auch Bereitzeiten einzelner Aktivitäten (ready times) (vgl. [Neumann u. a. 2003, S. 3]) und Stichtage (deadlines) (vgl. [Neumann u. a. 2003, S. 4]) modellieren.

Im Kontext der zeitlichen Anordnungsbeziehungen gibt es vier Anordnungstypen: Start-Start-, Start-Ende-, Ende-Start- und Ende-Ende-Beziehungen. In determinis- tischen Modellen mit nicht unterbrechbaren Ein-Modus-Aktivitäten können die un- terschiedlichen Anordnungstypen gemäß den von [Bartusch u. a. 1988] formulier- ten Regeln in die Start-Start-Form überführt werden. Somit lassen sich die Anord- nungstypen in den meisten Modellen standardisieren. Daher wird im Weiteren bei fehlender Angabe des Anordnungstyps davon ausgegangen, dass sich die zeitlichen Mindest- bzw. Höchstabstände auf die Startzeitpunkte der jeweiligen Aktivitäten beziehen.

2.2 Planungsabhängige Zeitfenster

Die Berücksichtigung minimaler und maximaler Zeitabstände zwischen Aktivitäten führt zur Entstehung der so genannten planungsabhängigen Zeitfenster. Für jede Aktivität i ∈ V eines lösbaren Projektplanungsproblems gibt es ein Intervall zulässi- ger Startzeitpunkte [ESi, LSi] und ein Intervall zulässiger Endzeitpunkte [ECi, LCi] (vgl.[Hartmann 1999, S. 8]). Diese Intervalle werden planungsabhängige Zeitfenster genannt. Planungsabhängig bedeutet in diesem Zusammenhang, dass sie von den geplanten Start- bzw. Endzeitpunkten der Vorgänger- bzw. Nachfolgeraktivitäten abhängig sind.

Algorithmen für die Berechnung der planungsabhängigen Zeitfenster findet man unter anderem bei [Hartmann 1999, S. 8].

2.3 Ressourcen

Die Bearbeitung der Projektaktivitäten erfordert in aller Regel bestimmte Ressourcen. Unter den verschiedenen Kategorien von Ressourcen sind erneuerbare, nichterneuerbare und doppelt beschränkte Ressourcen die wesentlichen (vgl. [Demeulemeester und Herroelen 2002, S. 48ff]).

Erneurbare Ressourcen sind solche Ressourcen, die in jeder Planungsperiode des Projektes zur Verfügung stehen. Dabei ist es irrelevant, ob bzw. in welcher Menge sie in früheren Zeitperioden verbraucht wurden (vgl. [Neumann u. a. 2003, S. 21].

Typische Arten erneuerbarer Ressourcen sind z.B. menschliche Arbeitskraft, Werkzeuge, Arbeitsräume oder Maschinen. Die erneurbaren Ressourcen eines Projektes werden in der Menge Rρ zusammengefasst. Der Verbrauch erneuerbarer Ressourcen in einer Planungsperiode ist durch ihre Kapazität begrenzt. Die Kapazität einer Ressource k ∈ Rρ kann konstant (Rρk) oder variabel (Rρ k(t))sein.

Nicht-erneuerbaren Ressourcen stehen zunächst in einer bestimmten Menge zur Verfügung. Diese Menge verringert sich bei jedem Verbrauch, sie “erneuert sich” also nicht von Planungsperiode zu Planungsperiode. Ein gutes Beispiel dafür ist Geld: Jede Ausgabe bedeutet eine Minderung des in weiteren Planungsperioden noch verfügbaren Projektbudgets (vgl. [Demeulemeester und Herroelen [2002], S.⁴⁸ ]). Die Menge der nicht-erneurbaren Ressourcen wird mit Rν notiert. Für ein Projekt wird die Gesamtkapazität einer Ressource k ∈ Rν mit Rνk angegeben.

Für doppelt beschränkte Ressourcen gilt, dass sowohl ihre Gesamtkapazität für das Projekt als auch ihre Kapazität in einer bestimmten Zeitperiode beschränkt ist. Ein gängiges Beispiel ist ein begrenztes Projektbudget mit zusätzlicher Einschränkung der Geldflüsse pro Planungsperiode (vgl. [Demeulemeester und Herroelen [2002], S. ⁴⁹ ]). Doppelt beschränkte Ressourcen können durch die gleichzeitige Einführung einer erneuerbaren und einer nicht-erneuerbaren Ressource abgebildet werden (vgl. [Talbot [1982], S.¹¹⁹⁹ ]).

Eine ausführliche Beschreibung weiterer Ressourcenkategorien wie z.B. partiell erneurbarer Ressourcen, kumulativer Ressourcen und räumlicher Ressourcen ist in [Demeulemeester und Herroelen [2002], S.⁴⁹ ff] zu finden.

3 Modellierung

3.1 Grundproblem der ressourcenbeschränkten Projektplanung

Das Grundproblem der ressourcenbeschränkten Projektplanung beschäftigt sich mit der Anordnung von Projektaktivitäten unter Beachtung von Zeit- und Ressourcen- restriktionen. Die Zeitrestriktionen sind gegeben durch Ende-Start-Beziehungen mit zeitlichem Abstand von 0 Zeiteinheiten. Die Projektaktivitäten können nur in einem Modus ausgeführt werden und haben bekannte ganzzahlige Bearbeitungsdauern. Während ihrer Bearbeitung dürfen Aktivitäten nicht unterbrochen werden. Diesem Problem liegen ausschließlich erneuerbare Ressourcen zu Grunde. Der Ressourcen- bedarf der Aktivitäten ist während ihrer gesamten Bearbeitungsdauer konstant. Ziel der Planung ist die Projektdauerminimierung. Dieses Projektplanungsproblem wird in der Klassifikation nach Herroelen u.a. (vgl. Abschnitt 4.2) als m, 1|cpm|Cmax und in der Klassifikation nach Brucker u.a. (vgl. Abschnitt 4.3) als P S|prec|Cmax no- tiert. Ebenso ist es als RCP SP (resource constrained project scheduling problem) bekannt.

Das oben beschriebene Problem lässt sich wie folgt als mathematisches Modell formulieren (vgl. [Hartmann 1999, S. 9f.]). Sei xit eine binäre Variable für jede Aktivität i ∈ V und jeden Zeitpunkt t ∈ T . Es gelte:

Abbildung in dieser Leseprobe nicht enthalten

unter den Nebenbedingungen:

Abbildung in dieser Leseprobe nicht enthalten

Die Zielfunktion (3.1) minimiert den Endzeitpunkt der fiktiven Aktivität n + 1 und somit die gesamte Projektdauer. Spätester Endzeitpunkt der Aktivität n + 1 sei die Anzahl der Planungsperioden T des Projektes (vgl. [Hartmann 1999, S. 8]. Die Nebenbedingung (3.2) stellt sicher, dass jede Aktivität nur einmal ausgeführt wird. Die Beachtung der zeitlichen Anordnungsbeziehungen ist durch die Nebenbedingung (3.3) gewährleistet. Die Ungleichung (3.4) beschreibt die Ressourcenbeschränkung und nutzt dabei das Konzept der planungsabhängigen Zeitfenster. Nebenbedingung (3.5) definiert die binären Entscheidungsvariablen.

Alternative mathematische Formulierungen des Problems sind in [Demeulemeester und Herroelen 2002, S. 210ff.] zu finden.

3.2 Berücksichtigung allgemeiner zeitlicher Anordnungsbeziehungen

Die Erweiterung des Grundproblems um allgemeine zeitliche Anordnungsbeziehun- gen führt zur Problemklasse, welche in der Klassifikation nach Herroelen u.a. (vgl. Abschnitt 4.2) als m, 1|gpr|Cmax bezeichnet wird. In der Klassifikation nach Brucker u.a. (vgl. Abschnitt 4.3) handelt es sich dabei um die Problemklasse P S|temp|Cmax. In der Buchstabenschreibweise ist das Problem als RCP SP/max bekannt.

Zum Zwecke der Modellierung allgemeiner zeitlicher Anordnungsbeziehungen (vgl. Abschnitt 2.1) soll zunächst ihre Abbildung in einem Vorgangsknotennetz (activity- on-node network ) eingeführt werden. Sei die Menge der Projektaktivitäten V = {0,1,...,n,n+1} gleichzeitig auch die Menge der Knoten des Vorgangsknotennetzes. Für jeden zeitlichen Mindestabstand dminij zwischen den Startzeitpunkten der Aktivitäten i und j wird eine gerichtete Kante 〈i, j〉 mit einer Gewichtung [Abbildung in dieser Leseprobe nicht enthalten] eingeführt. Bei zeitlichen Höchstabständen dmaxij zwischen den Startzeitpunkten der Aktivitäten i und j hingegen wird eine Rückwärtskante 〈j, i〉 mit einer Gewichtung [Abbildung in dieser Leseprobe nicht enthalten] eingeführt (vgl. [Neumann u. a. 2003, S. 6f.]). Abbildung 3.1 zeigt einen Ausschnitt aus dem Vorgangsknotennetz eines Beispielprojektes. Die Käst- chen i und j symbolisieren zwei Aktivitäten mit einem zeitlichen Mindestabstand dminij = 2 und einem zeitlichen Höchstabstand dmaxij = 5.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1: Abbildung zeitlicher Mindest- und Höchstabstände in einem Vor- gangsknotennetz (vgl. [Neumann u. a. 2003, S. 7])

Sei E die Menge aller Kanten des Vorgangsknotennetzes eines Projektes. Zur Beachtung allgemeiner zeitlicher Anordnungsbeziehungen muss gelten:

Abbildung in dieser Leseprobe nicht enthalten

(vgl. [Zimmermann 2001, S. 10])

Mit den in (3.6) formulierten zeitlichen Restriktionen lässt sich das Grundmodell aus Abschnitt 3.1 erweitern. Das Ergebnis ist das folgende mathematische Modell des ressourcenbeschränkten Projektplanungsproblems mit allgemeinen zeitlichen Anord- nungsbeziehungen:

xit sei weiterhin eine binäre Variable für jede Aktivität i ∈ V und jeden Zeitpunkt t ∈ T . Es gelte:

Abbildung in dieser Leseprobe nicht enthalten

unter den Nebenbedingungen:

Abbildung in dieser Leseprobe nicht enthalten

Gegenüber dem Grundmodell aus Abschnitt 3.1 wurde hier nur Nebenbedingung (3.3) durch Nebenbedingung (3.9) ersetzt. Dadurch wird die Einhaltung der allgemeinen zeitlichen Anordnungsbeziehungen gewährleistet.

Ein äquivalentes Modell ist in [Schwindt 1998, S. 9] zu finden.

3.3 Variable Verfügbarkeit erneurbarer Ressourcen

Die in den Abschnitten 3.1 und 3.2 vorgestellten Modelle gingen davon aus, dass die Kapazität einer Ressource k ∈ Rρ in jeder Zeitperiode eines Projektes konstant ist.

[...]