Werkstattfertigungsplanung
- Eingeführt von
- Pinedo, M. L.
- Jahr
- 2016
- Typ
- Combinatorial scheduling problem
- Familie
- Optimization
Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen
Was leistet sie?
Die Werkstattfertigungsplanung (Job Shop Scheduling) ist das Problem, eine Menge von Aufträgen (Aufgaben) einer Menge von Maschinen (Ressourcen) über die Zeit zuzuordnen, unter Berücksichtigung von Vorrang- und Kapazitätsbeschränkungen, mit dem Ziel, Leistungsmetriken wie die Durchlaufzeit (Gesamtfertigstellungszeit), Verspätung oder Kosten zu optimieren.
Das Werkstattfertigungsproblem ist ein klassisches kombinatorisches Optimierungsproblem in der Operations Research, das durch Heuristiken (gierige Dispositionsregeln, simulierte Abkühlung, genetische Algorithmen) und exakte Algorithmen (Branch-and-Bound, Constraint Programming) gelöst wird. Es ist grundlegend für die Fertigung, das Projektmanagement und die rechnergestützte Zeitplanung.
Die Intuition hinter der Methode
Stellen Sie sich eine kleine Maschinenwerkstatt mit 10 Maschinen vor. Ein Kundenauftrag (Job) besteht aus 5 Teilen, von denen jedes eine Abfolge von Operationen an verschiedenen Maschinen erfordert: Teil 1 benötigt Bearbeitung an Maschine A, dann Bohren an Maschine C. Teil 2 benötigt Bohren an Maschine B, dann Schweißen an Maschine D. Alle Teile laufen zur Endmontage zusammen. Die Herausforderung: Planen Sie alle Operationen so, dass die Gesamtfertigstellungszeit minimiert wird, ohne die Maschinenkapazität zu überschreiten, und unter Einhaltung der Operationsreihenfolge für jedes Teil. Wenn Sie Teil 1 zu spät Maschine A zuweisen, steht Maschine C untätig. Wenn Sie Maschine C überlasten, staut sich alles. Das Werkstattfertigungsproblem erfasst diese Komplexität: Bei 100 Aufträgen und 20 Maschinen ist die Anzahl der möglichen Zeitpläne astronomisch, was eine exakte Lösung unpraktisch macht. Stattdessen verwenden Sie Heuristiken, um schnell einen guten (nicht unbedingt optimalen) Zeitplan zu finden.
Geschichte
Das Problem der Werkstattfertigungsplanung entstand in den 1950er Jahren als Forschungsproblem in der Operations Research. Die wegweisende Arbeit von Johnson (1954) löste das Zwei-Maschinen-Problem optimal; Fisher und Thompson (1963) schufen Benchmark-Probleme, die heute noch verwendet werden. Das Problem ist NP-schwer (in den 1970er Jahren bewiesen), was die Entwicklung von Heuristiken und Metaheuristiken vorantrieb. Moderne Ansätze umfassen Constraint Programming (1990er–2000er Jahre), genetische Algorithmen und hybride Methoden. Die Werkstattfertigungsplanung ist heute ein ausgereiftes Feld mit Anwendungen, die über die Fertigung hinaus auf Cloud Computing, Telekommunikation und Transportwesen ausgedehnt werden.
Wann wird sie eingesetzt?
Die Werkstattfertigungsplanung (Job Shop Scheduling) findet Anwendung in jeder Fertigungs- oder Dienstleistungsumgebung mit mehreren Maschinen/Ressourcen und Aufträgen mit unterschiedlichen Operationssequenzen. Typische Anwendungen sind Maschinenwerkstätten, Druckereien, Halbleiter-Wafer-Fertigung, Krankenhäuser (Operationssaalplanung) und Projektplanung. Setzen Sie es ein, wenn die Auftragskomplexität hoch ist (mehrere Operationen pro Auftrag), die Maschinenauslastung kritisch ist oder die Fälligkeitstermine eng sind. Weniger kritisch in Fließbandumgebungen (linearer Fluss) oder einfachen Einzelmaschinenoperationen.
Grenzen und Hinweise
- Kombinatorische Komplexität: Das Finden optimaler Lösungen ist NP-schwer; praktische Lösungen erfordern Heuristiken, die möglicherweise nicht global optimal sind
- Heuristische Lösungen sind kontextabhängig; eine Regel, die in einer Werkstatt gut funktioniert, kann in einer anderen schlecht abschneiden und erfordert Abstimmung und Validierung
- Geht von statischen Eingaben aus (feste Aufträge und Maschinen); reale Werkstätten erleben dynamische Ankünfte, Stornierungen und Geräteausfälle, was häufige Umplanungen erfordert
- Planungsstabilität: Häufige Änderungen an Zeitplänen (aufgrund neuer Aufträge oder Störungen) können Kosten erhöhen und die Koordination mit Mitarbeitern und Kunden erschweren
Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.
Stärken
- Berücksichtigt komplexe, realistische Beschränkungen (Vorrang, Maschinenfähigkeiten, Fälligkeitstermine), die einfache Planungsregeln nicht bewältigen können
- Optimiert für relevante Geschäftsmetriken (Durchlaufzeit, Verspätung, Maschinenauslastung) anstelle von Ad-hoc-Regeln
- Ermöglicht schnelle Reaktion auf Störungen; Umplanungsalgorithmen können überarbeitete Pläne erstellen, wenn eine Maschine ausfällt oder ein dringender Auftrag eingeht
- Die mathematische Formulierung ermöglicht Sensitivitätsanalysen und die Untersuchung von Kompromissen (z. B. Verspätung vs. Durchlaufzeit)
- Unterstützt durch effiziente Software-Tools und ausgereifte metaheuristische Algorithmen
Anwendungen
- Eine Präzisionsmaschinenwerkstatt nutzt die Werkstattfertigungsplanung mit simulierter Abkühlung, um über 200 kundenspezifische Teile auf 15 CNC-Maschinen zu planen, wodurch die Durchlaufzeit um 15 Prozent reduziert und die pünktliche Lieferung von 85 Prozent auf 95 Prozent verbessert wird
- Ein Halbleiterfertigungswerk wendet eine constraints-basierte Planung an, um über 500 Prozessschritte auf 50 Werkzeugen zu verwalten, wodurch die Wafer-Zykluszeit minimiert und der Bestand an unfertigen Erzeugnissen um 20 Prozent reduziert wird
- Ein Druckunternehmen verwendet dynamische Werkstattfertigungsplanung, um Druckaufträge 8 Druckmaschinen mit unterschiedlichen Fähigkeiten zuzuweisen, wobei der Auftragsmix (hohes Volumen vs. Spezialität) optimiert und die Umrüstzeit minimiert wird
- Ein Krankenhausplanungsteam implementiert Werkstattfertigungsalgorithmen für die Operationssaalplanung, koordiniert Chirurgen, Operationsteams und Ausrüstung und verbessert die OP-Auslastung von 65 Prozent auf 82 Prozent
So funktioniert es
So funktioniert es
Definieren Sie Aufträge (Bestellungen, Aufgaben) mit Operationssequenzen, Maschinenanforderungen, Bearbeitungszeiten und Fälligkeitsterminen. Definieren Sie verfügbare Maschinen und deren Verfügbarkeitsfenster.
Spezifizieren Sie Beschränkungen: Operationsvorrang (Teil 1 muss Operation A beenden, bevor Operation B beginnt), Kapazität (jede Maschine kann einen Auftrag gleichzeitig bearbeiten) und optional Freigabezeiten und Fälligkeitstermine.
Wenden Sie eine Dispositionsregel an (z. B. kürzeste Bearbeitungszeit, frühester Fälligkeitstermin, kritisches Verhältnis), um Aufträge an jeder Maschine zu sequenzieren und einen anfänglichen Zeitplan zu erstellen.
Verwenden Sie Metaheuristiken (simulierte Abkühlung, Tabu-Suche, genetische Algorithmen, Ameisenalgorithmen), um den Zeitplan durch lokale Suche oder populationsbasierte Methoden zu verbessern.
Bewerten Sie die Qualität des Zeitplans (Durchlaufzeit, Verspätung, Leerlaufzeit, Pufferzeit). Wenn akzeptabel, implementieren; andernfalls Parameter anpassen und neu optimieren.
Häufige Fallstricke
- Optimierung für die falsche Metrik; die Maximierung der Maschinenauslastung kann die Auftragsverspätung erhöhen, während die Einhaltung aller Fälligkeitstermine erhebliche Leerlaufzeiten erfordern kann
- Ignorieren von Rüstzeiten und Umstellungen; ein Zeitplan, der die Leerlaufzeit minimiert, aber häufige, zeitaufwändige Rüstvorgänge erfordert, kann in der Praxis suboptimal sein
- Übermäßiges Vertrauen in heuristische Zeitpläne ohne Validierung anhand des realen Werkstattverhaltens; Beschränkungen sind oft komplexer, als das Modell erfasst
Häufig gestellte Fragen
Was ist die Durchlaufzeit (Makespan) und warum ist sie wichtig?
Die Durchlaufzeit ist die Gesamtzeit vom Beginn der ersten Operation bis zur Fertigstellung der letzten Operation. Sie korreliert direkt mit der Anlagenauslastung, dem Cashflow (schnellere Fertigstellung = schnellere Zahlung) und der Kundenzufriedenheit. Die Minimierung der Durchlaufzeit ist ein häufiges primäres Ziel in der Werkstattfertigungsplanung.
Was ist der Unterschied zwischen statischer und dynamischer Werkstattfertigungsplanung?
Statische Planung geht davon aus, dass alle Aufträge im Voraus bekannt sind; Sie optimieren eine feste Menge. Dynamische Planung behandelt Aufträge, die im Laufe der Zeit eintreffen; Zeitpläne werden überarbeitet, wenn neue Aufträge eintreffen oder Störungen auftreten. Die meisten realen Werkstätten sind dynamisch und erfordern schnelle Re-Optimierungsalgorithmen.
Welche Dispositionsregel sollten wir verwenden?
Keine einzelne Regel dominiert. Die kürzeste Bearbeitungszeit (SPT) minimiert die Durchlaufzeit; der früheste Fälligkeitstermin (EDD) minimiert die Verspätung; das kritische Verhältnis gleicht beides aus. Testen Sie Regeln mit historischen Daten oder Simulationen, um die beste Passung für die Prioritäten und Beschränkungen Ihrer Werkstatt zu finden.
Kann die Werkstattfertigungsplanung die Fähigkeiten der Mitarbeiter und die Quervernetzung berücksichtigen?
Ja, indem das Ressourcenmodell erweitert wird: Anstatt nur „Maschine A“ anzugeben, spezifizieren Sie „Maschine A mit Mitarbeiter 1“ oder „Maschine A mit Mitarbeiter 2“. Dies erhöht jedoch die Problemkomplexität; stellen Sie sicher, dass Ihre Planungssoftware Multi-Ressourcen-Beschränkungen unterstützt.
Verwandte Methoden
Quellen
Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (5th ed.). Cham: Springer.
DOI-Referenz öffnenKopiert.Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.
DOI-Referenz öffnenKopiert.