Benutzer: Gast  Login
Originaltitel:
Stochastic Scheduling with Precedence Constraints 
Übersetzter Titel:
Stochastisches Scheduling mit Präzedenz-Relationen 
Jahr:
2017 
Dokumenttyp:
Dissertation 
Institution:
Fakultät für Informatik 
Betreuer:
Mayr, Ernst W. (Prof. Dr.) 
Gutachter:
Mayr, Ernst W. (Prof. Dr.); Seidl, Helmut (Prof. Dr.) 
Sprache:
en 
Fachgebiet:
DAT Datenverarbeitung, Informatik; INF Informationswesen, Bibliotheks-, Dokumentations-, Archiv-, Museumswesen 
TU-Systematik:
DAT 530d 
Kurzfassung:
Scheduling partially ordered tasks on several parallel processors has been a topic of many scientific articles over the past 40 years. Mokotoff, Pinedo, and Lawler et al give many prominent examples, some of them polynomially optimizable, others NP-hard. The landscape of scheduling is vast, changing just one variable in the problem statement can dramatically alter the process of finding results and the results themselves. One special branch of scheduling that has been considered is stochastic scheduling, with stochastic processing times for the tasks, subject to some probability distributions.
This thesis starts by examining the scheduling problem given by two processors, exponentially distributed processing times, intree precedence constraints, and (expected) makespan optimization. This specific problem has been polynomially solved many years ago by Chandy and Reynolds , but, to our knowledge, has not been generalized to other distributions yet. This thesis describes an optimal solution for the geometric distribution, and provides insights and experimental results for the uniform and Erlang distributions.
We shed light on some strategies for general precedence constraints and the extension to three processors by indicating characterizations of the proposed scheduling problems that may lead to finding optimal strategies in future work. 
Übersetzte Kurzfassung:
Seit nun schon über 40 Jahren ist Scheduling von partiell geordneten Prozessen auf parallelen Systemen Thema zahlreicher wissenschaftlicher Arbeiten. Mokotoff, Pinedo, und Lawler et al nennen einige der berühmtesten Beispiele, viele davon lösbar in Polynomialzeit, andere wiederum sind NP-schwer. Das Spektrum von Scheduling ist reichhaltig, das Ändern einer Variable in der Problembeschreibung kann zu großen Unterschieden in den Ergebnissen führen. Ein großes Teilgebiet ist dabei das stochastische Scheduling, bei dem die Ausführungszeiten der Prozesse stochastischer Fluktuation unterliegen, d.h., sie sind nicht deterministisch gegeben, sondern durch Zufallsvariablen mit zugrundeliegenden Wahrscheinlichkeitsverteilungen beschrieben.
Das Ausgangsproblem dieser Arbeit ist das Scheduling-Problem, das gegeben ist durch zwei Prozessoren, exponentiell verteile Prozesszeiten, Präzedenzen in Form von Intrees, und Optimierung der totalen (erwarteten) Laufzeit. Zu diesem Problem gibt es schon seit einiger Zeit eine Polynomialzeit-Lösung von Chandy und Reynolds , doch ist es bisher (nach unserer Erkenntnis) noch nicht auf andere Verteilungen erweitert worden. Diese Arbeit zeigt den Beweis einer optimalen Lösung für geometrisch verteile Prozesszeiten, und fasst Einblicke und experimentelle Ergebnisse für gleichverteilte und Erlang-verteilte Prozesszeiten zusammen.
Außerdem befassen wir uns mit verschiedenen Strategien für allgemeine Präzedenzen und die Erweiterung des Problems auf mehr als zwei Prozessoren, bei denen die genaue Untersuchung von nicht-optimalen Strategien und deren Charakteristika zum Auffinden einer optimalen Strategie für zukünftige Arbeiten führen könnte. 
Mündliche Prüfung:
14.02.2017 
Dateigröße:
3177038 bytes 
Seiten:
223 
Letzte Änderung:
16.03.2017