Scheduling

Unter Scheduling (englisch für „Zeitplanerstellung“), auch Zeitablaufsteuerung genannt, versteht man die Erstellung eines Ablaufplanes (schedule), der Prozessen zeitlich begrenzt Ressourcen zuweist (Allokation). Scheduling findet hauptsächlich in der Betriebswirtschaftslehre und der Informatik Anwendung.

In der Betriebswirtschaft 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 legt Scheduling meist fest, welche Prozesse wann und wie viel Prozessorzeit erhalten.

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 die folgenden Ausprägungen der „Echtzeit-Fähigkeit“: „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 (preemptive: „vorwegnehmend“) von kooperativen Verfahren. Ein kooperatives Scheduling-Verfahren übergibt einem Prozess die benötigten Ressourcen und wartet, bis dieser die Ressourcen wieder freigibt bzw. bis dieser vollständig abgearbeitet ist und dadurch die Ressourcen wieder freigibt. Ein präemptives Verfahren kann dem Prozess Ressourcen vor 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 wieder Ressourcen durch den Scheduler zugeteilt werden.

Spezielle Begriffe der Betriebswirtschaftslehre

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

• Auftrag (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 (task) sind die technisch operationellen Inhalte der Arbeit, die in einem Auftrag auszuführen ist.
• Bearbeitungszeit (processing time) ist die zeitliche Dauer, die ein Auftrag an einer (bestimmten) Maschine bearbeitet werden muss.
• Einlastzeit (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 (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 (due date) bezeichnet den Zeitpunkt, zu dem ein Auftrag abgearbeitet sein sollte. Hier werden nur unbedingt einzuhaltende Fertigstellungstermine 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 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ählt unter Anderem das obige Beispiel und sämtlichen 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 vorgegeben 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

Scheduling-Probleme werden häufig durch die Systemkonfiguration, die vorgegebenen Einschränkungen und die zugrunde liegende Zielsetzung definiert.

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

Die Erzeugung eines Ablaufplans ist ein wichtiger Teil aller Computersysteme, bei denen mehrere Funktionen um die selben Ressourcen konkurrieren können. Für die verschiedenen Bereiche, bei denen Ablaufpläne benötig 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 Betriebssystemes an die Festplatte 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 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

• Blazewicz, J., Ecker, K.H., Pesch, E., Schmidt, G. und Weglarz, J.: Scheduling Computer and Manufacturing Processes. Berlin: Springer, 2001, ISBN 3-540-41931-4
• Conway, R., Maxwell, W. und Miller, L.: Theory of Scheduling. Reading: Addison-Wesley, 1967
• Günther, H.-O. und Tempelmeier, H.: Produktion und Logistik, 6. Aufl., Berlin: Springer, 2005, ISBN 3-540-23246-X
• Ow, P.S. und Morton, T.E.: The single machine early/tardy problem. In: Management Science, Vol. 35, No. 2, S. 177–192, 1989
• Pinedo, M.: Scheduling: Theory, Algorithms and Systems. Englewood Cliffs, New Jersey: Prentice-Hall, 2008
• Pinedo, M. und Chao, X.: Operations Scheduling with Applications in Manufacturing and Services. Boston: Irwin/McGraw-Hill, 1999
• Schmidt, G.: Prozessmanagement, Berlin: Springer, 2002, ISBN 3-540-43170-5