Wir untersuchen drei Scheduling-Problemfamilien auf ihre komplexitätstheoretische Härte und zeigen, welche algorithmischen Ansätze für diese Probleme geeignet sind. Im ersten Modell, das wir neu einführe und Server Cloud Scheduling nennen, werden große Abläufe als Sammlung von Jobs mit Abhängigkeiten gegeben. Die Jobs können auf einem Server ausgeführt werden, der beschränkt, aber kostenlos ist, oder in die Cloud ausgelagert werden, die unendliche Parallelität erlaubt, aber Kosten verursacht. Das Ziel ist die Minimierung der Laufzeit unter Einhaltung eines Budgets oder Minimierung der Kosten unter Einhaltung einer Frist. Unsere Ergebnisse beinhalten unter anderem FPTAS, die auf dynamischer Programmierung basieren, für recht allgemeine Fälle des Modells, und ein starkes NP-härte Ergebnis, das sogar dann gilt, wenn alle Joblängen 1 sind. Zweitens untersuchen wir das Restricted Assignment Interval Problem, bei dem Maschinen in einer bestimmten Reihenfolge gegeben sind und jeder Job nur auf einer konsekutiven Teilmenge der Maschinen ausgeführt werden kann. Ziel ist die Minimierung der Laufzeit. Es ist uns gelungen den ersten Approximationsalgorithmus mit einem konstanten Approximationsfaktor kleiner als 2 für das Problem zu liefern. Der Algorithmus erweitert frühere Ansätze der linearen Programmierung. Zuletzt betrachten wir Many Shared Resources Scheduling. Zusätzlich zu Maschinen und Jobs erhalten wir hier Ressourcen. Jeder Job benötigt eine Ressource, und Jobs, die dieselbe Ressource benötigen, können nicht parallel ausgeführt werden. Ziel ist die Laufzeit zu minimieren. Wir stellen zwei kombinatorische Approximationsalgorithmen vor, eine einfache und elegante 5/3-Approximation und eine technisch aufwendigere 3/2-Approximation. Unser erster Algorithmus schlägt bereits den Stand der Technik.

We study three different families of scheduling problems, discuss their complexity theoretical hardness and show how the problems lend themselves to various algorithmic approaches. First, we introduce a new problem called server cloud scheduling, in which large tasks are given as a collection of smaller jobs with some precedence relation between themselves. Jobs can be processed on a purely sequential but free server or offloaded to the cloud, which allows infinite parallelization but incurs costs. The objective is either to minimize the makespan while adhering to a budget or to minimize the cost while adhering to a deadline. Some of our main results are dynamic programming based FPTAS for fairly general special cases of the model; and a strong NP-hardness result that holds even when all processing times are equal to 1. Second, we consider the restricted assignment interval problem, where the machines are given in some order, and each job is only eligible on a consecutive subset of the machines. The objective is to minimize the makespan. We give the first approximation algorithm with a constant approximation ratio less than 2 for restricted assignment interval. The algorithm refines and expands previous linear programming approaches. Last, we consider many shared resources scheduling. In addition to the machines and jobs, we are also given a set of resources. Each job may now require exclusive access to one of the resources during its processing time, or in other words, two jobs needing the same resource may not be scheduled in parallel. The goal is again to minimize the makespan. We present two combinatorial approximation algorithms, a simple and elegant 5/3-approximation and a technically more involved 3/2-approximation. Both of these beat the previous best-known algorithm, which was a 2-approximation.