Scheduling
Unter Scheduling versteht man die Zuordnung von gegebenen, mengen- und terminmäßig spezifizierten Aufträgen zu Ressourcen und die Bestimmung der zeitlichen Reihenfolge, in der die zu einem bestimmten Zeitpunkt an einer Ressource wartenden Aufträge bearbeitet werden sollen. Als Ergebnis wird ein Plan ("schedule") aufgestellt.
Table of contents |
2 Scheduling-Probleme 3 Scheduling in der Informatik 4 Literatur |
Jobs ("Aufträge") sind definiert durch die Durchführung bestimmter Operationen unter Verwendung von Maschinen. Sie werden durch die folgenden Daten näher spezifiziert:
Bei der Lösung von Scheduling-Problemen müssen diverse Einschränkungen ("constraints") berücksichtigt werden – so werden z.B. für die Durchführung von Jobs Ressourcen (z.B. Maschinen, Monteure, Prozessoren etc.) eingesetzt, die nur in beschränktem Umfang verfügbar sind.
Man unterscheidet häufig zusätzlich zwischen harten Einschränkungen ("hard constraints"), die unbedingt einzuhalten sind, und weichen Einschränkungen ("soft constraints"). Zu den harten Einschränkungen zählt u.a. das obige Beispiel und sämtlichen Einschränkungen physikalischer Natur (z.B. Rüstzeiten). Weiche Einschränkungen sind solche, die zur Optimierung der Pläne dienen, aber nicht unbedingt eingehalten werden müssen. So besteht ggf. die Möglichkeit, nach voller Auslastung der vorhandenen personellen Kapazitäten zusätzliche Kapazität in Form von Überstunden in Anspruch zu nehmen.
Weitere typische Restriktionen sind die von der Planung vorgegeben Fertigstellungstermine, die aber in der Regel schwächere Einschränkungen darstellen als die ressourcenbedingten oder technischen Einschränkungen, sowie Einlastzeiten, die verhindern sollen, dass mit der Produktion begonnen wird, obwohl benötigte Materialien noch nicht vorhanden sind.
Scheduling-Probleme werden häufig durch die Systemkonfiguration, die vorgegeben Einschränkungen und der zugrunde liegenden Zielsetzung definiert.
Die einfachste Systemkonfiguration ist das single-machine Modell. Es existiert nur eine Maschine, auf der Jobs eingeplant werden müssen. Das Modell ist sehr häufig anzutreffen – hat man beispielsweise eine Systemkonfiguration mit mehreren Maschinen gegeben, bei denen es aber eine einzelne Engpassmaschine gibt, so dass sich das Scheduling der anderen Maschinen nach dem Plan des Engpasses richten muss, wird das vorliegende Problem auf das single-machine Problem zurückgeführt. Durch die geringe Komplexität ist es möglich, mittels einfachen Prioritätsregeln bestimmte Ziele mit Sicherheit zu erreichen.
Das parallel-machine Modell ist eine Generalisierung des one-machine Modells. Mehrere Maschinen desselben Typs arbeiten parallel. Ein ankommender Job kann von jeder dieser Maschinen bearbeitet werden.
Oft müssen Jobs unterschiedliche Operationen an verschiedenen Maschinen durchlaufen, so dass sie unterschiedliche Wege aufweisen. Eine solche Umgebung bezeichnet man als Job Shop Modell. Job Shop Probleme treten z.B. in der Halbleiterindustrie bei der Wafer-Fertigung auf; ebenso kann man aber auch ein Krankenhaus als typisches Beispiel für ein Job Shop Modell betrachten: Die Patienten sind die Jobs, die unterschiedlichen Wegen folgend, an verschiedenen Stellen im Krankenhaus (Anmeldung, Wartezimmer, Arztraum, Röntgenraum,…) behandelt werden.
Wenn alle Jobs die gleichen Maschinen in der gleichen Reihenfolge durchlaufen, d.h. wenn ihre Wege identisch sind, spricht man von einem Flow Shop Modell. Ein Flow Shop Modell ist somit ein eingeschränktes Job Shop Modell.
Typische Flow Shops findet man beispielsweise in der Metallherstellungsindustrie oder der Chargen- und Fließfertigung in der Lebensmittelproduktion.
Scheduling-Probleme treten an vielen Stellen in Produktionsvorgängen auf und sind in den meisten Fällen nur sehr schwierig optimal lösbar, da sie häufig in die Klasse der NP-vollständigen Probleme fallen. In der Praxis reichen aber oft gute Näherungslösungen aus.
Ein häufig auftretendes und praxisrelevantes Problem stellt das single-machine early/tardy Problem dar. In einer single-machine Umgebung sollen eine Reihe Jobs auf einer Maschine eingeplant werden, so dass die auftretenden early costs und tardy costs möglichst minimal sind. Die Zielsetzung deckt sich mit dem Ziel der Just in time-Produktion. Dieses Problem ist NP-vollständig.
Die angesprochenen Scheduling-Probleme lassen sich alle als ganzzahlige Optimierungsprobleme formulieren. Derartige Probleme versucht man vorwiegend mit so genanten Branch and Bound-Verfahren zu lösen.
Scheduling (dt.: Prozessverwaltung) ist eine Aufgabe eines Betriebssystems. Es bezeichnet die faire Verwaltung von mehreren Prozessenen, die auf einem Computer ausgeführt werden
Begriffsdefinitionen
Sowohl Jobs, die vor dem geplanten Fertigstellungstermin abgearbeitet werden, als auch Jobs, die ihn nicht einhalten können und erst später beendet werden, verursachen Kosten. Diese werden als "early costs" und "tardy costs" bezeichnet.
Die Reihenfolge, in der ein Job mehrere Maschinen durchläuft, bezeichnet man als Weg ("route").Scheduling-Probleme
Scheduling in der Informatik
Kriterien
Es gibt verschiedene Kriterien für einen guten Scheduling-Algorithmus. Besonders wichtig sind die folgenden (die sich z.T. widersprechen):Scheduling-Verfahren
Literatur
In: Management Science, Volume 35, No. 2, S. 177-192