Upload
nguyenhanh
View
214
Download
0
Embed Size (px)
Citation preview
Fakultät Informatik, Institut für Angewandte Informatik, Professur Modellierung und Simulation
Dresden, 04.07.2012
Ressourceneinsatzplanung in der Fertigung
Dr. Christoph LaroqueSommersemester 2012
Ressourcenmanagement Folie Nr. 2
Ausblick: Ab jetzt dann Planungsmodelle
In den kommenden Wochen wollen wir uns nun mit konkreten Planungsproblemen und zugehörigen Planungsmodellen auseinandersetzen…
Zur Einstimmung:Eine gute Übersicht findet sich bei dem ‚Guru‘ der mathematischen Planungsmodelle für die Produktion – Prof. Tempelmeier
http://www.produktion-und-logistik.de/index.html
04.07.2012
Ressourcenmanagement Folie Nr. 3
LÖSUNGSVERFAHREN
Ressourceneinsatzplanung in der FertigungSommersemester 2012
04.07.2012
Ressourcenmanagement Folie Nr. 4
Auf das richtige Werkzeug kommt es an…
Realistische Planungsmodelle werden sehr schnell sehr groß.Wir erinnern uns:
„Wir haben 50 Fertigungsaufträge, die an einem Tag über eine Maschine laufen sollen. Je nach Rüstzustand und Reihenfolge ergibt sich eine unterschiedliche Gesamtdurchlaufzeit.“
Vollständige Enumeration ergibt (50!)1 Möglichkeiten, also exakt 3,0414093201713378043612608166065e+64
Oder 3,01 * 1064
04.07.2012
Ressourcenmanagement Folie Nr. 5
Auf das richtige Werkzeug kommt es an…
Lösungsverfahren müssen also entweder genau UND schnell oder schneller und zielgerichtet zufällig sein.
Gängige Lösungsverfahren:• Lineare Optimierung (exakt)• MIP (exakt)• Netzwerkoptimierung (exakt)• Heuristiken und Metaheuristiken (schneller)• Simulation (schneller)• …weitere Verfahren des OperationsResearch (OR)
04.07.2012
Ressourcenmanagement Folie Nr. 6
Lineare Optimierung: Simplex Algorithmus
Grundverfahren der Linearen Optimierung.
Es löst ein Problem nach endlich vielen Schritten exakt oder stellt dessen Unlösbarkeit oder Unbeschränktheit fest.
Wem Simplex NIX sagt:Bitte bis kommende Woche noch mal klar machen…
04.07.2012
Ressourcenmanagement Folie Nr. 7
Alle Verfahren gibt es in allen Teilgebieten…
Die genannten Lösungsverfahren können in unseren einzelnen Teilgebieten eingesetzt werden, im Einzelnen
• Materialbedarfsplanung • Losgrößenplanung• Terminplanung• Kapazitätsplanung• Reihenfolgeplanung• …. Und viele, viele teilintegrierte Modelle
04.07.2012
Ressourcenmanagement Folie Nr. 8
Reihenfolgeplanung - Basics
Aufgabe der Reihenfolgeplanung ist die Zuordnung von N Aufträgen auf M Maschinen, auf denen sie unter Einhaltung bestimmter Restriktionen, wie der technologisch bedingten Reihenfolge, bearbeitet werden müssen. Die Zuordnung soll bezogen auf ein spezifisches Ziel optimal sein.
Ausgangsdaten:• Anzahl und Art der Maschinen• Anzahl der Fertigungsaufträge (Lose)• Fertigstellungstermin• Bearbeitungszeiten (Auftragszeiten)
04.07.2012
Ressourcenmanagement Folie Nr. 9
Reihenfolgeplanung - Basics
Aus den vorhandenen Daten ergeben sich
1. Bearbeitungszeitenmatrix2. Maschinenfolgegraph / Maschinenfolgematrix
Reihenfolgeplanungsprobleme können nach 4 Kriterien klassifiziert werden: N / M / O / Z Problem, mitN: Anzahl AufträgeM: Anzahl MaschinenO: Organisationstyp Fertigung (Flow Shop vs. Job Shop)Z: Zielfunktion
04.07.2012
Ressourcenmanagement Folie Nr. 10
Reihenfolgeplanung – Prämissen N/M/O/Z
N – Auftragsbezogene Prämissen• Auftragsbestand ist vorgegeben und konstant• Bearbeitungszeiten sind bekannt, Rüstzeiten bereits enthalten• Transportzeiten werden vernachlässigt
M - Maschinenbezogene Prämissen• Anzahl M der Maschinen ist bekannt, Maschinen fallen nicht aus• Bearbeitung eines Auftrags erfolgt ohne Unterbrechnung• Auftragssplitting ist nicht erlaubt• Eine Maschine kann nur 1 Auftrag bearbeiten
04.07.2012
Ressourcenmanagement Folie Nr. 11
Reihenfolgeplanung – Prämissen N/M/O/Z
O – Bearbeitungsablauf Prämissen• Reihenfertigung (Flow Shop): Jeder Auftrag hat dieselbe
Maschinenfolge• Werkstattfertigung (Job Shop): Die Aufträge durchlaufen die
Maschinen in unterschiedlicher Reihenfolge
Z - Zielfunktionen• Minimierung der Gesamtdurchlaufzeit• Minimierung der maximalen Durchlaufzeit (Zykluszeit)• Minimierung der gesamten Terminüberschreitungszeit• Minimierung der ablaufbedingten Gesamtleerzeit der Maschinen
(Maximierung der Kapazitätsauslastung)
04.07.2012
Ressourcenmanagement Folie Nr. 12
Doch man kann nicht alles haben…
Klassisches Dilemma der Ablaufplanung
„Die Optimierungsziele der Ablaufplanung beziehen sich nur auf die vorliegenden Aufträge oder nur auf die vorhandenen Maschinen. Sie widersprechen sich im allgemeinen. Das eigentliche Dilemma besteht
darin, die Durchlaufzeit der Aufträge zu minimieren und gleichzeitig die Kapazitätsauslastung der Maschinen zu maximieren.
Soll die Durchlaufzeit der Aufträge minimiert werden, so müssen die Maschinen, während sie auf die Bearbeitung der Aufträge warten, leer
stehen. Soll die Auslastung der Maschinen maximiert werden, so müssen die Aufträge vor den Maschinen auf ihre Bearbeitung warten,
so dass sich die Durchlaufzeit der Aufträge verlängert.“
04.07.2012
Ressourcenmanagement Folie Nr. 13
Reihenfolgeplanung – Ergebnisdarstellung
Die Darstellung der Ergebnisse einer Reihenfolgeplanung werden üblicherweise über Graphen dargestellt:
• Auftragsfolgegraph• Auftragsfolgematrix• Ablaufgraph • Gantt-Diagramm
04.07.2012
Ressourcenmanagement Folie Nr. 14
Reihenfolgeplanung – N / 1 / - / D
N Aufträge auf 1 Maschine zur Minimierung der Gesamtdurchlaufzeit D (makespan):
Verfahren:Anwendung der SPT-Regel (KOZ-Regel)„Die Aufträge sind in der Reihenfolge nicht abnehmender Bearbeitungszeiten zu ordnen.
Vorteil:Funktioniert auch bei mehreren Maschinen (Teilmodelle je Maschine) - Gesamtergebnis dann aber meist suboptimal.
04.07.2012
Ressourcenmanagement Folie Nr. 15
Reihenfolgeplanung – N / 1 / - / D
…Gesamtergebnis dann aber meist suboptimal..
(1) Überlegt kurz: Warum ist die mehrstufige Lösung dann zumeist suboptimal?
(2) Was könnte ich tun, um die richtige Prioritätsregel auszuwählen?
(3) Was kann ich tun, um die Bedeutung der Feinplanung und Auswahl der Prio-Regel zu reduzieren?
04.07.2012
Ressourcenmanagement Folie Nr. 16
Reihenfolgeplanung – N / 2 / R / Dmax
N Aufträge auf 2 Maschinen (FlowShop A - B) zur Minimierung der maximalen Durchlaufzeit Dmax:
Verfahren:Algorithmus von Johnson (1954), Reihenfolge für A und B gleich.
1. Bestimme Auftrag mit der kürzesten Bearbeitungszeit auf irgendeiner Maschine
2. Wenn Bearbeitungszeit auf Maschine A, dann 1. Setze Auftrag an die erste, freie Position der
Auftragsreihenfolge,2. Sonst setze Auftrag an die letzte freie Position der
Auftragsreihenfolge3. Streiche den Auftrag und gehe zu (1).
04.07.2012
Ressourcenmanagement Folie Nr. 17
Reihenfolgeplanung – N / 2 / R / Dmax
N Aufträge auf 2 Maschinen (FlowShop A - B) zur Minimierung der maximalen Durchlaufzeit Dmax:
2. Verfahren:NEH-Heuristik, Reihenfolge für Maschinen gleich. Funktioniert für mehrere Verkettungen.
1. Bestimme für jeden Auftrag die Summe der Bearbeitungszeiten an allen Maschinen und sortiere Aufträge absteigend.
2. Nimm die ersten beiden Aufträge und Bestimme Zykluszeit für alle Möglichkeiten. Fixiere Reihenfolge mit minimalem makespan.
3. Nimm den nächsten Auftrag und füge ihn der Reihe nach an jeder möglichen Position ein. Bestimme makespan. Fixiere minimalen makespan.
4. Wenn alle Aufträge bearbeitet, stoppe, ansonsten gehe zu 3.
04.07.2012
Ressourcenmanagement Folie Nr. 18
Reihenfolgeplanung – N / 2 / W / Dmax
N Aufträge auf 2 Maschinen (JobShop A - B) zur Minimierung der maximalen Durchlaufzeit Dmax:
Verfahren:Algorithmus von Jackson (1963) für JobShop Problem.
1. Bestimme Auftragsmengen (A, B, AB, BA)2. Ordne Teilmengen AB und BA nach Johnson.3. Bilde als Auftragsfolgen auf
1. Maschine A: Reihenfolge AB, A, BA2. Maschine B: Reihenfolge BA, B, AB
04.07.2012
Ressourcenmanagement Folie Nr. 19
Reihenfolgeplanung – komplexere Reihenfolgen
Exakte Verfahren für komplexere Reihenfolgeprobleme liefern nur unter sehr restriktiven Bedingungen optimale Lösungen. In der Praxis finden wir daher zumeist den Einsatz von heuristischen Prioritätsregelverfahren.
Auswahl an Prioritätsregeln (Wdh):• Kürzeste / Längste Operationszeit• Kürzeste / Größte Restbearbeitungszeit• Schlupfzeit• FCFS• Wertregel• Lieferterminregel• …
04.07.2012
Ressourcenmanagement Folie Nr. 20
FRAGEN?
Ressourceneinsatzplanung in der FertigungSommersemester 2012
04.07.2012