Using Deep Neural Networks for Scheduling Resource-Constrained Activity Sequences
Creators: name: Pagani, Paolo
Publisher: name: Karlsruher Institut für Technologie (KIT)
Year: 2022

description: 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 dass 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.