Algorithmisch Unterstützte Terminplanung: Untersuchung von Algorithmen zur Generierung für Terminvorschläge und Terminpläne

Autor: Pötter, Sebastian
Jazyk: němčina
Rok vydání: 2020
Předmět:
Druh dokumentu: Text
Popis: In der vorliegenden Arbeit geht es um die Vorstellung eines assistierenden Algorithmus, welche passende Termine für einen einzelnen Auftrag vorschlagen kann. Das Generieren einer vollständigen Terminplanung ist auch ein Teil dieser Arbeit. Als Erstes wird die Struktur, welche die Algorithmen als Grundlagen benötigen, kurz vorgestellt und erklärt. Dann wird auf die Grundlagen der Mengenlehre eingegangen sowie Anforderung solcher Algorithmen in Hinsicht auf Laufzeit und Komplexität. Zusätzlich werden noch Optimierungsvorschläge auf Basis von parallelisierter Rechnung vorgestellt. Das Ergebnis ist ein Algorithmus, welcher implementiert ist und korrekte Terminvorschläge generieren kann. Hierbei benötigt der Algorithmus für einen Suchraum von sechs Monaten weniger als eine Sekunde Rechenzeit. Die optimierten Versionen benötigen für größere Suchräume (größer als sechs Monate) wenig Zeit und sind langsamer bei kleineren Suchräumen (weniger als zwei Monate). Danach werden mögliche Algorithmen zur Erzeugung eines Terminvorschlags erklärt und gegenübergestellt. Dabei wird ein Ansatz auf evolutionärer Basis vorgestellt sowie ein Algorithmus welcher die Terminplanung als Erfüllbarkeitsproblem behandelt. Dabei werden bei beiden Ansätzen mögliche Probleme sowie deren Lösung vorgestellt. Zuletzt werden diese Algorithmen mit Hauptaugenmerk auf Laufzeit und Komplexität miteinander verglichen. Das Ergebnis resultiert in zwei Algorithmen, welche vom Vorgehen her definiert sind. Eine Implementierung der Algorithmen fehlt hierbei. Abschließend wird ein Ausblick für weiter folgende Aufgaben gegeben.:1 Einleitung 1.1 Thematische Abgrenzung 1.2 Zielsetzung 1.3 Aufbau der Arbeit 2 Definition der zugrundeliegenden Daten 2.1 Struktur der vorliegende Daten 2.2 Anforderung an die Problemlösung 2.3 Beschreibung der Problemlösung 2.4 Definition der Programmumgebung 3 Generierung von Terminvorschlägen 3.1 Mengentheoretischer Ansatz 3.1.1 Die Definition der Grundmengen 3.1.2 Formeln für die Zeitblock-Berechnung 3.1.3 Formeln der Randbedingung 3.2 Unparallelisierter Ansatz 3.2.1 Ladeprozess der Daten 3.2.2 Funktionsweise des Algorithmus 3.2.3 Ergebnis 3.3 Parallelisierter Ansatz 3.3.1 Möglichkeiten der Parallelisierung 3.3.2 Ergebnis der Parallelisierung 3.4 Laufzeitanalyse und Vergleich 4 Zusammenstellung eines Terminplans 4.1 Evolutionäre Ansätze zur Laufzeitoptimierung 4.1.1 Möglicher Ansatz einer Lösung 4.1.2 Problematik von lokalen Optima 4.2 Erfüllbarkeitproblem - SAT-SOLVING 4.2.1 Das Erfüllbarkeitsproblem 4.2.2 Modellierung der Terminplanung 4.2.3 Probleme bei der Modellierung der Zeit 4.2.4 Ansatz einer Lösung 4.3 Vergleich der Ansätze 4.3.1 Auswahl eines Ansatzes 4.3.2 Laufzeitanalyse 5 Zusammenfassung und Ausblick 5.1 Zusammenfassung 5.2 Ausblick Literaturverzeichnis Abbildungsverzeichnis Tabellenverzeichnis Anhang A.1 Quellcode des Projektes A.1.1 Klasse zum Laden und verarbeiten der Daten A.1.2 Klasse für die Generierung von Terminvorschlägen B.2 JSON Datei
In the present thesis, the idea of an assisting algorithm is presented, which can suggest suitable dates for an individual order. The generation of a complete schedule is also a part of this thesis. First, the structure that the algorithms need as a basis is briefly introduced and explained. Then the basics of set theory are discussed and the requirements of such algorithms in terms of run-time and complexity are discussed. Additionally, optimization proposals based on parallelized computation are presented. The result is an algorithm, which is implemented and can generate correct timing proposals. The algorithm needs less than one second of computing time for a search space of six months. The optimized versions need little time for larger search spaces (larger than six months) and are slower for smaller search spaces (less than two months). Afterwards, possible algorithms for generating a date proposal are explained and compared. An evolutionary approach is presented as well as an algorithm that treats scheduling as a fulfillment problem. For both approaches possible problems and their solutions are presented. Finally, these algorithms are compared with each other with a focus on runtime and complexity. The result results in two algorithms, which are defined by the procedure. An implementation of the algorithms is missing here. Finally, an outlook for further tasks is given.:1 Einleitung 1.1 Thematische Abgrenzung 1.2 Zielsetzung 1.3 Aufbau der Arbeit 2 Definition der zugrundeliegenden Daten 2.1 Struktur der vorliegende Daten 2.2 Anforderung an die Problemlösung 2.3 Beschreibung der Problemlösung 2.4 Definition der Programmumgebung 3 Generierung von Terminvorschlägen 3.1 Mengentheoretischer Ansatz 3.1.1 Die Definition der Grundmengen 3.1.2 Formeln für die Zeitblock-Berechnung 3.1.3 Formeln der Randbedingung 3.2 Unparallelisierter Ansatz 3.2.1 Ladeprozess der Daten 3.2.2 Funktionsweise des Algorithmus 3.2.3 Ergebnis 3.3 Parallelisierter Ansatz 3.3.1 Möglichkeiten der Parallelisierung 3.3.2 Ergebnis der Parallelisierung 3.4 Laufzeitanalyse und Vergleich 4 Zusammenstellung eines Terminplans 4.1 Evolutionäre Ansätze zur Laufzeitoptimierung 4.1.1 Möglicher Ansatz einer Lösung 4.1.2 Problematik von lokalen Optima 4.2 Erfüllbarkeitproblem - SAT-SOLVING 4.2.1 Das Erfüllbarkeitsproblem 4.2.2 Modellierung der Terminplanung 4.2.3 Probleme bei der Modellierung der Zeit 4.2.4 Ansatz einer Lösung 4.3 Vergleich der Ansätze 4.3.1 Auswahl eines Ansatzes 4.3.2 Laufzeitanalyse 5 Zusammenfassung und Ausblick 5.1 Zusammenfassung 5.2 Ausblick Literaturverzeichnis Abbildungsverzeichnis Tabellenverzeichnis Anhang A.1 Quellcode des Projektes A.1.1 Klasse zum Laden und verarbeiten der Daten A.1.2 Klasse für die Generierung von Terminvorschlägen B.2 JSON Datei
Databáze: Networked Digital Library of Theses & Dissertations
Externí odkaz: