Diplomarbeit
Diplomarbeit
Scheduling von unbeschränkten Taskfolgen mit relativen Timing Constraints.
Diplomarbeit, Wilko Hein, 1999
Im Rahmen der Diplomarbeit wird das Planen von unendlichen Taskfolgen mit relativen Zeitbeschränkungen auf Single-Prozessor-Systemen untersucht.
Einleitend werden nach einer konkreten Problemformulierung einige bereits veröffentlichte Lösungsstrategien vorgestellt. Diese sind jedoch nur bedingt auf das behandelte Scheduling-Problem anwendbar, da oft nur endliche Schedules oder Probleme ohne Release-Constraints betrachtet werden. Basierend auf einigen hergeleiteten theoretischen Aussagen werden dann zwei neue Lösungsstrategien formuliert. Die beweisbar korrekte Methode erweitert ein Branch-and-Bound-Vorgehen auf release-beschränkte Probleme; das zweite, heuristische Verfahren dagegen generiert flexible Schedules mittels einer Simulated-Annealing-Strategie.
Dabei wird ein neues Repräsentations- und Verarbeitungsmodell für Schedules vorgestellt und verwendet. In experimentellen Ergebnissen kann schließlich die Qualität der vorgestellten Methoden gezeigt werden. Dazu wird eine eigens implementierte Simulations-Software verwendet. Neben statistischen Auswertungen erfolgt dabei auch die Simulation grundlegender Beispielprobleme.
Zum Downloadbereich der Diplomarbeit und des Simulators.