Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Welcher Job läuft wann auf welcher Maschine? Klausurpflicht in 4/5 Produktions-Modulen. Operative Feinplanung der Produktion.
Die Idee in einem Satz
Scheduling weist Jobs den Maschinen zeitlich zu, um Ziele wie Makespan, Durchlaufzeit oder Verzug zu optimieren, mit Heuristiken wie SPT, EDD oder optimalen Algorithmen wie Johnson.
Klassifikation (α | β | γ-Notation)
Standard-Notation (Graham 1979):
| α (Maschinen) | β (Restriktionen) | γ (Ziel) |
|---|---|---|
| 1 (Einmaschine) | pmtn (Unterbrechung) | Cmax (Makespan) |
| P (Parallel-Identisch) | prec (Reihenfolge) | ΣC_j (Σ Fertigstellung) |
| F (Flow-Shop) | r_j (Bereitstellung) | L_max (max. Verspätung) |
| J (Job-Shop) | d_j (Fälligkeit) | T_max (max. Verzug) |
| O (Open-Shop) | , | ΣT_j (Σ Verzug) |
Beispiel: J || C_(max) = Job-Shop ohne Restriktionen, Makespan minimieren.
Wichtige Scheduling-Probleme
Einmaschinen-Scheduling (1 || γ)
Ziele + Optimal-Regeln:
| Ziel | Optimal-Regel |
|---|---|
| ΣC_j minimieren | SPT (Shortest Processing Time) |
| L_max minimieren | EDD (Earliest Due Date) |
| Σw_j C_j minimieren | WSPT (Weighted SPT) |
| Σ Verzug | NP-schwer im allgemeinen |
Flow-Shop (F || C_(max))
2 Maschinen: Johnson-Algorithmus (1954) löst optimal in O(n log n). 3+ Maschinen: NP-schwer → Heuristiken (NEH, Palmer's slope).
Job-Shop (J || C_(max))
NP-schwer für > 2 Maschinen. Standard für reale Werkstätten. Heuristiken: Shifting Bottleneck, Tabu-Search, Genetische Algorithmen.
Scheduling-Regeln (Prioritätsregeln)
| Regel | Beschreibung | Best für |
|---|---|---|
| FCFS (First-Come-First-Served) | Wer zuerst da, dran | Fair, einfach |
| SPT (Shortest Processing Time) | Kürzeste Bearbeitungszeit zuerst | Ø Durchlaufzeit minimieren |
| LPT (Longest Processing Time) | Längste zuerst | Parallel-Maschinen (Load Balancing) |
| EDD (Earliest Due Date) | Frühester Liefertermin zuerst | Max. Verspätung minimieren |
| CR (Critical Ratio) | (DueDate−Now)/Bearbeitungszeit | Verzug minimieren |
| WSPT (Weighted SPT) | gewichtetes SPT | gewichtete Σ-Fertigstellung |
Johnson-Algorithmus (1954), 2-Maschinen-Flow-Shop
Setup: n Jobs müssen erst auf M1 dann M2 laufen. Bearbeitungszeiten p_{i,1} und p_{i,2}.
Algorithmus:
- Wenn min(p_{i,1}, p_{i,2}) = p_{i,1} (zuerst M1): Job an ANFANG der Liste
- Sonst (zuerst M2): Job ans ENDE der Liste
- Ausgewählten Job entfernen, wiederholen
Garantie: OPTIMAL für 2-Maschinen-Flow-Shop bzgl. Makespan.
Beispiel:
| Job | M1 | M2 |
|---|---|---|
| A | 3 | 5 |
| B | 1 | 6 |
| C | 7 | 2 |
| D | 4 | 3 |
Min-Werte: B(1,M1), C(2,M2), D(3,M2), A(3,M1). Sortiert: M1-Min vorn, M2-Min hinten. → Reihenfolge: B → A → D → C.
Gantt-Chart
Standard-Visualisierung:
- X-Achse: Zeit
- Y-Achse: Maschinen (eine Reihe pro Maschine)
- Balken: Job auf Maschine in [start, ende]
- Farbe pro Job
Schreiben: Henry Gantt (1910er, für US-Marine im 1. Weltkrieg).
Kennzahlen
- Makespan (Cmax): Zeitpunkt, an dem alle Jobs fertig sind
- Fertigstellungs-Zeit (C_j): Zeitpunkt, an dem Job j fertig ist
- Durchlaufzeit (F_j):
F_j = C_j - r_j(Bereitstellung) - Verspätung (L_j):
L_j = C_j - d_j(kann negativ sein, zu früh fertig) - Verzug (T_j):
T_j = max(0, L_j)(nur positiv) - Lateness (max L_j): schlechtester Job
- Throughput: Output pro Zeit
Lean-Scheduling
Lean-Production-Konzepte (eigenes Topic 22.9):
- Heijunka (Nivellierung): gleichmäßige Auslastung statt Schwankungen
- Pull-System (Kanban): Produktion zieht statt Push-Planung
- Takt-Zeit: verfügbare Zeit / Kunden-Nachfrage = Soll-Takt
Stolpersteine in der Praxis
- Setup-Zeiten (Rüstzeiten zwischen Jobs) komplizieren Lösung
- Maschinen-Ausfälle machen Pläne hinfällig
- Bearbeitungs-Schwankungen (Stochastik)
- Rüstkosten-Abhängigkeit (sequence-dependent setup)
- Multi-Skill-Mitarbeiter (parallele Ressourcen-Wahl)
Klausur-Faustregeln
- Notation α|β|γ beachten (Maschinen|Restriktionen|Ziel)
- 1 || ΣC_j → SPT optimal
- 1 || L_max → EDD optimal
- F2 || Cmax → Johnson-Algorithmus optimal (2-Maschinen-Flow-Shop)
- Job-Shop > 2 Maschinen → NP-schwer → Heuristiken
- Gantt-Chart zentrale Visualisierung
- Verzug ≠ Verspätung (Verzug nur positiv)
- Setup-Zeiten + Schwankungen machen Praxis komplexer als Lehrbuch
Stolpersteine
❌ "SPT minimiert immer Makespan", FALSCH. SPT minimiert Σ-Fertigstellung auf 1 Maschine. Für Makespan braucht es andere Algorithmen.
❌ "Johnson löst alle Flow-Shops", FALSCH. Nur 2 Maschinen. 3+ ist NP-schwer.
❌ "EDD minimiert Σ Verzug", FALSCH. EDD minimiert max. Verzug (L_max), nicht die Summe.
❌ "Job-Shop = Flow-Shop", FALSCH. Flow-Shop hat fixe Reihenfolge der Maschinen, Job-Shop nicht.
❌ "Heuristik = falsch", FALSCH. Heuristiken liefern oft 90%+-optimal in akzeptabler Zeit. Bei NP-schwer kein Standard-Algorithmus.
Quellen
- Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G. "Optimization and Approximation in Deterministic Sequencing and Scheduling", Annals of Discrete Mathematics 1979. α|β|γ-Notation.
- Johnson, S. M. "Optimal Two- and Three-Stage Production Schedules with Setup Times Included", Naval Research Logistics 1954. Johnson-Algorithmus.
- Pinedo, M. Scheduling: Theory, Algorithms, and Systems, 6. Aufl., Springer 2022. Standard-Lehrbuch.
- Brucker, P. Scheduling Algorithms, 5. Aufl., Springer 2007.
- Günther, H.-O.; Tempelmeier, H. Produktion und Logistik, 9. Aufl., Springer 2012. Kap. 11 Ablaufplanung.
- Thonemann, U. Operations Management, 3. Aufl., Pearson 2015. Kap. 8 Scheduling.
Interaktiv verstehen
Ablaufplanung, Gantt-Visualizer
Job-Shop mit 4 Jobs (J1-J4) und 3 Maschinen. Jeder Job hat einen Arbeitsplan (Maschinen-Reihenfolge + Dauern + Liefertermin). Toggle zwischen FCFS (First-Come-First-Served) und SPT (Shortest Processing Time). Gantt-Chart zeigt Schedule pro Maschine mit Makespan + Verzugs-Anzeige.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei Scheduling-Aufgaben IMMER 1) α|β|γ-Notation, 2) passende Regel wählen (SPT/EDD/Johnson je nach Ziel), 3) Gantt-Chart zeichnen, 4) Cmax + Verzug berechnen. Johnson nur für 2-Maschinen-Flow-Shop.
Praxis-Übung
Ablaufplanung, Praxis-Übung
6 Aufgaben zu Scheduling-Regeln + Johnson + Gantt-Chart.
Klausurfragen mit Lösungen (6)
- F1.Was bedeutet 'Makespan' (Cmax) in der Ablaufplanung?
Antwort: Zeitpunkt, an dem ALLE Jobs fertig sind (Gesamtdauer des Schedules)
Erklärung: Makespan = Cmax = max(C_j) = Zeitpunkt der LETZTEN Fertigstellung. Misst die Gesamtdauer eines Schedules. Bei Auslieferung an Endkunden oft die wichtigste Größe. Klausur-Pflicht-Kennzahl.
- F2.Welche Scheduling-Regel minimiert die durchschnittliche Fertigstellung (Σ C_j) auf 1 Maschine optimal?
Antwort: SPT (Shortest Processing Time)
Erklärung: SPT (Shortest Processing Time First): kürzeste Jobs zuerst. BEWEISBAR OPTIMAL für 1 || Σ C_j (Smith 1956). Intuition: kurze Jobs schnell wegnehmen reduziert deren Wartezeit + alle nachfolgenden warten kürzer. Klausur-Standard-Theorem.
- F3.Ordne Ziel der optimalen Regel zu.
Zuordnungen:
- Σ C_j (Σ Fertigstellung) auf 1 Maschine → SPT (Shortest Processing Time)
- L_max (maximale Verspätung) auf 1 Maschine → EDD (Earliest Due Date)
- Cmax (Makespan) bei 2-Maschinen-Flow-Shop → Johnson-Algorithmus (1954)
- Σ w_j C_j (gewichtete Fertigstellung) → WSPT (Weighted SPT)
Erklärung: Optimal-Regeln zu Standard-Zielen. SPT/EDD/Johnson/WSPT sind beweisbar optimal für ihr jeweiliges Setting. Job-Shop > 2 Maschinen ist NP-schwer → Heuristiken. Klausur-Pflicht-Tabelle.
Typ: Zuordnung
- F4.Was unterscheidet einen JOB-SHOP von einem FLOW-SHOP?
Antwort: Flow-Shop: alle Jobs durchlaufen Maschinen in FIXER Reihenfolge. Job-Shop: jeder Job hat individuelle Maschinen-Reihenfolge
Erklärung: Flow-Shop: gleicher Maschinen-Weg für alle Jobs (z.B. M1→M2→M3). Job-Shop: jeder Job hat eigenen Maschinen-Plan (z.B. Job A: M2→M1→M3, Job B: M3→M2→M1). Job-Shop ist die allgemeinere Variante + entspricht eher klassischen Werkstätten. Klausur-Pflicht-Unterscheidung.
- F5.Der Johnson-Algorithmus (1954) löst das 2-Maschinen-Flow-Shop-Problem optimal bzgl. Makespan in O(n log n).
Antwort: Wahr
Erklärung: RICHTIG. Johnson 1954 (Naval Research Logistics): elegantes O(n log n)-Verfahren. 1) Jobs mit min auf M1: an Anfang der Liste. 2) Jobs mit min auf M2: ans Ende. Liefert OPTIMALE Makespan für F2 || Cmax. Für 3+ Maschinen wird das Problem NP-schwer und braucht Heuristiken (NEH, Palmer's slope). Klausur-Klassiker.
Typ: Wahr/Falsch
- F6.Wofür wird die α | β | γ-Notation (Graham 1979) verwendet?
Antwort: Klassifikation von Scheduling-Problemen (α = Maschinen-Setup, β = Restriktionen, γ = Optimierungs-Ziel)
Erklärung: Graham/Lawler/Lenstra/Rinnooy Kan 1979 (Annals of Discrete Mathematics): Notation für Scheduling-Probleme. α (Maschinen-Typ: 1/P/F/J/O), β (Restriktionen: pmtn/prec/r_j/d_j), γ (Ziel: Cmax/ΣC_j/L_max/ΣT_j). Beispiel: J || Cmax = Job-Shop ohne Restriktionen, Makespan minimieren. Standard-Notation in der Scheduling-Literatur. Klausur-Pflicht-Wissen.
Klausur-Quiz
Ablaufplanung, Klausur-Quiz
6 Klausur-Fragen mit Johnson + α|β|γ + NP-Komplexität.
Klausurfragen mit Lösungen (6)
- F1.Wer hat das Gantt-Chart erfunden, und in welchem Kontext?
Antwort: Henry Gantt, 1910er für die US-Marine im 1. Weltkrieg
Erklärung: Henry Gantt (1861-1919): Schüler von F.W. Taylor, entwickelte die Balken-Diagramm-Visualisierung in den 1910er-Jahren. Erste großflächige Anwendung: US-Marine im 1. Weltkrieg zur Schiffsbau-Planung. Bis heute Standard-Visualisierung in Projektmanagement + Operations. Klausur-Anekdoten-Wissen.
- F2.Was ist der Unterschied zwischen 'Verspätung' (L_j) und 'Verzug' (T_j)?
Antwort: Verspätung L_j = C_j − d_j (kann negativ sein = zu früh fertig). Verzug T_j = max(0, L_j) (nur positiv)
Erklärung: Wichtige Unterscheidung: Verspätung (Lateness) L_j = C_j − d_j kann NEGATIV sein (= früher fertig). Verzug (Tardiness) T_j = max(0, L_j) ist NUR positiv (zu früh fertig ist kein Verzug). Klausur-Stolperstein: oft synonym verwendet, aber technisch unterschiedlich. ΣT_j-Minimierung ist NP-schwer, L_max ist mit EDD optimal lösbar.
- F3.Vervollständige die α|β|γ-Notation: F2 || Cmax bedeutet {{1}}-Maschinen-Flow-Shop ohne Restriktionen, Ziel: {{2}} minimieren.
Lösungen pro Lücke:
- {{1}}: 2 / zwei
- {{2}}: Makespan / Cmax / Gesamtdauer
Erklärung: α = F2 → 2-Maschinen-Flow-Shop. β = || (leer = keine Restriktionen). γ = Cmax → Makespan minimieren. Dieses Problem ist mit Johnson-Algorithmus optimal lösbar in O(n log n). Klausur-Pflicht-Notation.
Typ: Lückentext
- F4.Gegeben Jobs A(M1=3, M2=5), B(M1=1, M2=6), C(M1=7, M2=2), D(M1=4, M2=3): Was ist die optimale Johnson-Reihenfolge?
Antwort: B → A → D → C
Erklärung: Johnson-Algorithmus: 1) Job B hat min=1 auf M1 → an Anfang. 2) Job C hat min=2 auf M2 → ans Ende. 3) Job D hat min=3 auf M2 → vor C. 4) Job A hat min=3 auf M1 → nach B. Ergebnis: B → A → D → C. Klausur-Standard-Rechentyp.
- F5.Das Job-Shop-Scheduling-Problem mit mehr als 2 Maschinen ist NP-schwer, es gibt keinen Polynomial-Zeit-Algorithmus für die optimale Lösung.
Antwort: Wahr
Erklärung: RICHTIG. J3 || Cmax ist bereits NP-schwer (Garey/Johnson/Sethi 1976). Daher praktischer Einsatz von Heuristiken: Shifting Bottleneck (Adams/Balas/Zawack 1988), Tabu-Search, Genetische Algorithmen, Simulated Annealing. OR-Tools (Google CP-SAT-Solver) lösen kleinere Instanzen praktisch optimal. Klausur-Komplexitäts-Wissen.
Typ: Wahr/Falsch
- F6.Welche Eigenschaft hat die SPT-Regel hinsichtlich SCHWANKUNGEN in den Bearbeitungszeiten?
Antwort: Anfällig: bei stochastischen Bearbeitungszeiten ist nur die ERWARTUNGSWERT-SPT-Regel optimal, und auch dann nur in Erwartung
Erklärung: Bei stochastischen Bearbeitungszeiten: SPT mit Erwartungswerten ist optimal in Erwartung (Σ E[C_j] minimieren). Aber: einzelne Realisationen können stark abweichen. In Praxis kombiniert man mit Sicherheitspuffern. Stochastisches Scheduling ist eigenes Forschungsgebiet (Pinedo Kap. 9-12). Klausur-Detail aus fortgeschrittenen Modulen.
