Scheduling Algorithmen

Ein einfaches Scheduling Problem mit einer effizienten, optimalen Lösung

Inhalt

• Erklärung des Problems
• Berechnung der Zielfunktion
• Optimierung der Zielfunktion
• Eine interaktive Animation zur weiteren Vertiefung

 

Erklärung des Problems

Ein Beispiel für einen sehr einfachen und beweisbar optimalen Algorithmus zur Lösung eines Scheduling Problems ist die folgende Variante des Job-Shop Scheduling:

Gegeben sei eine Maschine, welche verschiedene Aufgaben verarbeiten muss. Die Aufgaben werden sequentiell (also nacheinander) abgearbeitet. Die Aufgaben können unterschiedliche Verarbeitungszeiten haben und sind voneinander unabhängig: Die Reihenfolge ihrer Verarbeitung ist beliebig. Die Zielfunktion soll die Summe aller Beendigungszeiten minimieren. Unter der Beendigungszeit versteht man diejenige Zeit, welche vom Beginn der gesamten Verarbeitung an verstreicht, bis eine Aufgabe erledigt ist. Abbildung 1 soll dies verdeutlichen.

Abbildung 1: Eine Maschine muss drei Aufgaben sequentiell verarbeiten. Für die angegebene Sequenz sind die Verarbeitungszeiten und die Beendigungszeiten angegeben.

 

Berechnung der Zielfunktion

Möchte man die Summe aller Beendigungszeiten minimieren, so muss man sich zuerst überlegen, wie sich diese Summe berechnet. Die Beendigungszeit der Aufgabe i ist die Summe ihrer Verarbeitungszeit und der Beendigungszeit der Aufgabe i-1. Wendet man diese Erkenntnis rekursiv auf alle Verarbeitungszeiten an, so sieht man folgendes: In der Summe aller Beendigungszeiten von n Aufgaben ist die Verarbeitungszeit der ersten Aufgabe n mal enthalten, die Verarbeitungszeit der zweiten Aufgabe n-1 mal, und so weiter. Abbildung 2 unterstützt diese Erklärungen anhand der drei Aufgaben aus Abbildung 1.

Abbildung 2: Für die Aufgabe a sind die Verarbeitungszeit und die Beendigungszeit identisch. Bei b wird die Beendigungszeit der Aufgabe a mit der Verarbeitungszeit der Aufgabe b addiert. Daraus ergibt sich die Beendigungszeit der Aufgabe b. Bei c geschieht dasselbe mit den Aufgaben b und c. s stellt die Summe aller Beendigungszeiten dar. Zuerst anhand der Addition aller Verarbeitungszeiten, dann unter Verwendung der drei Beendigungszeiten.

Die Summe aller Beendigungszeiten lässt sich also direkt aus den Verarbeitungszeiten der einzelnen Aufgaben berechnen, ohne den Umweg über die einzelnen Beendigungszeiten. Daher ist diese Berechnung sehr effizient. Für das angegebene Beispiel lautet die Formel:

Aus dieser spezifischen Formel folgt eine allgemeine Formel für die Summe aller Beendigungszeiten:

 

Optimierung der Zielfunktion

Wie im Kapitel Erklärung des Problems erwähnt, ist eine Lösung des Problems optimal, wenn sie die Summe aller Beendigungszeiten minimiert. Betrachtet man die obige Formel, so wird klar, wie die Aufgaben angeordnet werden müssen: So, dass ihre Verarbeitungszeiten aufsteigend geordnet sind. Auf diese Weise wird die kürzeste Verarbeitungszeit mit dem grössten Faktor (also mit n) und die längste Verarbeitungszeit mit dem kleinsten Faktor (also mit 1) multipliziert.

Abbildung 3: Hier werden alle möglichen Sequenzen mit den drei Aufgaben aus Abbildung 1 untersucht. Unter jeder Sequenz sind die einzelnen Beendigungszeiten und deren Summe dargestellt. Diejenige Sequenz, welche mit der kürzesten Aufgabe beginnt, minimiert die Zielfunktion. Die umgekehrte Reihenfolge führt zum maximalen Zielfunktionswert.

Die optimale Lösung des ausgewählten Scheduling Problems zu finden, reduziert sich also darauf, die vorgegebenen Aufgaben nach ihren Verarbeitungszeiten zu sortieren. Dazu kann ein beliebiger Sortieralgorithmus (Quicksort, Bubblesort, etc.) verwendet werden. Die so berechnete Lösung ist mathematisch beweisbar optimal gemäss der vorgegebenen Zielfunktion. Allerdings ist sie nicht eindeutig: Wenn mehrere Aufgaben die selbe Verarbeitungszeit aufweisen, dann kann die Reihenfolge dieser Aufgaben beliebig verändert werden, ohne dass die Optimalität der Lösung verändert wird.

 

Eine interaktive Animation zur weiteren Vertiefung

Das folgende Beispielprogramm visualisiert das beschriebene Problem. Die farbigen Balken stellen die verschiedenen Aufgaben dar. Ihre Verarbeitungszeiten steigen von einer Sekunde für die kürzeste Aufgabe in Einerschritten an.

Hinweise zur Benutzung:

• Dieses Applet setzt einen Java 1.1-fähigen Browser voraus.
• Links oben kann die Anzahl der zu verarbeitenden Aufgaben eingestellt werden.
• Die restlichen Buttons werden verwendet, um eine Anordnung neu zu mischen, die optimale oder die schlechteste Lösung zu berechnen.
• Die einzelnen Aufgaben können mit der Maus verschoben werden. Wenn der farbige Balken losgelassen wird, so reiht er sich vor derjenigen Aufgabe in die Sequenz ein, über welcher der Mauszeiger in diesem Moment steht.