Online Algorithms for Scheduling with Testing

Eckl, Alexander

Alexander Eckl

If you experience problems opening the document, please try this link.

Original title:: Online Algorithms for Scheduling with Testing
Translated title:: Online-Algorithmen für Zeitplanerstellung mit Tests
Author:: Eckl, Alexander
Year:: 2022
Document type:: Dissertation
Faculty/School:: Fakultät für Informatik
Advisor:: Albers, Susanne (Prof. Dr.)
Referee:: Albers, Susanne (Prof. Dr.); Schulz, Andreas (Prof. Dr.)
Language:: en
Subject group:: DAT Datenverarbeitung, Informatik
Keywords:: online scheduling, competitive analysis, explorable uncertainty, scheduling with testing, makespan, sum of completion times
Translated keywords:: Online Zeitplanerstellung, kompetitive Analysis, erkundbare Unsicherheit, Zeitplanerstellung mit Tests, Produktionsspanne, Summe der Komplettierungszeiten
TUM classification:: DAT 500
Abstract:: We study the scheduling with testing problem which models situations where preliminary actions can decrease the duration of tasks. Jobs have an unknown processing time that can be revealed by running a test. Jobs can alternatively be executed for the length of a fixed upper limit. We study the objectives of minimizing the makespan and the total completion time of the schedule, and examine the model on one as well as multiple machines.
Translated abstract:: Wir untersuchen das Scheduling with Testing-Problem, welches Situationen mit vorangehenden Maßnahmen zur Verringerung der Laufzeit von Aufgaben modelliert. Aufgaben haben eine unbekannte Laufzeit, die mit einem Test offen gelegt werden kann. Alternativ können Aufgaben mit Dauer einer festgelegten oberen Schranke ausgeführt werden. Wir betrachten die Zielfunktionen Minimierung der Produktionsspanne und Summe der Komplettierungszeiten, und untersuchen sowohl eine als auch mehrere Maschinen.
WWW:: https://mediatum.ub.tum.de/?id=1621766
Date of submission:: 14.09.2021
Oral examination:: 28.03.2022
File size:: 2245119 bytes
Pages:: 106
Urn (citeable URL):: https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20220328-1621766-1-2
Last change:: 28.07.2022
BibTeX