Scheduling

Scheduling (deutsch „Zeitplanerstellung“; auch Zeitablaufsteuerung; in der Betriebswirtschaftslehre Ablaufplanung Maschinenbelegungsplanung oder Reihenfolgeplanung genannt) ist ein Anglizismus für die Erstellung eines Ablaufplanes (englisch schedule), der Prozessen zeitlich begrenzt Ressourcen zuteilt (Allokation).

Allgemeines

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).

Kriterien

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.

Präemptive und nicht-präemptive Verfahren

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.

Spezielle Begriffe der Betriebswirtschaftslehre

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

Siehe auch: Klassifikation von Maschinenbelegungsmodellen

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.

Siehe auch:

• Netzplantechnik

Scheduling in der Informatik

→ Hauptartikel: Scheduling (Informatik)

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.

Datei:Schedulingprobleme HNI.png

Verschiedene Ebenen von Schedulingproblemen

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.

Literatur

• 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.