Scheduling

Article on other languages:

• Ordonnancement
• 스케줄링
• Schemaläggning

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

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 Aufträge wann und an welchen Produktionsmaschinen ausgeführt werden, steuert also die Produktionsprozesse. In der Informatik legt Scheduling meist fest, welche Prozesse wann und wie viel Prozessorzeit und Arbeitsspeicher 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. Statt direkt den Durchsatz zu maximieren, optimieren viele Verfahren stattdessen die Effizienz, das heißt die zur Verfügung stehenden Ressourcen werden möglichst vollständig ausgelastet. Beide Kriterien sind gleichwertig, das heißt die Erfüllung des einen bringt stets die Erfüllung des anderen mit sich.
• 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.
• 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 Implementation in Hochgeschwindigkeits-Switchen ist es wichtig die Komplexität zu begrenzen.

Neben diesen allgemeinen Optimierungskriterien werden gelegentlich weitere Nebenbedingungen verlangt, z. B:

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

Präemptive und nicht-präemptive Verfahren

Man unterscheidet präemptive (preemptive, „vorzeitig leerende“) von nicht-präemptiven Verfahren. Ein nicht-präemptives 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 (blockiert) und verharrt in seinem momentanen Zustand, bis ihm wieder 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 (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:
• 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, d. h. 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 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 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, 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 Parallele Maschinenmodell ist eine Generalisierung des Einmaschinen 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

Prozess-Scheduling

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.

Festplatten-Scheduling

Der Festplatten-Scheduler ist für die zeitliche Verwaltung von Schreib- und Leseaufträgen des Betriebssystemes an die Festplatte verantwortlich.

Der Datenbank-Scheduler

In Datenbankverwaltungssystemen verwaltet ein Scheduler die Schreib- und Lesezugriffe der einzelnen Transaktionen auf die Daten, um Verstöße gegen das ACID-Prinzip zu vermeiden.

Ziele

• Durchsatz der Anlage zu maximieren
• Antwortzeiten minimieren
• Ressourcenauslastung maximieren
• vorhersagbares Verhalten zu zeigen
• geringsmöglichen Verwaltungsaufwand (overhead) zu benötigen
• determiniert zu sein, d.h. zu garantieren, dass ein Prozess innerhalb endlicher Zeit abgearbeitet wird,
• auch unter hoher Last sinnvoller Arbeit zu leisten und
• fair zu allen Benutzern (Prozessen) zu sein.

Siehe auch:

• Netzplantechnik

Literatur

• Blazewicz, J., Ecker, K.H., Pesch, E., Schmidt, G. und J. Weglarz, Scheduling Computer and Manufacturing Processes, Berlin (Springer) 2001, ISBN 3-540-41931-4
• Conway, R., Maxwell, W., Miller, L.: Theory of Scheduling. Addison-Wesley, Reading (USA) 1967
• Günther, H.-O. und H. Tempelmeier, Produktion und Logistik, 6. Aufl., Berlin (Springer) 2005, ISBN 3-540-23246-X
• 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
• Schmidt, G., Prozessmanagement, Berlin (Springer) 2002, ISBN 3-540-43170-5