Job-Shop-Planung (GA)
Optimierung der Job-Shop-Planung mit Genetischem Algorithmus. Löst Job-Shop-Planungsprobleme, bei denen jeder Auftrag eine Reihe von Operationen auf…
Löst Job-Shop-Planungsprobleme, bei denen jeder Auftrag eine Reihe von Operationen auf verschiedenen Maschinen hat. Verwendet Genetischen Algorithmus (POX-Kreuzung, Swap-Mutation) zur Minimierung von Makespan und Verspätung.
Was ist Job-Shop-Planung und wie loest ein GA sie?
Job-Shop-Planung weist Operationen von Auftraegen Maschinen zu, um Makespan oder Verspaetung zu minimieren. Jeder Auftrag besteht aus einer geordneten Folge von Operationen auf verschiedenen Maschinen.
JSSP ist NP-schwer. Ein GA entwickelt eine Population von Kandidatenplaenen. POX-Kreuzung bewahrt die Auftragsreihenfolge; Swap-Mutation tauscht Operationspositionen.
JSSP ist kritisch in der Fertigung. 10-15% Makespan-Reduktion steigert den Durchsatz direkt ohne Kapitalinvestition.
Formula: Makespan = max(Fertigstellungszeiten aller Operationen) Verspätung = Σ max(0, Fertigstellung_j − Fälligkeit_j) GA: Initialisierung → Bewertung → Selektion → POX → Mutation → Iteration
Berechnungsbeispiel
3 Auftraege, 3 Maschinen. Auftrag 1: M1(3)→M2(2)→M3(4). Optimaler Makespan = 12. GA (Population 100, 200 Generationen) findet typisch dieses Optimum oder 5% darüber.
Wann Sie diesen Rechner verwenden sollten
- Ein Produktionsplaner plant mehrere Aufträge in einer Werkstatt mit gemeinsamen Maschinen zur Minimierung der Durchlaufzeit
- Ein Fertigungsingenieur bewertet den Einfluss einer neuen Maschine auf den Gesamtdurchsatz
- Ein Scheduler in einer Druckerei oder Halbleiterfab bestimmt Auftragsprioritäten für minimale Verspätung
- Ein Operations Researcher benchmarkt GA-basiertes Scheduling gegen aktuelle manuelle Methoden
Häufige Fehler, die vermieden werden sollten
- Populationsgröße für komplexe Probleme zu klein — bei 10+ Aufträgen und 5+ Maschinen mindestens 100-200 Individuen verwenden
- Zu wenige Generationen laufen lassen — beobachten Sie ob die Fitness sich noch verbessert
- Freigabezeiten und Liefertermine ignorieren, wenn vorhanden — ohne diese optimiert GA nur Makespan
- GA nicht mehrfach mit verschiedenen Random Seeds laufen lassen — GA ist stochastisch; 3-5 Läufe und bestes Ergebnis nehmen
Wie die Ergebnisse zu interpretieren sind
- Ist die Gesamtverspätung null, werden alle Aufträge vor dem Liefertermin fertig — der Plan ist machbar
- Liegt der Makespan nahe der Summe der Bearbeitungszeiten auf der Engpassmaschine, ist der Plan nahezu optimal
- Das Gantt-Chart zeigt Leerlaufzeiten auf Maschinen: große Lücken deuten auf Planungsineffizienz hin
Verwandte Standards & Referenzen
- Garey, Johnson & Sethi (1976) — wiesen die NP-Schwere der Makespan-Minimierung im Job-Shop nach
- Makespan (C_max) und Gesamtverspätung — die standardmäßigen Zielfunktionen in der Produktionsplanung
- Genetische Algorithmen (Holland, 1975) — die hier angewandte Metaheuristik-Klasse zur Durchsuchung des Lösungsraums der Ablaufpläne
Häufig gestellte Fragen
Wie stelle ich GA-Parameter fuer gute Ergebnisse ein?
Population 50-200, Mutationsrate 0,05-0,15, 200-500 Generationen. Fuer 10+ Auftraege: Population ≥100, Generationen ≥300.
Unterschied zwischen Makespan- und Verspaetungsoptimierung?
Makespan-Minimierung fokussiert auf schnellstmoegliche Fertigstellung aller Auftraege. Verspaetungsminimierung priorisiert Termineinhaeltung. Multikriterie-Optimierung kann beide balancieren.