Exakte Verfahren für das Ressourcennivellierungsproblem

Sowohl die landwirtschaftliche und industrielle Produktion als auch die Erstellung von Dienstleistungen erfordern den Einsatz einer Reihe von unterschiedlichen Ressourcen wie beispielsweise Maschinen, Räumlichkeiten oder Arbeitskräften. Eine Ablaufplanung für die entsprechenden Leistungserstellungsprozesse verfolgt häufig das Ziel, die Inanspruchnahmen dieser Ressourcen möglichst gleichmäßig über den jeweils betrachteten Planungszeitraum zu verteilen, da auf diese Weise in vielen Fällen das Auftreten starker Überlastungen bzw. starker Unterauslastungen von Ressourcen (mit einhergehenden erhöhten Kosten) vermieden werden kann.

In diesem Kapitel wollen wir zunächst einige Grundlagen erläutern, die zum Verständnis der nachfolgenden Kapitel notwendig sind. Dazu führen wir in Abschnitt 1.1 zunächst verschiedene Begriffe und Konzepte der Projektplanung ein, bevor wir in Abschnitt 1.2 das klassiche Ressourcennivellierungsproblem mit zeitlichen Mindest- und Höchstabständen beschreiben. Im Anschluss betrachten wir in Abschnitt 1.3 verschiedene praxisrelevante Zielfunktionen für die Ressourcennivellierung, die bereits in verschiedenen Arbeiten aus der Literatur behandelt worden sind. Schließlich geben wir in Abschnitt 1.4 noch einen Überblick über den aktuellen Stand der Forschung zum Thema Ressourcennivellierung.

Wie wir in den Abschnitten 1.2 bzw. 1.3 verdeutlicht haben, sind nivellierte Ressourceninanspruchnahmen immer dann anzustreben, wenn durch überdurchschnittlich hohe bzw. durch unterdurchschnittlich niedrige Auslastungen von Ressourcen zu einzelnen Zeitpunkten oder durch eine Abweichung der Auslastungen von einem Vorgabewert Kosten oder anderweitige Nachteile entstehen.

In diesem Kapitel werden wir auf Basis der im vorangegangenen Kapitel eingeführten Struktureigenschaften von Problem (RLP) einen Branch-and-Bound-Algorithmus zur Lösung des Ressourcennivellierungsproblems mit Zielfunktion (RL) (vgl. Abschnitt 1.2) entwickeln.

In diesem Kapitel wollen wir die Leistungsfähigkeit der Verfahren und der MIP-Formulierungen aus den Kapiteln 4, 5 und 6 untersuchen. Zu diesem Zweck haben wir eine experimentelle Performance-Analyse mit Hilfe verschiedener, aus der Literatur bekannter, Testsets durchgeführt. Die einzelnen Probleminstanzen dieser Testsets unterscheiden sich dabei durch verschiedene Merkmale wie die Anzahl an Projektvorgängen oder die Anzahl an erneuerbaren Ressourcen, die Größe von Zeitfenstern bzw. Pufferzeiten oder auch die Höhe der Ressourceninanspruchnahmen und decken somit viele in praktischen Problemstellungen (wie den in Abschnitt 2.1 beschriebenen Revisionsprojekten oder den in Abschnitt 2.2 vorgestellten Mittelfristplanungsprojekten) auftretende Ausprägungen dieser Merkmale ab. Ein weiteres Merkmal vieler Projektplanungsprobleme stellen die Kosten c _k für die Nutzung der im Projektverlauf verwendeten Ressourcen k ∈ R dar. Da sich in den durchgeführten Tests bei einer Veränderung der Kosten für einzelne Ressourcen keine zusätzlichen Erkenntnisse ergeben haben, wurden für die vorliegende Analyse die Kosten aller Ressourcen (für alle verwendeten Testinstanzen) auf den Wert c _k = 1 festgelegt.

In der vorliegenden Arbeit sind verschiedene praktische Anwendungen sowie Lösungsansätze für das Ressourcennivellierungsproblem unter allgemeinen Zeitbeziehungen vorgestellt worden. Um mögliche Zielsetzungen der beschriebenen Anwendungsbeispiele bestmöglich zu berücksichtigen, sind wir in diesem Zuge insbesondere auch auf unterschiedliche, aus der Literatur bekannte, Zielfunktionen eingegangen. Die Leistungsfähigkeit der vorgestellten Lösungsverfahren und MIP-Formulierungen ist in einer umfangreichen Performance-Analyse nachgewiesen worden.