Inhaltsverzeichnis

1  Einleitung  1

2  Grundlagen der Projektplanung  2

2.1  Zeitliche Anordnungsbeziehungen zwischen Aktivitäten  2

2.2  Planungsabhängige Zeitfenster  3

2.3  Ressourcen  3

3  Modellierung  5

3.1  Grundproblem der ressourcenbeschränkten Projektplanung  5

3.2  Berücksichtigung allgemeiner zeitlicher Anordnungsbeziehungen  6

3.3  Variable Verfügbarkeit erneurbarer Ressourcen  7

3.4  Kalendrierung  8

3.4.1  Ressourcenkalender  8

3.4.2  Aktivitätenkalender  9

3.4.3  Anordnungskalender  10

3.4.4  Konzeptionelles Modell  11

4  Klassifikationen  13

4.1  Nutzen von Klassifikationen  13

4.2  Drei-Feld-Klassifikation der Projektplanungsprobleme nach Herroelen  

u.  a.  14

4.2.1  Feld α: Ressourcen  14

4.2.2  Feld β: Aktivitäten  16

4.2.3  Feld γ: Zielfunktion  20

4.3  Drei-Feld-Klassifikation der Projektplanungsprobleme nach Brucker  

u.a.   20

4.3.1  Feld α: Ressourcen  21

4.3.2  Feld β: Aktivitäten  21

4.3.3  Feld γ: Zielfunktion  22

4.4  Kritik an der Klassifikation nach Brucker u.a.  22

4.4.1  Einführung der Parameter P S und M P S im α-Feld  22

4.4.2  Beschreibung der Aktivitäten  23

4.4.3  Formelschreibweise zur Beschreibung der Zielfunktion  24

5  Zusammenfassung  25

i

Symbolverzeichnis

A R ^ρ Ressourcenkalender einer Ressource k ∈ R ρ

k

Aktivitätenkalender der Aktivität i ∈ V A i

C i Endzeitpunkt der Aktivität i

d ^min zeitlicher Mindestabstand zwischen dem Startzeitpunkt der Aktivität i und

ij

dem Startzeitpunkt der Aktivität j

^e i ^{e j} d ^min zeitlicher Mindestabstand zwischen dem Ereignis e i ∈ {S, C} der Aktivität

ij

i und dem Ereignis e j ∈ {S, C} der Aktivität j

d ^max zeitlicher Höchstabstand zwischen dem Startzeitpunkt der Aktivität i und

ij

dem Startzeitpunkt der Aktivität j

^e i ^{e j} d ^max zeitlicher Höchstabstand zwischen dem Ereignis e i ∈ {S, C} der Aktivität

ij

i und dem Ereignis e j ∈ {S, C} der Aktivität j

Gewichtung der Kante i, j im Vorgangsknotennetz δ ij

^e i ^{e j} Gewichtung der Kante i, j bezüglich des Ereignisse e i ∈ {S, C} der dem δ

ij

Knoten i zugeordneten Aktivität i und des Ereignisses e j ∈ {S, C} der dem Knoten j zugeordenten Aktivität j

E Menge aller Kanten im Vorgangsknotennetz

EC i frühester Endzeitpunkt der Aktivität i

ES i frühester Startzeitpunkt der Aktivität i

i, j gerichtete Kante vom Knoten i zum Knoten j im Vorgangsknotennetz

LC i spätester Endzeitpunkt der Aktivität i

LS i spätester Startzeitpunkt der Aktivität i

P i Menge der Vorgängeraktivitäten der Aktivität i

p i Bearbeitungsdauer der Aktivität i

R ^ρ Menge der erneuerbaren Ressourcen des Projektes

R ^ρ Menge der von Aktivität i benötigten erneuerbaren Ressourcen

i

ii

R ^ρ Ressourcenmenge i einer zeitlichen Anordnungsbeziehung ^e i ^{e j} d ^min bzw. ^e i ^{e j} d max

^{ij ij ij} R ^ρ konstante Kapazität der erneuerbaren Ressource k

^k R ρ k (t) Kapazität der erneuerbaren Ressource k zum Zeitpunkt t bzw. in der Zeitperiode t + 1

R ^ν Menge der nicht-erneuerbaren Ressourcen des Projektes

R ^ν Gesamtprojektkapazität der nicht-erneuerbaren Ressource k

k

r ik Bedarf der Aktivität i an Ressource k

S i Startzeitpunkt der Aktivität i

Schedule eines Projektes, S = (S 0 , S 1 , . . . , S n , S n+1 ), i ∈ V S

T Planunghorizont (Anzahl der Zeitperioden)

T Menge aller Zeitperioden des Planungshorizontes T

T Menge aller Zeitpunkte des Planungshorizontes T

V Menge der Projektaktivitäten (inklusive der fiktiven Projektaktivitäten 0 und n + 1 für Projektanfang bzw. Projektende)

V ^p Menge der unterbrechbaren Aktivitäten eines Projektes

V ^np Menge der nicht unterbrechbaren Aktivitäten eines Projektes

X i Zeitpunkt des Ereignisses e i von Vorgang i; bei e i = S ist X i = S i , bei e i = C ist X i = C i

iii

1 Einleitung

Gegenstand der Projektplanung ist “die zeitliche Einplanung von Vorgängen oder Aktivitäten eines Projektes, so daß alle Nebenbedingungen der Problemstellung berücksichtigt werden und eine vorgegebene Zielfunktion optimiert wird.” ([Schwindt 1998, S. 5]). Praxisrelevante Projektplanungsprobleme beinhalten zumeist 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 einzubeziehen, spricht man von ressourcenbeschränkter Projektplanung (resource constrained project scheduling).

Die vorliegende Seminararbeit beschreibt die Modellierung ausgewählter grundlegender 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.

1

2 Grundlagen der Projektplanung

Ein Projekt bestehe aus einer endlichen Menge V = {0, 1, . . . , n, n + 1} von Aktivitäten (auch Vorgänge genannt). Aktivitäten können dabei einzelne Arbeitsschritte 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 reprä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 Aktivität i ∈ V sei ein Vielfaches der Zeitperioden und durch p i ∈ N gegeben (vgl. [Hartmann 1999, S. 6]). Im Mehr-Modus-Fall hängt die Bearbeitungsdauer einer Aktivität davon ab, in welchem Modus diese Aktivität ausgeführt wird. S i 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 C i := S i +p ⁱ 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. S 0 = 0), liefert der Startzeitpunkt des Projektendes S n+1 (ebenso wie der Endzeitpunkt C n+1 ) die Gesamtdauer des Projektes. Ein Vektor S = (S 0 , S 1 , . . . , S n , S n+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 P i definierten Vorgängeraktivitäten beendet ist (vgl. [Hartmann 1999, S. 6]).

Zwischen den Aktivitäten eines Projektes bestehen jedoch häufig zeitliche Abhängigkeiten, die nicht alleine durch Ende-Start-Beziehungen mit zeitlichem Mindestab-

2

stand von 0 Zeiteinheiten erfasst werden können (vgl. [S. 9][Zimmermann 2001]). Daher arbeiten zahlreiche Modelle mit so genannten allgemeinen zeitlichen Anordnungsbeziehungen (Generalised Precedence Relations) (vgl. [Neumann u. a. 2003, S. 2ff.], [Demeulemeester und Herroelen 2002, S. 40ff.]). Allgemeine zeitliche An-ordnungsbeziehungen berücksichtigen sowohl Mindestabstände d min stabstände d

max ij

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 deterministischen Modellen mit nicht unterbrechbaren Ein-Modus-Aktivitäten können die unterschiedlichen Anordnungstypen gemäß den von [Bartusch u. a. 1988] formulierten Regeln in die Start-Start-Form überführt werden. Somit lassen sich die Anordnungstypen 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ässiger Startzeitpunkte [ES i , LS i ] und ein Intervall zulässiger Endzeitpunkte [EC i , LC i ] (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].

3

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. 48]). 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. 49]). Doppelt beschränkte Ressourcen können durch die gleichzeitige Einführung einer erneuerbaren und einer nicht-erneuerbaren Ressource abgebildet werden (vgl. [Talbot 1982, S. 1199]).

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. 49ff] zu finden.

4