User: Guest  Login
If you experience problems opening the document, please try this link.
Original title:
Stochastic Scheduling with Precedence Constraints
Translated title:
Stochastisches Scheduling mit Präzedenz-Relationen
Author:
Pinkau, Chris
Year:
2017
Document type:
Dissertation
Faculty/School:
Fakultät für Informatik
Advisor:
Mayr, Ernst W. (Prof. Dr.)
Referee:
Mayr, Ernst W. (Prof. Dr.); Seidl, Helmut (Prof. Dr.)
Language:
en
Subject group:
DAT Datenverarbeitung, Informatik; INF Informationswesen, Bibliotheks-, Dokumentations-, Archiv-, Museumswesen
TUM classification:
DAT 530d
Abstract:
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.
Translated abstract:
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
Date of submission:
13.06.2016
Oral examination:
14.02.2017
File size:
3177038 bytes
Pages:
223
Urn (citeable URL):
https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20170214-1307184-1-6
Last change:
16.03.2017
 BibTeX