TY  - THES
AB  - Das Auftreten von Setupzeiten für die Bereitstellung von Maschinen ist eine natürliche Annahme bei der Betrachtung von Schedulingproblemen. Derartige Setups tauchen z.B. als Startzeiten von Maschinen oder für die Rekonfiguration zwischen der Ausführung von Jobs unterschiedlicher Typen auf. Diese Arbeit beschäftigt sich mit zwei unterschiedlichen Modellen für Probleme mit Setupzeiten. Im ersten Modell betrachten wir Jobs, die in verschiedene Klassen unterteilt sind. Sobald eine Maschine zwischen Jobs unterschiedlicher Klassen wechselt, ist ein Setup für die Rekonfiguration der Maschine notwendig. Wir betrachten dieses Problem für parallele Maschinen und die Minimierung des Makespan. Hierfür entwerfen und analysieren wir Approximationsalgorithmen für identische und heterogene Maschinen. Darüber hinaus verallgemeinern wir das Problem auf über die Zeit eintreffende Jobs und die Minimierung der maximalen Antwortzeit. Dabei betrachten wir Approximationen für den offline Fall auf einer Maschine und untersuchen die (smoothed) competitiveness eines einfachen online Algorithmus. Im zweiten Modell befassen wir uns mit der Ausführung von Jobs auf gemieteten Maschinen und dem Ziel der Mietkostenminimierung. Wir betrachten zwei heterogene Maschinentypen, die für beliebige Zeitspannen gemietet werden können, bei denen allerdings Setupzeiten mit dem Starten einhergehen. Wir entwickeln und analysieren einen online Algorithmus für über die Zeit eintreffende Jobs mit Abarbeitungsfristen.
AU  - Mäcker, Alexander
CY  - Paderborn
DA  - 2019
DO  - 10.17619/UNIPB/1-828
DP  - Universität Paderborn
LA  - eng
N1  - Tag der Verteidigung: 06.11.2019
N1  - Universität Paderborn, Dissertation, 2019
PB  - Veröffentlichungen der Universität
PY  - 2019
SP  - 1 Online-Ressource (x, 134 Seiten)
T2  - Institut für Informatik
TI  - On scheduling with setup times
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-35865
Y2  - 2026-01-20T02:19:34
ER  -