Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich.
mehr Informationen...
ger: 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.
eng: The occurrence of setup times for the preparation of machines is a natural assumption when considering scheduling problems. They may occur, for example, as startup times for machines or for the (re-)configuration of machines between the processing of jobs of different types. In this thesis, we study two kinds of models for scheduling problems incorporating such setup times. The first kind of model considers jobs that are partitioned into several classes. Whenever a machine switches between the processing of jobs of different classes, a setup for the reconfiguration of the machine needs to take place. We study this problem for parallel machines with the objective of minimizing the makespan. We design and analyze approximation algorithms for the case of identical and heterogeneous machines. Additionally, we generalize the problem by allowing jobs to arrive over time and by considering the minimization of the maximum flow time. We give an approximation algorithm for the offline case of a single machine and study the (smoothed) competitiveness of a simple online algorithm. The second model deals with jobs that need to be processed on machines rented from the cloud and the minimization of the rental cost. We consider the availability of two heterogeneous types of machines that can be rented for arbitrary durations but incur a setup time for booting newly rented machines. We develop and analyze an online algorithm for jobs with deadlines arriving over time.