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).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
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).
Welcher Job läuft wann auf welcher Maschine? Klausurpflicht in 4/5 Produktions-Modulen. Operative Feinplanung der Produktion.
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.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Welcher Job läuft wann auf welcher Maschine? Klausurpflicht in 4/5 Produktions-Modulen. Operative Feinplanung der Produktion.
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.
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.
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 |
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).
J || C_(max))NP-schwer für > 2 Maschinen. Standard für reale Werkstätten. Heuristiken: Shifting Bottleneck, Tabu-Search, Genetische Algorithmen.
| 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 |
Setup: n Jobs müssen erst auf M1 dann M2 laufen. Bearbeitungszeiten p_{i,1} und p_{i,2}.
Algorithmus:
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.
Standard-Visualisierung:
Schreiben: Henry Gantt (1910er, für US-Marine im 1. Weltkrieg).
F_j = C_j - r_j (Bereitstellung)L_j = C_j - d_j (kann negativ sein — zu früh fertig)T_j = max(0, L_j) (nur positiv)Lean-Production-Konzepte (eigenes Topic 22.9):
❌ "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.
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.
6 Aufgaben zu Scheduling-Regeln + Johnson + Gantt-Chart.
Klausurfragen mit Lösungen (6)
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.
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.
Zuordnungen:
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
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.
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
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.
6 Klausur-Fragen mit Johnson + α|β|γ + NP-Komplexität.
Klausurfragen mit Lösungen (6)
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.
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.
Lösungen pro Lücke:
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
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.
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
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.