Unter Scheduling bzw. Zeitablaufsteuerung 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.
Begriffsdefinitionen
Jobs ("Aufträge") sind definiert durch die Durchführung bestimmter Operationen unter Verwendung von Maschinen. Sie werden durch die folgenden Daten näher spezifiziert:
- Bearbeitungszeit ("processing time"): Die Zeit, die ein Job an einer (bestimmten) Maschine bearbeitet werden muss.
- Einlastzeit ("release date"): Der Zeitpunkt, zu dem der Job im System ankommt – zu diesem Zeitpunkt kann frühestens mit seiner Bearbeitung begonnen werden.
- Gewicht ("weight"): Ein Prioritätsfaktor, der den Job in Relation zur Bedeutung der anderen Jobs im System beschreibt.
- Fertigstellungstermin ("due date"): Zu diesem Zeitpunkt sollte der Job abgearbeitet sein (z.B. um eine beim Kunden angekündigte Lieferung zu erfüllen oder einen Nutzer vor dem Computer nicht zu lange warten zu lassen). Dieser Termin muss ggf. nicht notwendigerweise eingehalten werden. Ein unbedingt einzuhaltender Fertigstellungstermin wird als Deadline bezeichnet.
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").
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
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 sogenannten Branch and Bound-Verfahren oder dem Johnson-Algorithmus zu lösen.
Scheduling in der Informatik
Scheduling (dt.: Prozessverwaltung) ist eine Aufgabe eines Betriebssystems. Es bezeichnet die faire Verwaltung von mehreren Prozessen, die auf einem Computer ausgeführt werden
Kriterien
Es gibt verschiedene Kriterien für einen guten Scheduling-Algorithmus. Besonders wichtig sind die folgenden (die sich z.T. widersprechen):
- Fairness: gerechte Verteilung der Prozessorzeit
- Effizienz: vollständige Auslastung der CPU
- Antwortzeit: interaktive Prozesse sollen schnell reagieren
- Verweilzeit: Aufgaben im Batchbetrieb sollen möglichst schnell ein Ergebnis liefern
- Durchsatz: Maximierung der Anzahl der Aufträge, die innerhalb einer bestimmten Zeitspanne ausgeführt werden
Scheduling-Verfahren
Literatur
- Conway, R., Maxwell, W., Miller, L.: Theory of Scheduling. Addison-Wesley, Reading (USA) 1967
- Günther, H. O. und H. Tempelmeier (2000). Produktion und Logistik. (4. Aufl.) New York u.a.: Springer.
- Ow, P. S. und T. E. Morton (1989). The single machine early/tardy problem.
In: Management Science, Volume 35, No. 2, S. 177-192 - Pinedo, M. (1995). Scheduling: Theory, Algorithms and Systems. Englewood Cliffs, New Jersey: Prentice-Hall
- Pinedo, M. und X. Chao (1999). Operations Scheduling with Applications in Manufacturing and Services. Boston: Irwin/McGraw-Hill