Abstract:
Eines der bekanntesten Planungsprobleme stellt die Planung von Aktivitäten
unter Berücksichtigung von Reihenfolgenbeziehungen zwischen diesen
Aktivitäten sowie Ressourcenbeschränkungen dar. In der Literatur ist
dieses Planungsproblem als das ressourcenbeschränkte Projektplanungsproblem
bekannt und wird im Englischen als Resource-Constrained Project
Scheduling Problem oder kurz RCPSP bezeichnet. Das Ziel dieses Problems
besteht darin, die Bearbeitungszeit einer Aktivitätsfolge zu minimieren,
indem festgelegt wird, wann jede einzelne Aktivität beginnen soll, ohne
... mehrdass die Ressourcenbeschränkungen überschritten werden. Wenn die Bearbeitungsdauern
der Aktivitäten bekannt und deterministisch sind, können
die Startzeiten der Aktivitäten à priori definiert werden, ohne dass die
Gefahr besteht, dass der Zeitplan unausführbar wird. Da jedoch die Bearbeitungsdauern
der Aktivitäten häufig nicht deterministisch sind, sondern auf
Schätzungen von Expertengruppen oder historischen Daten basieren, können
die realen Bearbeitungsdauern von den geschätzten abweichen. In diesem Fall
ist eine reaktive Planungsstrategie zu bevorzugen. Solch eine reaktive Strategie
legt die Startzeiten der einzelnen Aktivitäten nicht zu Beginn des Projektes
fest, sondern erst unmittelbar an jedem Entscheidungspunkt im Projekt, also
zu Beginn des Projektes und immer dann wenn eine oder mehrere Aktivitäten
abgeschlossen und die beanspruchten Ressourcen frei werden.
In dieser Arbeit wird eine neue reaktive Planungsstrategie für das
ressourcenbeschränkte Projektplanungsproblem vorgestellt. Im Gegensatz zu
anderen Literaturbeiträgen, in denen exakte, heuristische und meta-heuristische
Methoden zur Anwendung kommen, basiert der in dieser Arbeit aufgestellte
Lösungsansatz auf künstlichen neuronalen Netzen und maschinellem Lernen.
Die neuronalen Netze verarbeiten die Informationen, die den aktuellen Zustand
der Aktivitätsfolge beschreiben, und erzeugen daraus Prioritätswerte für
die Aktivitäten, die im aktuellen Entscheidungspunkt gestartet werden können.
Das maschinelle Lernen und insbesondere das überwachte Lernen werden für das
Trainieren der neuronalen Netze mit beispielhaften Trainingsdaten angewendet,
wobei die Trainingsdaten mit Hilfe einer Simulation erzeugt wurden.
Sechs verschiedene neuronale Netzwerkstrukturen werden in dieser Arbeit betrachtet.
Diese Strukturen unterscheiden sich sowohl in der ihnen zur Verfügung
gestellten Eingabeinformation als auch der Art des neuronalen Netzes, das diese
Information verarbeitet. Es werden drei Arten von neuronalen Netzen betrachtet.
Diese sind neuronale Netze mit vollständig verbundenen Schichten, 1-
dimensionale faltende neuronale Netze und 2-dimensionale neuronale faltende
Netze. Darüber hinaus werden innerhalb jeder einzelnen Netzwerkstruktur verschiedene
Hyperparameter, z.B. die Lernrate, Anzahl der Lernepochen, Anzahl
an Schichten und Anzahl an Neuronen per Schicht, mittels einer Bayesischen Optimierung
abgestimmt. Während des Abstimmens der Hyperparameter wurden
außerdem Bereiche für die Hyperparameter identifiziert, die zur Verbesserung
der Leistungen genutzt werden sollten.
Das am besten trainierte Netzwerk wird dann für den Vergleich mit anderen
vierunddreißig reaktiven heuristischen Methoden herangezogen. Die Ergebnisse
dieses Vergleichs zeigen, dass der in dieser Arbeit vorgeschlagene Ansatz
in Bezug auf die Minimierung der Gesamtdauer der Aktivitätsfolge die meisten
Heuristiken übertrifft. Lediglich 3 Heuristiken erzielen kürzere Gesamtdauern
als der Ansatz dieser Arbeit, jedoch sind deren Rechenzeiten um viele
Größenordnungen länger.
Eine Annahme in dieser Arbeit besteht darin, dass während der Ausführung
der Aktivitäten Abweichungen bei den Aktivitätsdauern auftreten können,
obwohl die Aktivitätsdauern generell als deterministisch modelliert werden.
Folglich wird eine Sensitivitätsanalyse durchgeführt, um zu prüfen, ob die
vorgeschlagene reaktive Planungsstrategie auch dann kompetitiv bleibt, wenn
die Aktivitätsdauern von den angenommenen Werten abweichen.
Abstract (englisch):
One of the most popular scheduling problems is the scheduling of the activities
under precedence and resource constraints. In the literature, this problem is
called Resource-Constrained Project Scheduling Problem, or shortly RCPSP,
and its goal is generally to minimize the execution time of the entire activity
sequence by defining when each activity should start without exceeding the resource
consumption. If the activity durations are known and deterministic, it is
possible to define their start time à priori with no risk that the schedule becomes
unfeasible. However, since the activity durations are often not deterministic and
... mehr
roughly estimated by groups of experts and with historical data, the real unknown
activity durations may be different than the assumed ones. In this case,
it is generally preferred to use a reactive scheduling policy, i.e. a policy that
does not determine the starting time of each activity at the beginning of the
project but only determines step by step which activities should be immediately
started at each decision point, i.e. at the beginning and every time one or more
activities are completed and new resources are released.
In this thesis, a new reactive policy for the Resource-Constrained Project
Scheduling Problem is proposed. Unlike the other literature contributions,
where exact, heuristic and meta-heuristic methods are used, the proposed approach
is based on artificial neural networks and machine learning. The neural
networks are used to process the information defining the current state of the
activity sequence and to generate priority values for the activities that could
be started at the current decision point. On the other hand, machine learning
and, in particular, supervised learning are used to train the neural network with
training data generated by simulation experiments.
Six different neural network structures are considered in this thesis. They differ
both in the input information and in the type of neural network they use to
process it. Three neural network types are considered, namely fully connected,
1-dimensional convolutional and 2-dimensional convolutional neural networks.
Moreover, within the same structure, different hyperparameters, for example learning
rate, number of epochs, number of layers and number of neurons per
layer, are considered and tuned using a Bayesian optimization. The tuning
process has also identified which ranges for the hyperparameter should be used
to improve the performance.
The best trained neural network is then considered for the comparison with
other thirty-four reactive heuristic methods. The results show that the proposed
approach is very competitive for what concerns the minimization of the
total duration since it outperforms most of the heuristics. Only three heuristics
achieved a better performance. However, they require computing times that
are many orders of magnitude bigger.
One assumption of this thesis is that, although the activity durations are modeled
as deterministic, some deviations may occur during the activity execution.
As a result, a sensitivity analysis is performed to test whether the proposed
reactive policy remains competitive even if the durations deviate from the assumed
value.
