imported>PerfektesChaos: tk k

2025-09-23T20:10:30Z

tk k

Neue Seite

'''Scheduling''' (deutsch „Zeitplanerstellung“; auch '''Zeitablaufsteuerung'''; in der [[Betriebswirtschaftslehre]] '''[[Ablaufplanung]]'''<ref name="Nebl">Theodor Nebl: ''Einführung in die Produktionswirtschaft.'' 2. Auflage. 1997, ISBN 3-486-24326-8, S. 341 f.</ref><ref>Dietrich Adam: ''Produktionsmanagement.'' 9. Auflage. 1998, ISBN 3-409-69117-0, S. 535f.</ref><ref>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.</ref> '''Maschinenbelegungsplanung'''<ref name="Nebl" /><ref name="Corsten">Hans Corsten: ''Produktionswirtschaft.'' 12. Auflage. 2009, ISBN 978-3-486-58751-7, S. 510.</ref><ref>Jörg Heuer: ''Das Multiprocessor Scheduling-Problem mit reihenfolgeabhängigen Rüstzeiten.'' 2004, ISBN 3-8244-8253-3, S. 9.</ref> oder '''Reihenfolgeplanung'''<ref name="Nebl" /><ref name="Corsten" /><ref>Holger Luczak, Walter Eversheim (Hrsg.): ''Produktionsplanung und -steuerung.'' 2. Auflage. 1999, ISBN 3-540-65559-X, S. 48.</ref><ref>Dietrich''Produktionsmanagement.'' 9. Auflage. 1998, ISBN 3-409-69117-0, S. 120.</ref> genannt) ist ein [[Anglizismus]] für die Erstellung eines [[Ablaufplan]]es ({{enS|schedule}}), der [[Prozess]]en zeitlich begrenzt [[Ressource]]n zuteilt ([[Ressourcenallokation|Allokation]]).

== Allgemeines ==
Das Scheduling folgt auf die summarische [[Planung]] der anstehenden Aufgaben. Auf das Einteilen zu einem [[Pool (Informatik)|Pool]] an Ressourcen folgt später das [[Dynamisches Scheduling|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 [[Produktionsprozess]]e vom Abschluss der Auftragsplanung ({{enS|planning}}) über die Einlastung ({{enS|dispatch}}) in der Ausführung ({{enS|processing}}) mit begleitender Auftragssteuerung ({{enS|control}}) mit Beobachtung des Zustandes ({{enS|[[monitoring]]}}) und Rückmeldung von Ereignissen ({{enS|[[Feedback (Kommunikation)|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 [[Prozess (Informatik)|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 (Datenbank)|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.
* [[Wirtschaftlichkeit|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 „[[Termin|Deadlines]]“ und ungefähr einzuhaltende Termine „Fertigstellungstermine“ heißen, spricht man in der Informatik nur von Deadlines und unterscheidet stattdessen folgende Arten von [[Echtzeitanforderung]]en: „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 [[Multitasking#Präemptives Multitasking|präemptive]] (von {{enS|preemptive}}, ‚vorwegnehmend‘) Verfahren von nicht-präemptiven bzw. [[Multitasking#Kooperatives Multitasking|kooperativen]]:
* Ein kooperatives Scheduling-Verfahren übergibt einem [[Prozess (Informatik)|Prozess]] die benötigten [[Ressource#Informatik|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:
* [[Fertigungsauftrag|Auftrag]] ({{enS|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:
* [[Arbeitsschritt]]e ({{enS|task}}) sind die technisch operationellen Inhalte der Arbeit, die in einem Auftrag auszuführen ist.
* [[Zeit je Einheit|Bearbeitungszeit]] ({{enS|processing time}}) ist die zeitliche Dauer, in der ein Auftrag an einer (bestimmten) Maschine bearbeitet werden muss.
* Einlastzeit ({{enS|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 ({{enS|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 ({{enS|due date}}) bezeichnet den Zeitpunkt, zu dem ein Auftrag abgearbeitet sein sollte. Hier werden nur unbedingt einzuhaltende Fertigstellungstermine als {{enS|[[Termin#Arten|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 („[[Flaschenhals (Logistik)|constraints]]“) berücksichtigt werden. So werden zum Beispiel für die Durchführung von Jobs [[Ressource]]n (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üstzeit (Technik)|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ätsregel (Produktion)|Prioritätsregeln]] bestimmte Ziele mit Sicherheit zu erreichen.

Das [[Maschinenbelegungsproblem mit parallelen Maschinen|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 Scheduling|Job Shop]]. Job-Shop-Probleme treten zum Beispiel in der [[Halbleiter]]industrie 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 [[Metallurgie|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ändigkeit|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 [[Optimierungsproblem]]e 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 [[Metaheuristik|Metaheuristiken]] wie die [[Evolutionärer Algorithmus|Evolutionäre Algorithmen]]<ref>{{Literatur |Titel=Evolutionary Scheduling |Band= |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2007 |Reihe=Studies in Computational Intelligence (SCI) |BandReihe=49 |ISBN=978-3-540-48582-7 |DOI=10.1007/978-3-540-48584-1}}</ref><ref>{{Literatur |Autor=Bahriye Akay, Xin Yao |Titel=Recent Advances in Evolutionary Algorithms for Job Shop Scheduling |Hrsg=A. Sima Uyar, Ender Ozcan, Neil Urquhart |Sammelwerk=Automated Scheduling and Planning |Band= |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=2013 |Reihe=Studies in Computational Intelligence (SCI) |BandReihe=505 |ISBN=978-3-642-39303-7 |DOI=10.1007/978-3-642-39304-4_8 |Seiten=191–224}}</ref> oder die [[Ameisenalgorithmus|Ameisenalgorithmen]]<ref>{{Literatur |Autor=R.F. Tavares Neto, M. Godinho Filho |Titel=Literature review regarding Ant Colony Optimization applied to scheduling problems: Guidelines for implementation and directions for future research |Sammelwerk=Engineering Applications of Artificial Intelligence |Band=26 |Nummer=1 |Datum=2013-01 |ISSN=0952-1976 |DOI=10.1016/j.engappai.2012.03.011 |Seiten=150–161 |Online=https://www.researchgate.net/publication/257392389_Literature_review_regarding_Ant_Colony_Optimization_applied_to_scheduling_problems_Guidelines_for_implementation_and_directions_for_future_research |Abruf=2024-12-31}}</ref>.

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|mini|500px|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 [[Betriebssystem]]en. Er ist für die faire [[Verwaltung]] von mehreren [[Prozess (Informatik)|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 [[Scheduler (Datenbank)|Transaktionsscheduler]] die Schreib- und Lesezugriffe der einzelnen Transaktionen auf die Daten, um Verstöße gegen das [[ACID|ACID-Prinzip]] zur Einhaltung der Datenkonsistenz zu vermeiden.
* Beim [[Job-Scheduler|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.

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4122751-7}}

[[Kategorie:Betriebswirtschaftslehre]]
[[Kategorie:Betriebssystemtheorie]]
[[Kategorie:Planung und Organisation]]
[[Kategorie:Parallelverarbeitung]]
[[Kategorie:Maschinenbelegungsplanung]]

Scheduling - Versionsgeschichte

imported>PerfektesChaos: tk k