Direkt zum Inhalt | Direkt zur Navigation

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-79760
URL: http://www.freidok.uni-freiburg.de/volltexte/7976/


Nonner, Tim

Approximation in batch and multiprocessor scheduling

Approximation in Batch- und Multiprozessor-Scheduling

Dokument1.pdf (1.178 KB) (md5sum: 7f0dee20c5a96ea9d772a1cc3e23d5b7)

Kurzfassung in Englisch

This thesis is about scheduling problems where jobs arrive over time. Depending on the problem, we consider the case that each job has a deadline, or the relaxation that the sum of flow times or completion times need to be minimized. Since most of the discussed problems are NP-hard, the goal is to find polynomial time algorithms with provable approximation guarantee, preferably in an on-line setting.

In the first part of this thesis, we consider batch scheduling problems for the case that each job has a deadline, and hence two jobs may be added to the same batch if their due intervals intersect. We first present a framework that unifies all batch cost structures discussed in this part. For instance max-batching, where the cost of each batch is the maximum weight of any contained job. We show that max-batching is strongly NP-hard in this context if the size of each batch is additionally restricted by a constant capacity constraint, and we also give a polynomial time approximation scheme (PTAS) for this case. Moreover, we consider a minmax-variant of max-batching which finds application in the area of data aggregation. We show that this variant is strongly NP-hard as well, and we present a quasi-polynomial time approximation scheme (QPTAS) and moreover a PTAS for the case that the due interval lengths are constants. Finally, we show that the closely related batch cost structure used in joint replenishment results in an APX-hard problem, which is hence not likely to admit an approximation scheme, but we show that it admits a randomized 5/3-approximation algorithm.

In the second part of this thesis, multiprocessor scheduling problems are discussed. We give the first proof that the competitive ratio of the well-known algorithm SRPT is strictly smaller than 2 for completion time scheduling on identical machines. Specifically, we give the upper bound 1.86. Since it is harder to find approximation guarantees for flow time scheduling, we investigate this case in the context of speed-scaling, where it is allowed to arbitrarily increase the speed of each processor subject to some reasonable penalty. For this model, we present a general approach to transform single processor algorithms into multiprocessor algorithms. This yields new or improved constant approximation guarantees for basically all variants of speed-scaled multiprocessor scheduling.


Kurzfassung in Deutsch

Diese Dissertation beschäftigt sich mit Schedulingproblemen mit unterschiedlichen Einlastzeiten (engl. release times), d.h. die Aufträge (engl. jobs) erscheinen nacheinander. Abhängig von dem betrachteten Problem untersuchen wir den Fall, dass jeder Auftrag entweder eine Fertigstellungstermin (engl. deadline) besitzt oder die Relaxierung, dass die Summe der Flusszeiten (engl. flow times) oder Fertigstellungszeiten (engl. completion times) minimiert werden soll. Da die meisten der betrachteten Probleme NP-hart sind, ist es unser Ziel, Algorithmen zu enwickeln, die in Polynomialzeit Lösungen mit beweisbarer Approximationsgüte liefern, und dies möglichst sogar dann, wenn die Aufträge on-line erscheinen.

Der erste Teil dieser Dissertation beschäftigt sich mit Batch-Schedulingproblemen. Wir betrachten den Fall, dass jeder Auftrag über einen Fertigstellungstermin verfügt, und sich zwei Jobs nur dann in denselben Batch packen lassen, wenn ihre entsprechenden Verfügbarkeitsintervalle (engl. due intervals) überlappen. Wir erläutern zuerst ein einheitliches Rahmenwerk, welches alle betrachteten Batch-Kostenstrukturen enthält. Ein prominentes Beispiel ist max-Batching, d.h., die Kosten eines Batches ist das maximale Gewicht aller Aufträge, welche in diesem Batch enthalten sind. Wir zeigen, dass max-Batching in diesem Zusammenhang NP-hart ist falls die Größe jedes Batches durch eine konstante Kapazität beschränkt ist und präsentieren ausserdem ein Polynomialzeit-Approximationsschema (PTAS) für diesen Fall. Danach betrachten wir eine minmax-Variante von max-Batching, welche bei der Aggregation von Daten Verwendung findet, und zeigen, dass auch dieses Problem NP-hart ist. Ausserdem präsentieren wir auch hier eine Quasi-Polynomialzeit-Approximationsschema (QPTAS) und außerdem ein PTAS für den Fall, dass die Längen der Verfügbarkeitsintervalle konstant beschränkt sind. Zuletzt zeigen wir, dass die verwandte Batch-Kostenstruktur des Joint Replenishment ein APX-hartes Problem ergibt, welches damit wahrscheinlich kein Approximationsschema zuläßt. Wir formulieren aber einen randomisierten 5/3-Approximationsalgorithmus.

Der zweite Teil dieser Dissertation befasst sich mit Schedulingproblemen auf mehreren Prozessoren. Wir präsentieren den ersten Beweis, dass die Kompetitivität des bekannten Algorithmus SRPT echt kleiner ist als 2 falls die Summe der Fertigstellungszeiten minimiert werden soll. Speziell erhalten wir die obere Schranke 1.86. Da es schwieriger ist, solche Approximationsgarantien für die Minimierung der Summe der Flusszeiten zu erhalten, betrachten wird diesen Fall für Prozessoren mit skalierbaren Geschwindigkeiten (engl. speed-scaled processors), welche unter Rücksichtnahme einer sinnvollen Kostensanktion beliebig erhöht werden dürfen. Für dieses Modell präsentieren wir eine allgemeine Methode, um aus einen beliebigen Algorithmen für einen einzelnen Prozessor einen Algorithmus für mehrere Prozessoren zu erhalten. Dies liefert neue oder verbesserte Kompetitivitäten für alle wesentlichen Varianten.


SWD-Schlagwörter: Online-Algorithmus , Approximationsalgorithmus , Scheduling
Freie Schlagwörter (englisch): Batch Scheduling , Multiprocessor Scheduling
CCS Klassifikation G.2.2 , G.1.6 , G.2.1 , F.2.2
Institut: Institut für Informatik
Fakultät: Technische Fakultät (bisher: Fak. f. Angew. Wiss.)
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Erstgutachter: Albers, Susanne (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 03.12.2010
Erstellungsjahr: 2010
Publikationsdatum: 22.02.2011
Indexliste