In dieser Arbeit untersuchen wir Algorithmen für Scheduling-Probleme. Wir betrachten semi-online Makespan-Scheduling und generalisiertes Bin Covering. Im online Makespan- Scheduling-Problem sind m Maschinen und n Jobs gegeben, wobei letztere jeweils eine individuelle Bearbeitungszeit haben. Es wird zu jedem Zeitpunkt ein Job offengelegt und muss sofort und unwiderruflich einer Maschine zugewiesen werden, ohne Wissen über zukünftige Jobs. Die Last einer Maschine wird als die Summe der Bearbeitungszeiten der ihr zugewiesenen Jobs definiert. Das Ziel ist es, eine Zuweisung von Jobs zu Maschinen zu finden, sodass die höchste Last einer Maschine minimiert wird. Im semi-online Scheduling-Modell wird dieses strikte Szenario relaxiert. Wir untersuchen drei verschied- ene Modelle. Im ersten ist uns die kumulierte Bearbeitungszeit der Jobs vor Ankunft der einzelnen Jobs bekannt. Im zweiten Modell dürfen wir bis zu einem gewissen Grade bereits zugewiesene Jobs anderen Maschinen neu zuordnen.Im dritten semi-online Scheduling-Modell darf ein Algorithmus mehrere Lösungen parallel konstruieren, von denen die beste ausgegeben wird. Beim generalisierten Bin Covering sind uns m Bintypen und n Objekte gegeben. Ein Bintyp Mj hat einen Bedarf dj und einen Profit rj. Jedes Objekt Jt hat eine Größe pt. Ein Bin vom Typ Mj heißt abgedeckt, wenn die Summe der Größen der ihm zugewiesenen Objekte mindestens dj ist. Wenn ein Bin vom Typ Mj abgedeckt ist, erzielen wir einen Profit von rj. Ziel ist es, die Objekte Bins zuzuweisen, sodass der erzielte Gesamtprofit maximiert wird. Wir untersuchen zwei Modelle, die sich in der Verfügbarkeit von Bintypen unterscheiden. Im Unit-Supply-Modell steht uns von jedem Bintyp genau ein Bin zur Verfügung. Im Gegensatz dazu stehen uns im Infinite-Supply-Modell von jedem Bintyp beliebig viele Bins zur Verfügung. Das Unit-Supply-Modell ist daher eine Verallgemeinerung des Infinite-Supply-Modells. Für alle Modelle zeigen wir beinahe scharfe obere und untere Schranken. / In this thesis we study algorithms for scheduling problems. We investigate semi-online minimum makespan scheduling and generalized bin covering. In online minimum makespan scheduling we are given a set of m machines and n jobs, where each job Jt is specified by a processing time. The jobs arrive one by one and we have to assign them to the machines without any knowledge about future incoming jobs. The load of a machine is defined to be total processing time of the assigned jobs. The goal is to place the jobs on the machines such that the maximum load of a machine is minimized. In semi-online minimum makespan scheduling this strict setting is softened. We investigate three different models. In the first setting an algorithm is given an advice on the total processing time of the jobs. In the second setting we may reassign jobs upto a limited amount. The third semi-online setting we study is minimum makespan scheduling with parallel schedules. In this problem an algorithm may maintain several schedules, the best of which is output after the arrival of the entire job sequence. In generalized bin covering we are given m bin types and n items. Each bin type Mj is specified by a demand dj and a revenue rj. Each item Jt has a size pj. A bin of type Mj is said to be covered if the total size of the assigned items is at least the demand dj. Then the revenue rj is earned. The goal is to find an assignment of items to bins maximizing the total obtained revenue. We study two models of bin supply. In the unit supply model there is only one bin of each type available. By contrast in the infinite supply model each bin type is available arbitrarily often, and hence the former is a generalization of the latter. We provide nearly tight upper and lower bounds for all models.

Diese Arbeit beschäftigt sich mit Scheduling von Tasks in Computersystemen. Wir untersuchen sowohl die in neueren Arbeiten betrachtete Zielfunktion zur Energieminimierung als auch die klassische Zielfunktion zur Lastbalancierung auf mehreren Prozessoren. Beim Speed-Scaling mit Sleep-State darf ein Prozessor, der zu jedem Zeitpunkt seine Geschwindigkeit anpassen kann, auch in einen Schlafmodus übergehen. Unser Ziel ist es, den Energieverbrauch zu minimieren. Wir zeigen die NP-Härte des Problems und klären somit den Komplexitätsstatus. Wir beweisen eine untere Schranke für die Approximationsgüte für eine spezielle natürliche Klasse von Schedules. Ferner entwickeln wir eine Familie von Algorithmen, die gute Approximationsfaktoren liefert, und zeigen, dass diese sogar Lösungen liefert, die optimal für die zuvor erwähnte Klasse von Schedules sind. Anschließend widmen wir unsere Aufmerksamkeit dem folgenden Termin-basierten Scheduling-Problem. Es seien mehrere Prozessoren gegeben, wobei jeder einzelne Prozessor zu jedem Zeitpunkt seine Geschwindigkeit anpassen kann. Ziel ist es wie zuvor, den Energieverbrauch des erzeugten Schedules zu minimieren. Für den Offline-Fall entwickeln wir einen optimalen Polynomialzeit-Algorithmus. Für das Online-Problem erweitern wir die zwei bekannten Ein-Prozessor-Algorithmen Optimal Available und Average Rate. Wir zeigen, dass diese den gleichen bzw. einen um die additive Konstante von eins vergrößerten kompetiven Faktor haben. Bei der Lastbalancierung auf mehreren Prozessoren betrachten wir Offline-Load-Balancing auf identischen Maschinen. Unser Ziel ist es, die Current-Load für temporäre Tasks mit identischem Gewicht zu minimieren. Wir zeigen, dass eine Lösung mit maximaler Imbalance von eins immer existiert und entwickeln einen effizienten Algorithmus, der solche Lösungen liefert. Zum Schluss beweisen wir die NP-Härte von zwei Verallgemeinerungen des Problems. / This thesis studies problems of scheduling tasks in computing environments. We consider both the modern objective function of minimizing energy consumption, and the classical objective of balancing load across machines. We first investigate offline deadline-based scheduling in the setting of a single variable-speed processor that is equipped with a sleep state. The objective is that of minimizing the total energy consumption. Apart from settling the complexity of the problem by showing its NP-hardness, we provide a lower bound of 2 for general convex power functions, and a particular natural class of schedules. We also present an algorithmic framework for designing good approximation algorithms. Furthermore, we give tight bounds for the aforementioned particular class of schedules. We then focus on the multiprocessor setting where each processor has the ability to vary its speed. We first study the offline problem and show that optimal schedules can be computed efficiently in polynomial time. Regarding the online problem and a natural class of power functions, we extend the two well-known single-processor algorithms Optimal Available and Average Rate. We prove that Optimal Available has the same competitive ratio as in the single-processor case. For Average Rate we show a competitive factor that increases by an additive constant of one compared to the single-processor result. With respect to load balancing, we consider offline load balancing on identical machines, with the objective of minimizing the current load, for temporary unit-weight jobs. The problem can be seen as coloring n intervals with k colors, such that for each point on the line, the maximal difference between the number of intervals of any two colors is minimal. We prove that a coloring with maximal difference at most one is always possible, and develop a fast polynomial-time algorithm for generating such a coloring. Lastly, we prove that two generalizations of the problem are NP-hard.