Scheduling

Scheduling (deutsch „Zeitplanerstellung“; auch Zeitablaufsteuerung; in der Betriebswirtschaftslehre Ablaufplanung^[1][2][3] Maschinenbelegungsplanung^[1][4][5] oder Reihenfolgeplanung^[1][4][6][7] genannt) ist ein Anglizismus für die Erstellung eines Ablaufplanes (englisch schedule), der Prozessen zeitlich begrenzt Ressourcen zuteilt (Allokation).

Das Scheduling folgt auf die summarische Planung der anstehenden Aufgaben. Auf das Einteilen zu einem Pool an Ressourcen folgt später das Einlasten für eine einzelne Instanz dieses Pools.

In der Betriebswirtschaftslehre legt Scheduling meist fest, welche einzelnen Auftragsinstanzen wann (in welcher Reihenfolge) und an welchen Produktionsmaschinen (in welcher Zuordnung) ausgeführt werden, steuert also die Produktionsprozesse vom Abschluss der Auftragsplanung (englisch planning) über die Einlastung (englisch dispatch) in der Ausführung (englisch processing) mit begleitender Auftragssteuerung (englisch control) mit Beobachtung des Zustandes (englisch monitoring) und Rückmeldung von Ereignissen (englisch feedback) bis zum Abschluss aller verketteten Teilprozesse jeder einzelnen Auftragsinstanz. In der Produktionswirtschaft wird auch einfach von Maschinenbelegungsplanung gesprochen.

In der Informatik im Bereich der Betriebssysteme legt Scheduling fest, welche Prozesse wann und wie viel Prozessorzeit erhalten, im Bereich der Datenbanktechnik wird mit dem Scheduling festgelegt, wie parallele Transaktionen ablaufen müssen, ohne die Konsistenz der Datenbank zu verletzen (siehe auch: Scheduler).

Ein gutes Scheduling-Verfahren zeichnet sich dadurch aus, dass es die folgenden Kriterien optimiert:

• Durchsatz: Möglichst viele Prozesse werden in möglichst kurzer Zeit abgearbeitet.
• Effizienz: Die zur Verfügung stehenden Ressourcen werden möglichst vollständig ausgelastet.
• Fairness: Die Ressourcen werden den Prozessen gerecht zugeteilt, das heißt, kein Prozess wird dauerhaft vernachlässigt. Man sagt auch, das Verfahren vermeide das „Verhungern“ (starvation) von Prozessen.
• Transparenz: Die einzelnen Schritte der Prozesse werden in ihrem Ablauf und in ihrer Zuordnung zu Ressourcen klar erkannt und getrennt.
• Termineinhaltung: Prozesse, die zu einem bestimmten Termin beendet sein müssen, werden so geplant, dass der Termin eingehalten wird. Während in der Betriebswirtschaft präzise einzuhaltende Termine „Deadlines“ und ungefähr einzuhaltende Termine „Fertigstellungstermine“ heißen, spricht man in der Informatik nur von Deadlines und unterscheidet stattdessen folgende Arten von Echtzeitanforderungen: „Harte Echtzeit“ hält alle Deadlines präzise ein, „weiche Echtzeit“ hält Deadlines einigermaßen ein und Best Effort („so gut wie möglich“) sichert keine Einhaltung der Deadlines zu.
• Einfach und schnell. Für eine Implementierung in Hochgeschwindigkeits-Switchen ist es wichtig, die Komplexität zu begrenzen.

Neben diesen allgemeinen Optimierungskriterien werden gelegentlich weitere Nebenbedingungen verlangt, zum Beispiel:

• Verweilzeit. Prozesse sollten möglichst schnell beendet sein.

Man unterscheidet präemptive (von englisch preemptive, ‚vorwegnehmend‘) Verfahren von nicht-präemptiven bzw. kooperativen:

• Ein kooperatives Scheduling-Verfahren übergibt einem Prozess die benötigten Ressourcen und wartet, bis der Prozess diese Ressourcen wieder freigibt bzw. bis er vollständig abgearbeitet ist und dadurch die Ressourcen wieder freigibt.
• Ein präemptives Verfahren dagegen kann dem Prozess Ressourcen bereits vor der Fertigstellung wieder entziehen, um sie zwischenzeitlich anderen Prozessen zuzuteilen. Der Prozess wird dabei in seiner Ausführung unterbrochen (er geht in den Zustand ‚bereit‘ über) und verharrt dort, bis ihm durch den Scheduler erneut Ressourcen zugeteilt werden.

Betriebswirtschaftslehre und Informatik haben verschiedene Terminologien für dieselben Sachverhalte. In der Betriebswirtschaftslehre verwendet man folgende Begriffe:

• Auftrag (englisch job) ist gleichbedeutend mit „Prozess“ und bezeichnet die Durchführung bestimmter Operationen unter Verwendung von Maschinen. Sie werden durch die folgenden Daten näher spezifiziert:
• Arbeitsschritte (englisch task) sind die technisch operationellen Inhalte der Arbeit, die in einem Auftrag auszuführen ist.
• Bearbeitungszeit (englisch processing time) ist die zeitliche Dauer, in der ein Auftrag an einer (bestimmten) Maschine bearbeitet werden muss.
• Einlastzeit (englisch release date) ist der Zeitpunkt, zu dem der Auftrag im System ankommt, also der Zeitpunkt, zu dem frühestens mit der Bearbeitung begonnen werden kann.
• Gewicht (englisch weight) ist gleichbedeutend mit dem Nebenkriterium „Verweilzeit“ und bezeichnet einen Prioritätsfaktor, der die Dringlichkeit eines Auftrags im Vergleich zu anderen Aufträgen im System beschreibt.
• Fertigstellungstermin (englisch due date) bezeichnet den Zeitpunkt, zu dem ein Auftrag abgearbeitet sein sollte. Hier werden nur unbedingt einzuhaltende Fertigstellungstermine als englisch 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 zum Beispiel für die Durchführung von Jobs Ressourcen (zum Beispiel 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ählen unter anderem das obige Beispiel und sämtliche Einschränkungen physikalischer Natur (zum Beispiel Rüstzeiten). Weiche Einschränkungen sind solche, die zur Optimierung der Pläne dienen, aber nicht unbedingt eingehalten werden müssen. So besteht gegebenenfalls die Möglichkeit, nach voller Auslastung der vorhandenen personellen Kapazitäten zusätzliche Kapazität in Form von Überstunden bereitzustellen.

Weitere typische Restriktionen sind die von der Planung vorgegebenen Fertigstellungstermine, die aber in der Regel schwächere Einschränkungen darstellen als die ressourcenbedingten oder technischen, 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 vorgegebenen Einschränkungen und die zugrunde liegende Zielsetzung definiert. Die verschiedenen Modelle werden durch ein etabliertes System Kriterien klassifiziert.

Die einfachste Systemkonfiguration ist das Einmaschinenmodell. 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, sodass 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 einfacher Prioritätsregeln bestimmte Ziele mit Sicherheit zu erreichen.

Das parallele Maschinenmodell ist eine Generalisierung des Einmaschinenmodells. 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. Job-Shop-Probleme treten zum Beispiel in der Halbleiterindustrie bei der Wafer-Fertigung auf; ebenso kann man aber auch ein Krankenhaus als typisches Beispiel für einen Job-Shop 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, das heißt, wenn ihre Wege identisch sind, spricht man von einem Flow Shop. Ein Flow-Shop ist somit ein spezieller Job-Shop.

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. Gute Näherungslösungen liefern auch Metaheuristiken wie die Evolutionäre Algorithmen^[8][9] oder die Ameisenalgorithmen^[10].

Siehe auch:

• Netzplantechnik

Die Erzeugung eines Ablaufplans ist ein wichtiger Teil aller Computersysteme, bei denen mehrere Funktionen um dieselben Ressourcen konkurrieren können. Für die verschiedenen Bereiche, bei denen Ablaufpläne benötigt werden, werden teils hochoptimierte Scheduler entwickelt. Entsprechend kann man Scheduler sowohl auf Grund ihrer Funktionsweise als auch anhand des speziellen Einsatzgebietes unterscheiden.

Beispielhaft für wichtige Einsatzgebiete, für die hochoptimierte Scheduler entwickelt werden, sind folgende:

• Der Prozess-Scheduler (dt.: Prozessverwaltung/Ressourcenzuteilung/Zeitplanung) ist Bestandteil von Betriebssystemen. Er ist für die faire Verwaltung von mehreren Prozessen zuständig, die auf einem Computer ausgeführt werden.
• Der Festplatten-Scheduler ist für die zeitliche Verwaltung von Schreib- und Leseaufträgen des Betriebssystems an das Festplattenlaufwerk verantwortlich.
• In Datenbankverwaltungssystemen verwaltet ein Transaktionsscheduler die Schreib- und Lesezugriffe der einzelnen Transaktionen auf die Daten, um Verstöße gegen das ACID-Prinzip zur Einhaltung der Datenkonsistenz zu vermeiden.
• Beim Job-Scheduling (Task-Scheduling) geht es um die korrekte Ansteuerung von Jobs (Batchjobs, Programmstarts etc.) in meist größeren IT-Umgebungen, die in zeitlichen und weiteren Abhängigkeiten untereinander stehen.

• J. Blazewicz, K. H. Ecker, E. Pesch, G. Schmidt, J. Weglarz: Scheduling Computer and Manufacturing Processes. Springer, Berlin 2001, ISBN 3-540-41931-4.
• Peter Brucker: Scheduling Algorithms. 5. Auflage. Springer, 2007, ISBN 978-3-540-69515-8.
• R. Conway, W. Maxwell, L. Miller: Theory of Scheduling. Addison-Wesley, Reading 1967.
• Wolfgang Domschke, Armin Scholl, Stefan Voß: Produktionsplanung – Ablauforganisatorische Aspekte. Springer, Berlin 1993, ISBN 3-540-56585-X.
• Florian Jaehn, Erwin Pesch: Ablaufplanung – Einführung in Scheduling. Springer, 2014, ISBN 978-3-642-54438-5.
• P. S. Ow, T. E. Morton: The single machine early/tardy problem. In: Management Science. Vol. 35, No. 2, 1989, S. 177–192.
• M. Pinedo: Scheduling: Theory, Algorithms and Systems. Prentice-Hall, Englewood Cliffs, New Jersey 2008.
• M. Pinedo, X. Chao: Operations Scheduling with Applications in Manufacturing and Services. Irwin/McGraw-Hill, Boston 1999.
• G. Schmidt: Prozessmanagement. Springer, Berlin 2002, ISBN 3-540-43170-5.

1. ↑ ^{a b c} Theodor Nebl: Einführung in die Produktionswirtschaft. 2. Auflage. 1997, ISBN 3-486-24326-8, S. 341 f.
2. ↑ Dietrich Adam: Produktionsmanagement. 9. Auflage. 1998, ISBN 3-409-69117-0, S. 535f.
3. ↑ Horst Seelbach: Ablaufplanung. In: Waldemar Wittmann/Werner Kern/Richard Köhler/Hans U. Küpper/Klaus von Wysocki: Handwörterbuch der Betriebswirtschaft. 5. Auflage, 1993, Sp. 1 f.
4. ↑ ^{a b} Hans Corsten: Produktionswirtschaft. 12. Auflage. 2009, ISBN 978-3-486-58751-7, S. 510.
5. ↑ Jörg Heuer: Das Multiprocessor Scheduling-Problem mit reihenfolgeabhängigen Rüstzeiten. 2004, ISBN 3-8244-8253-3, S. 9.
6. ↑ Holger Luczak, Walter Eversheim (Hrsg.): Produktionsplanung und -steuerung. 2. Auflage. 1999, ISBN 3-540-65559-X, S. 48.
7. ↑ DietrichProduktionsmanagement. 9. Auflage. 1998, ISBN 3-409-69117-0, S. 120.
8. ↑ Evolutionary Scheduling (= Studies in Computational Intelligence (SCI). Band 49). Springer, Berlin, Heidelberg 2007, ISBN 978-3-540-48582-7, doi:10.1007/978-3-540-48584-1. 
9. ↑ Bahriye Akay, Xin Yao: Recent Advances in Evolutionary Algorithms for Job Shop Scheduling. In: A. Sima Uyar, Ender Ozcan, Neil Urquhart (Hrsg.): Automated Scheduling and Planning (= Studies in Computational Intelligence (SCI). Band 505). Springer, Berlin, Heidelberg 2013, ISBN 978-3-642-39303-7, S. 191–224, doi:10.1007/978-3-642-39304-4_8. 
10. ↑ R.F. Tavares Neto, M. Godinho Filho: Literature review regarding Ant Colony Optimization applied to scheduling problems: Guidelines for implementation and directions for future research. In: Engineering Applications of Artificial Intelligence. Band 26, Nr. 1, Januar 2013, ISSN 0952-1976, S. 150–161, doi:10.1016/j.engappai.2012.03.011 (researchgate.net [abgerufen am 31. Dezember 2024]).