Benutzer: Gast  Login
Wenn Sie Schwierigkeiten haben, das Dokument zu öffnen, versuchen Sie auch bitte diesen Link
Originaltitel:
Stochastic Scheduling with Precedence Constraints
Übersetzter Titel:
Stochastisches Scheduling mit Präzedenz-Relationen
Autor:
Pinkau, Chris
Jahr:
2017
Dokumenttyp:
Dissertation
Fakultät/School:
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.
WWW:
https://mediatum.ub.tum.de/?id=1307184
Eingereicht am:
13.06.2016
Mündliche Prüfung:
14.02.2017
Dateigröße:
3177038 bytes
Seiten:
223
Urn (Zitierfähige URL):
https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20170214-1307184-1-6
Letzte Änderung:
16.03.2017
 BibTeX