Beispiel für List Scheduling mit 2 Maschinen

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:
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:
Nach 2 zugewiesenen Jobs
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 3 Jobs
Nach 2 Zeiteinheiten sind der 2. und 3. Job fertig bearbeitet, und beide Maschinen bekommen neue Jobs zugewiesen.
fertig
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.

Zurück