Scheduling

Definition:
Das Problem List-Scheduling sucht nach einer Verteilung von $n$ Jobs der Länge $p_i$ auf $k$ Maschinen, so dass die gesamte Ausführungszeit minimal ist.

Approximationsalgorithmus: [Graham]
Suche Maschine mit minimaler Ausführungszeit der Jobs (am Anfang beliebige Maschine) und ordne ihr Job $i$ zu. Wiederhole den Vorgang bis alle Jobs zugeordnet sind. Dieser Algorithmus garantiert Güte $2-\frac{1}{k}$.

Approximationsalgorithmus: (Longest Processing Time List-Scheduling)
Jobs sind nach Ausführungszeiten vorsortiert. Zuerst werden die Jobs mit der längsten Zeit zugeordnet. Dieser Algorothmus garantiert Güte $\frac{4}{3}-\frac{1}{3k}$.

Analyse:
List-Scheduling ist ähnlich Knapsack nicht beschränkt in der Eingabe $p_i$ und somit pseudo-polynomial. Auch hier lassen sich die Zeiten $p_i$ skalieren.

Korollar: List-Scheduling $\in PTAS$