Projektplanung mit partiell erneuerbaren Ressourcen: Entwicklung und Untersuchung von Branch-and-Bound-Verfahren

Autor: Watermeyer, Kai
Přispěvatelé: Zimmermann, Jürgen
Jazyk: němčina
Rok vydání: 2021
Předmět:
DOI: 10.21268/20210714-0
Popis: Die Implementierung eines geeigneten und zielgerichteten Projektmanagements stellt für viele Unternehmen im Hinblick auf kürzer werdende Innovationszyklen und sich verändernde Marktanforderungen einen immer wichtigeren Erfolgsfaktor dar. Eine entscheidende Bedeutung kommt dabei vor allem der Projektplanung als Bindeglied zwischen der Vorbereitungs- und der Ausführungsphase eines Projekts zu. Insbesondere die ressourcenbeschränkte Projektplanung kann durch die Bestimmung effizienter und kostengünstiger Einsatzpläne für begrenzt verfügbare Ressourcen einen wichtigen Beitrag zur Wettbewerbsfähigkeit eines Unternehmens leisten. Die meisten Modelle der ressourcenbeschränkten Projektplanung gehen vereinfachend davon aus, dass erneuerbare Ressourcen in bestimmten Mengen in jeder Zeitperiode für die Ausführung von Vorgängen zur Verfügung stehen, die durch Vorrangbeziehungen miteinander verbunden sind. Diese einschränkenden Annahmen führen jedoch dazu, dass praxisrelevante Restriktionen wie Arbeitszeitvereinbarungen oder Vorgaben zur Höchstauslastung von Maschinen durch Modelle der ressourcenbeschränkten Projektplanung nicht abgebildet werden können. Eine Möglichkeit, um komplexere Restriktionen in die Modelle einzubinden, stellen sogenannte partiell erneuerbare Ressourcen dar, die Kapazitätsrestriktionen auch über mehrere Zeitperioden modellieren können. Durch diese Art von Ressourcen können unter anderem maximale Arbeitsstunden am Wochenende oder vorgeschriebene Pausenzeiten von Arbeitskräften modelliert werden, die durch klassische Modelle der Projektplanung nicht abgebildet werden können. Weitere praxisrelevante Restriktionen wie technologisch bedingte Zeitfenster für die Ausführung von Fertigungsprozessen können zudem durch zeitliche Mindest- und Höchstabstände bzw. durch allgemeine Zeitbeziehungen zwischen den Vorgängen eines Projekts dargestellt werden. In der vorliegenden Arbeit wird das Projektdauerminimierungsproblem mit allgemeinen Zeitbeziehungen und partiell erneuerbaren Ressourcen (RCPSP/max-π) untersucht. Ein Schwerpunkt liegt dabei auf der Entwicklung von Branch-and-Bound-Verfahren, die auf unterschiedlichen Enumerationsschemata basieren. Es werden zwei relaxationsbasierte und ein konstruktionsbasiertes Branch-and-Bound-Verfahren vorgestellt, deren Leistungsfähigkeit anhand geeigneter Testinstanzen durch eine experimentelle Performance-Analyse untersucht werden. Die Ergebnisse der Analysen zeigen, dass eines der relaxationsbasierten Verfahren, das die zeitzulässigen Startzeitpunkte der Vorgänge des Projekts schrittweise in disjunkte Mengen zerlegt, die beiden anderen Ansätze dominiert. Aus einem weiterführenden Vergleich mit dem MILP-Solver IBM CPLEX sowie den besten bislang bekannten Näherungsverfahren zur Projektdauerminimierung mit partiell erneuerbaren Ressourcen wird zudem die vorteilhafte Performance des dominanten Branch-and-Bound-Verfahrens bestätigt. In der vorliegenden Arbeit wird weiterhin gezeigt, dass der Einsatz partiell erneuerbarer Ressourcen ein weites Feld an Modellierungsmöglichkeiten eröffnet, das auch andere Konzepte der Projektplanung umfasst, die über die letzten Jahrzehnte entwickelt wurden. Basierend auf diesen Ergebnissen wird zudem gezeigt, dass exakte Verfahren für das RCPSP/max-π auch zur Lösung anderer bekannter Projektdauerminimierungsprobleme aus der Literatur eingesetzt werden können.
The implementation of a suitable and targeted project management is an increasingly important success factor for many companies in view of shorter innovation cycles and changing market requirements. Project scheduling is of particular importance as the link between the preparation and execution phase of a project. In fact, resource-constrained project scheduling can make an important contribution to the competitiveness of a company by determining efficient and cost-effective deployment plans for limited resources. Most models of resource-constrained project scheduling assume, in a simplified manner, that renewable resources are available in certain quantities in each period of time for the execution of tasks that are linked by precedence relationships. However, these limiting assumptions mean that practical restrictions such as working time agreements or specifications for the maximum utilization of machines cannot be mapped by models of resource-constrained project scheduling. One way of integrating more complex restrictions into the models are so-called partially renewable resources that can model capacity restrictions over several time periods. This type of resource can be used to model, among other things, maximum working hours on weekends or prescribed break times for workers, which cannot be mapped using classic project scheduling models. Further practical restrictions such as technologically-related time windows for the execution of manufacturing processes can be represented by minimum and maximum time lags or rather by general temporal constraints between the activities of a project. In the present work the project duration problem with general temporal constraints and partially renewable resources (RCPSP/max-π) is investigated. One focus is on the development of branch-and-bound procedures that are based on different enumeration schemes. Two relaxation-based and one construction-based branch-and-bound method are presented, the performance of which is examined using suitable test instances through an experimental performance analysis. The results of the analyzes show that one of the relaxation-based methods, which gradually decomposes the time-feasible start times of the project's activities into disjoint sets, dominates the other two approaches. A further comparison with the MILP solver IBM CPLEX as well as the best known approximation methods for project duration problems with partially renewable resources also confirms the advantageous performance of the dominant branch-and-bound method. In the present work it is further shown that the use of partially renewable resources opens up a wide field of modeling possibilities that also includes other project scheduling concepts that have been developed over the past decades. Based on these results it is shown that exact solution procedures for the RCPSP/max-π can also be used to solve other known project duration problems from the literature.
Databáze: OpenAIRE
Externí odkaz: