Voraussetzungen:
In diesem Beispiel gibt es keine release times
und keine precedence constraints. Der erste Job in der Sequenz kann
also immer als nächstes zugewiesen
werden.
Anfangszustand:
Hier wurde noch kein Job zugewiesen, also sind alle Maschinen frei,
deshalb weist List Scheduling beiden Maschinen die ersten zwei Jobs
in der Sequenz zu:
Nachdem eine Zeiteinheit abgelaufen ist, hat die erste Maschine den ersten
Job vollständig bearbeitet und bekommt den nächsten Job in
der Sequenz zugewiesen:
Nach 2 Zeiteinheiten sind der 2. und 3. Job fertig bearbeitet, und beide
Maschinen bekommen neue Jobs zugewiesen.
Jetzt sind alle Jobs der Sequenz zugewiesen, wodurch der ersten Maschine
nach der 3. Zeiteinheit kein Job mehr zugewiesen werden kann und die
Maschine von da an Leerlauf hat. Nach 4 Zeiteinheiten ist auch der
letzte Job beendet wodurch sich ergibt, dass der Makespan 4
Zeiteinheiten beträgt. In diesem Beispiel liefert List
Scheduling eine optimale Lösung für das Problem, das ist
aber nicht immer so. Hätte der letzte Job in der Sequenz eine
Laufzeit von 3 Zeiteinheiten hätte, bräuchte List
Scheduling 5 Zeiteinheiten, um die gesamte Sequenz abzuarbeiten, ein
optimaler Offlinealgorithmus benötigte dafür nur 4
Zeiteinheiten.