Gegeben $n$ Druckjobs, die jeweils eine Druckdauer $t_i$ und eine Deadline $d_i$ haben; $1$ Drucker
Aufgabe: Finde eine Reihenfolge der Druckjobs, beginnend bei Zeit $0$, so dass die maximale Verspätung eines Druckjobs minimiert wird (d.h. über alle Jobs soll die maximale Verspätung (Fertigstellungszeitpunkt minus Deadline) minimiert werden).
Idee 1: Sortiere die Druckjobs nach aufsteigender Länge.
Idee 2: Betrachte die "slack time" eines Druckjobs, definiert als $d_i - t_i$. Die slack time gibt also an, wie viel Spielraum wir für einen Job haben.
Sortiere die Druckjobs aufsteigend nach slack time.
Idee 3 : Sortiere die Druckjobs aufsteigend nach Deadline ("Earliest Deadline First").
