Klassische Scheduling-Theorie erklärt
Elf Stücke mit demselben wachsenden Beispiel: eine Maschine, keine Fristen, keine Gewichte. SPT ist dafür beweisbar optimal. Jedes Folgestück hebt GENAU EINE dieser Annahmen auf: Fristen (EDD, Moore-Hodgson), Gewichte (WSPT), beides zugleich (ATC, das erste stark NP-schwere Stück), eine zweite Maschine seriell (Johnson-Regel) oder parallel (LPT), bis Job Shop beides zusammenführt: jeder Auftrag mit eigener Maschinenreihenfolge, der Konvergenzpunkt der Linie.
Von dort zwei State-of-the-Art-Verfahren für dasselbe Job-Shop-Modell: Shifting Bottleneck konstruiert einmal gut (Engpass-Maschine zuerst), Job-Shop-Tabu-Search verbessert iterativ über eine gezielte Nachbarschaft am kritischen Pfad. Den Abschluss bildet RCPSP, der wachsende Endpunkt: Ressourcen mit Kapazität ab 1 statt nur Maschinen, ein allgemeiner Vorranggraph statt fester Ketten. Job Shop ist hier der Spezialfall Kapazität 1, per Test belegt, nicht nur behauptet.
In short: Covers classical scheduling theory: single-machine rules such as SPT and EDD, parallel machines, flow shop (Johnson's rule), job shop, shifting bottleneck, tabu search and RCPSP. Interactive demos relax one assumption at a time in a growing example.
Hintergrund zum Thema: Hafenlogistik.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Die SPT-Regel verständlich erklärt
Warum die Reihenfolge „kurze Aufträge zuerst“ bei der durchschnittlichen Fertigstellung nicht zu überbieten ist, wie ein einfacher Tauschbeweis das zeigt und wo er bei Rüstzeiten endet: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die elf Stücke im Überblick
SPT ist die Wurzel: eine Maschine, keine Fristen, keine Gewichte, beweisbar optimal durch ein Vertauschungsargument. EDD und Moore-Hodgson führen Fristen für unterschiedliche Ziele ein, WSPT führt Gewichte ein und mündet in ATC, sobald Frist UND Gewicht zugleich zählen, das erste stark NP-schwere Stück der Linie. Johnson-Regel und LPT führen je eine zweite Maschine ein, seriell beziehungsweise parallel, und laufen in Job Shop zusammen (Doppelrahmen): jeder Auftrag mit eigener Maschinenreihenfolge, Reihenfolge und serielle UND parallele Maschinen kommen hier zusammen.
Von Job Shop aus verzweigt die Linie in ein Kontrastpaar (Shifting Bottleneck konstruiert einmal gut, Job-Shop-Tabu-Search verbessert iterativ über eine gezielte Nachbarschaft, beides für dasselbe Problem) und mündet in RCPSP, den wachsenden Endpunkt: Ressourcen mit Kapazität ab 1 statt nur Maschinen mit Kapazität 1, ein allgemeiner Vorranggraph statt fester Ketten.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- Zusammenfluss mehrerer Stränge
Verwandt in anderen Linien
- Trajektorien-Metaheuristiken — Job-Shop-Tabu-Search nutzt dieselbe Grundidee wie die Tabu-Search-Demo dort (eine Tabu-Liste gegen Zyklen), aber mit einer winzigen, gezielten N5-Nachbarschaft am kritischen Pfad statt der vollen paarweisen Nachbarschaft für die Lieferroute. Gemessen konvergiert die Job-Shop-Fassung selbst von einem schwächeren Start aus bei den meisten Instanzen zum fast gleichen Ergebnis, während bei der Lieferroute ein guter Start stark zählt: derselbe Mechanismus, zwei unterschiedliche Empfindlichkeiten.
- Ordnung und Abhängigkeit — Der kritische Pfad kennt nur Abhängigkeiten, keine knappen Teams oder Maschinen: Die Kritischer-Pfad-Demo der Linie Ordnung und Abhängigkeit lässt Ressourcen bewusst weg und verweist auf die ressourcenbeschränkte Projektplanung dieser Linie.
SPT: eine Warteschlange, die sich selbst optimal sortiert
Verfolgen Sie, wie SPT die Aufträge an einer Maschine nach Bearbeitungszeit sortiert, kürzeste zuerst, und damit ohne Rüstzeiten die Summe der Fertigstellungszeiten beweisbar minimiert. Die Demo vergleicht SPT mit längster-zuerst, Zufall und einer Vollaufzählung aller Reihenfolgen. Der Haken: Mit Rüstzeiten beim Wechsel zwischen Auftragsfamilien gilt der Beweis nicht mehr, bei 60 Minuten Rüstzeit liegt SPT 28,9 % über dem echten Optimum.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →EDD: eine Warteschlange, die die schlimmste Verspätung klein hält
Verfolgen Sie, wie EDD die Aufträge nach Fälligkeit sortiert, frühester Termin zuerst, und damit ohne Schichtgrenzen die größte Verspätung beweisbar klein hält. Die Demo vergleicht EDD mit SPT, Zufall und einer Vollaufzählung, auch mit begrenzten Schichten. Der Haken: Bei 480 Minuten Schichtlänge bleibt EDD optimal, bei 350 Minuten und kürzer nicht mehr, und der Abstand schwankt von Schichtlänge zu Schichtlänge.
Demo starten →Moore-Hodgson: möglichst wenige Aufträge verspäten
Verfolgen Sie, wie Moore-Hodgson die Aufträge nach Fälligkeit einplant und bei drohender Verspätung den bisher längsten Auftrag streicht, nicht den Auslöser, um möglichst wenige Aufträge zu verspäten. Die Demo vergleicht das Verfahren mit EDD, SPT und Zufall. Der Haken: Mit Rüstzeiten zwischen Familien trägt der Beweis nicht mehr, bei 60 Minuten kommen im Mittel 2,2 verspätete Aufträge hinzu.
Demo starten →WSPT / Smith's Rule: wenn nicht jeder Auftrag gleich wichtig ist
Sehen Sie, wie WSPT die Aufträge nach dem Verhältnis von Gewicht zu Bearbeitungszeit sortiert, damit wichtige und kurze Aufträge zuerst laufen. Die Demo vergleicht WSPT mit der gewichts-blinden SPT-Regel, Zufall und einer Vollaufzählung. Der Haken: Mit Rüstzeiten gilt der Beweis nicht mehr, bei 60 Minuten liegt WSPT 30,3 % über dem Optimum, und im Einzelfall schlägt sogar SPT die Regel.
Demo starten →ATC: wenn keine einfache Regel mehr beweisbar optimal ist
Verfolgen Sie, wie die ATC-Regel zu jedem Zeitpunkt den Auftrag mit dem höchsten Prioritätswert aus Frist und Gewicht wählt, weil es für beides zugleich keine einfache, beweisbar optimale Regel mehr gibt. Die Demo vergleicht ATC mit EDD, WSPT, Zufall und dem exakten Löser CP-SAT. Der Haken: ATC trifft das Optimum nicht zuverlässig, die Trefferquote sinkt auf 20 % bei 9 Aufträgen.
Demo starten →Johnson-Regel: die erste Erweiterung auf zwei Maschinen
Sehen Sie, wie die Johnson-Regel zwei hintereinanderliegende Maschinen so beschickt, dass die Gesamtdurchlaufzeit ohne Rüstzeiten beweisbar minimal ist: erst Aufträge mit kurzer erster Operation, dann die übrigen nach absteigender zweiter Operation. Die Demo vergleicht sie mit naivem SPT und Zufall. Der Haken: Mit Rüstzeiten zwischen Familien zerbricht der Beweis, bei 60 Minuten liegt Johnson 27,4 % über dem Optimum.
Demo starten →LPT: eine bewiesene Garantie statt eines Beweises
Verfolgen Sie, wie LPT die Aufträge, längste zuerst, jeweils der am wenigsten ausgelasteten von mehreren gleichen Maschinen zuweist. Die Demo vergleicht LPT mit beliebiger und zufälliger Reihenfolge und prüft Grahams Garantie mit CP-SAT. Der Haken: Die Garantie gilt nur gegenüber dem echten Optimum, nicht gegenüber anderen Regeln, deshalb war in einem konkreten Fall eine beliebige Reihenfolge 3,7 % besser als LPT.
Demo starten →Job Shop: der Konvergenzpunkt dieser Linie
Verfolgen Sie, wie Giffler-Thompson einen Job-Shop-Zeitplan Schritt für Schritt nach einer Prioritätsregel aufbaut, wobei jeder Auftrag die Maschinen in eigener Reihenfolge durchläuft. Die Demo vergleicht die Regeln MWKR (meiste Restarbeit zuerst), SPT, FIFO und Zufall. Der Haken: SPT, an der Wurzel der Linie noch optimal, liegt hier 44 % über MWKR und sogar hinter der naiven FIFO-Regel.
Demo starten →Shifting Bottleneck: Engpässe zuerst, dann nachbessern
Sehen Sie, wie Shifting Bottleneck die Maschinen nacheinander sequenziert, die engpassträchtigste zuerst, und bereits fixierte Maschinen danach neu optimiert. Die Demo vergleicht das Verfahren mit und ohne Nachbesserung und mit der Regel MWKR. Der Haken: Im Mittel liegt MWKR nur 1,7 % über Shifting Bottleneck, und auf einzelnen Instanzen verliert das Verfahren oder die Nachbesserung sogar.
Demo starten →Job-Shop-Tabu-Search: kritischer Pfad, gezielt verbessert
Verfolgen Sie, wie Tabu Search eine Startlösung verbessert, indem es auf dem kritischen Pfad, dem Weg ohne Puffer, gezielt Operationspaare vertauscht und Rückwärtszüge kurzzeitig sperrt. Die Demo zeigt jede gefundene Verbesserung und vergleicht zwei Startlösungen. Der Haken: Der MWKR-Start liegt im Mittel 7,9 % über dem Tabu-Ergebnis, doch ein besserer Start bringt bei festem Rechenbudget kaum etwas.
Demo starten →RCPSP: der wachsende Endpunkt dieser Linie
Verfolgen Sie, wie RCPSP den Job Shop verallgemeinert: Ressourcen können mehrere Aktivitäten zugleich bedienen, und die Vorrangbeziehungen bilden ein beliebiges Netz statt einer festen Kette. Zwei Regler verändern Kapazität und Vorrangdichte. Der Haken: Mehr Kapazität hilft nur bis zu einer Grenze, die Projektdauer sinkt von 86 auf 57 und bleibt dann stehen, weil die Vorränge bremsen.
Demo starten →Welche Regel passt zu meinem Scheduling-Problem?
Ein Entscheidungsbaum über alle elf Stücke: er fragt nach der Struktur des Problems (Maschinenzahl, Fristen, Gewichte), nicht nach dem Verfahren.
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Alle elf Antworten sind durch die Messreihen der Demos belegt (siehe jede README): welche Regel beweisbar optimal ist, welche nur eine Worst-Case-Garantie hat, und welche keine Garantie mehr hat, sobald zwei Annahmen zugleich zutreffen (ATC, Job Shop und seine Nachfolger).
Weitere Linien in diesem Bereich
Exakte Suche
Bewiesen beste statt nur guter Lösungen: zwei Linien, Rucksack und Cutting Stock, von Branch & Bound bis Column Generation und Branch & Price.
Lineare Programmierung
Was steckt in einem LP-Löser? Elf Stücke vom Tableau-Simplex über Schattenpreise und Innere Punkte bis zum Crossover, alle von Grund auf geschrieben und gemessen.
Nichtlineare Optimierung
Wie findet man ein Minimum, wenn nichts linear ist? Acht Stücke vom ersten Schritt bergab über Krümmung und Nebenbedingungen bis zur Brücke ins Deep Learning, jedes mit gemessenem statt behauptetem Befund.
Populations-Metaheuristiken
Wie durchsucht eine ganze Population den Lösungsraum? Elf Verfahren von der Kreuzung über Kovarianzmatrizen bis zu Pheromonspuren, jedes mit seiner gemessenen Grenze.
Trajektorien-Metaheuristiken
Wie kommt eine einzelne Lösung über ihr erstes lokales Optimum hinaus? Zwölf Verfahren von Verschlechterungen akzeptieren bis Destroy-and-Repair, jedes mit seiner gemessenen Grenze.
Heuristische Baumsuche
Was bleibt von der Suche, wenn man das Optimum nicht abwarten kann? Acht Verfahren von der gierigen Suche bis Monte Carlo Tree Search, jedes mit seiner gemessenen Grenze.
Novelty Search und Quality-Diversity
Ein Hof-Roboter im täuschenden Labyrinth, zwölf Stücke: von der Sackgasse der Fitness über Novelty Search und MAP-Elites bis zu Go-Explore, Routing und POET.
Standortplanung
Welche Standorte eröffnen, wenn jeder Kunde zum nächsten offenen geht? Sechs Stücke von der einfachen Fixkosten-Entscheidung über Kapazität, Maximum statt Summe und Lagerbestand bis zum Wettbewerb zweier Spieler und zum Hub mit Rabatt.
Warteschlangentheorie und Simulation
Ein Terminal-Gate, dreizehn Stücke und ein Zusatzstück: jedes hebt genau eine Annahme der Formel davor auf, bis zum Netz aus Gate, Kran und Stapel und seinem Ersatzmodell.
Mittelwerte und Lagemaße
Welche Zahl steht für die Mitte der Daten, wie genau rechnet man sie, und was geschieht bei Ausreißern, Quotienten, Uhrzeiten und Standorten in der Ebene? Sieben Stücke vom Mittelwert bis zur Mitte im Raum.
Optimierung unter Unsicherheit
Eine Kapazität, die vor der unbekannten Nachfrage gewählt wird, sechs Stücke: vom Wert der Information über Stichprobe, CVaR, Robustheit und Garantie bis zur rollierenden Planung.
Bayessche Optimierung und Gauß-Prozesse
Eine teure Simulation, sieben Stücke: vom Gauß-Prozess und der erwarteten Verbesserung über Rauschen und Nebenbedingungen bis zu hohen Dimensionen, parallelen Läufen und mehreren Genauigkeiten.
Mehrkriterien-Ranking
Eine neutrale Entscheidungsmatrix, fünfzehn Stücke: von der Pareto-Dominanz über Gewichte, AHP, TOPSIS und Outranking bis zu unsicheren Gewichten, DEA, Gruppen und dem Verfahrensvergleich.
Komplexitätsklassen
Was sagt es aus, wenn ein Problem als NP-schwer gilt, und welcher Ausweg passt zu welchem Grund der Härte? Zehn Stücke über Reduktionen, typische Instanzen, große Zahlen, Garantien, Parameter, Zufall, Zählen, Spiele und lokale Optima.