Zusammenfassung / Abstract
Bei der Maschinenbelegungsplanung geht es darum, die auf den Maschinen zu bearbeitenden Aufträge im Hinblick auf ein vorher festgelegtes Zielwertkriterium und unter Einhaltung bestimmter Restriktionen optimal einzuplanen. Im Rahmen dieser Arbeit wird das Maschinenbelegungsproblem als Reihenfolgeproblem, welches bei der Werkstattfertigung vorliegt, verstanden.
Die Ermittlung eines optimalen Produktionsablaufs durch rein algebraische Methoden und Algorithmen erfordert schon bei einer kleinen Anzahl von Aufträgen und Maschinen einen recht hohen Rechenaufwand. Die Planung des Produktionsprozesses kann aber alternativ durch die Zuhilfenahme graphischer Methoden geschehen.
Für den besonderen Fall von insgesamt nur zwei Aufträgen werden solche Verfahren vorgestellt. Das Grundmodell von S.B. Akers stellt dabei die Ausgangs-basis dar. In einem Koordinatensystem werden kürzeste, den Produktionsablauf darstellende, Wege ermittelt. Da bei der Konstruktion nur einige wenige Regeln beachtet werden müssen, ist das Auffinden von optimalen bzw. kürzesten Wegen nicht immer garantiert. Dieser Nachteil führte zu zwei voneinander völlig verschiedenen Modifikationen des Grundmodells. Beide Verbesserungen werden ausführlich anhand eines Optimierungsproblems vorgestellt.
Eine weitere graphische Methode zur Lösung der Maschinenbelegung mit zwei Aufträgen ist durch das Diagonal-Verfahren von G. Mensch im Jahre 1968 eingeführt worden. Es handelt sich dabei primär um eine Abänderung des Koordinatensystems und der Darstellungsform.
Wenn mehr als zwei Aufträge zu bearbeiten sind, stoßen die bislang benannten Verfahren an ihre Grenzen, da eine zeichnerische Lösung in einem Koordinaten-system kaum realisierbar ist. Dennoch ist eine Lösung des Problems mit rein graphischen Verfahren möglich. Diese werden vorgestellt und bzgl. ihren generellen Anwendbarkeit untersucht.
Schlüsselwörter
Werkstattfertigung, graphische Methoden, Maschinenbelegung, Reihenfolge-problem, kombinatorische Optimierung
Inhaltsverzeichnis
Abbildungs- und Tabellenverzeichnis
Übersicht verwendeter Algorithmen
Symbolverzeichnis
1. Grundlagen zur Maschinenbelegungsplanung
2. Ausgewählte graphische Verfahren
2.1 Das Verfahren von Akers
2.2 Die Verfahrenserweiterung durch W. Szwarc
2.2.1 Das Verfahren bei einem fest vorgegebenen Produktionsablauf
2.2.2 Das Verfahren zur generellen Bestimmung von Z*
2.3 Die Verfahrensmodifikation durch Hardgrave / Nemhauser
3. Das Diagonal-Verfahren
4. Graphische Verfahren für n >
5. Abschließende Bemerkungen
Literaturverzeichnis
Eidesstattliche Erklärung
Abbildungs- und Tabellenverzeichnis
I Abbildungsübersicht
Abbildung 1: Maschinenfolgegantt für zwei Aufträge auf sieben Maschinen
Abbildung 2: Mögliche Wege für [ J7 | n=2 | Z ] nach der Methode
von Akers
Abbildung 3: Produktionsablauf für L1 = (S, A, B‘, C‘‘, D, E, J‘‘, F)
Abbildung 4: Ermittelte Wege nach der Methode von W. Szwarc
Abbildung 5: Verzweigung bei Erreichen der linken Kante
Abbildung 6: Verzweigung bei Erreichen der unteren Kante
Abbildung 7: Einfügen einer Wartezeit für A1 bei Mj
Abbildung 8: Graphische Darstellung des Produktionsablaufs III
Abbildung 9: Maschinenfolgegantt für [ J7 | n=3 | Z ]
Abbildung 10: Ablaufgantt für die Gesamtlösung G1
II Tabellenübersicht
Tabelle 1: Bearbeitungszeit von Auftrag i auf Maschine j
Tabelle 2: Maschinenfolgen der beiden Aufträge
Tabelle 3: Ermittelte Wartezeit für A1 nach Anwendung
von Algorithmus 2
Tabelle 4: Übersicht relevanter Produktionsabläufe für das Problem [ J7 | n=2 | Z ]
Tabelle 5: Optimale Programmabläufe aller Einzelprobleme
Tabelle 6: Auftragsreihenfolgen auf den einzelnen Maschinen für G1 und G2
Übersicht verwendeter Algorithmen
Algorithmus 1
Vorgehensweise zur Bestimmung von kürzesten Wegen bzw. Linien in einem Operationsfeld, wenn der Produktionsablauf gegeben ist
Algorithmus 2
Verfahrensanweisung zur Ermittlung eines Produktionsablaufs mit minimaler Zykluszeit
Algorithmus 3
Vorschrift zur Verzweigung eines Weges wenn dieser auf ein Konfliktfeld trifft.
Symbolverzeichnis
Abbildung in dieser Leseprobe nicht enthalten
Kapitel 1 Grundlagen zur Maschinenbelegungsplanung
Gegenstand der Maschinenbelegungsplanung (engl. Scheduling) ist die optimale Einplanung von Aufträgen (engl. Jobs), die auf gewissen Maschinen zu bearbeiten sind.[1] Die praktische Relevanz ist hauptsächlich im Rahmen der industriellen Fertigung gegeben. Anwendungsmöglichkeiten bestehen aber auch in anderen Bereichen wie zum Beispiel bei der Koordinierung von Flugzeugen, die auf verschiedenen Rollbahnen eines Flughafens starten oder landen, oder bei mehrstufigen Untersuchungen eines Patienten in Krankenhäusern.
Im Folgenden wird jedoch primär der Bereich der industriellen Fertigung angesprochen. Innerhalb der gesamten Produktionsplanung, die sich aus den Teilbereichen Produktionsprogrammplanung, Bereitstellungsplanung und der Produktionsprozessplanung zusammensetzt,[2] ist die Maschinenbelegungsplanung als das Kernproblem der Produktionsprozessplanung anzusehen. Dies impliziert, dass die Entscheidungen über das eigentliche Produktionsprogramm (welche Produkte in welcher Stückzahl über einen bestimmten Zeitraum hergestellt werden) und über die Bereitstellung der benötigten Produktionsfaktoren (Anzahl von Rohstoffen, Maschinen, Arbeitskräften etc.) bereits getroffen worden sind.
Bei einem Maschinenbelegungsproblem werden ganz allgemein n Aufträge Ai (i = 1,...,n) auf m Maschinen Mj (j = 1,...,m) bearbeitet. Die zentrale Fragestellung lautet nun, wann die einzelnen Aufträge auf welcher Maschine bearbeitet werden sollen, damit ein bestimmter Zielfunktionswert unter etwaigen Restriktionen sein Minimum erreicht.[3] Aufgrund verschiedener Kombinationsmöglichkeiten von Zielfunktion, Restriktionen und der Eigenschaften der einzelnen Maschinen ergibt sich eine Vielzahl unterschiedlicher Optimierungsprobleme. Allgemein handelt es sich um ein ganzzahliges, kombinatorisches Optimierungsproblem.
Zur Klassifikation des zu untersuchenden Optimierungsproblems wird in der einschlägigen Literatur zur Maschinenbelegungsplanung eine einheitliche Schreibweise, bestehend aus den Tripeln [ a | b | c ] verwendet.[4] Die abkürzenden Symbole entsprechen dabei:
a : Maschinencharakteristik
Der Parameter a = a1, a2 wird zur Beschreibung der Maschinenart- und anordnung (a1) und der Maschinenanzahl (a2) verwendet.
b : Auftragscharakteristik
Dieser Parameter beschreibt verschiedenartige Anforderungen und Eigenschaften der Aufträge. Beispielhaft seien hier Auftragszahl, Unterbrechbarkeit und Reihenfolgebeziehungen genannt. Entsprechend der gewünschten Charakteristik wird auch dieser Parameter bei Bedarf mit einem entsprechenden numerischen Index versehen.[5]
c : Zielsetzung
Die Zielsetzung wird durch eine zu minimierende Zielfunktion ausgedrückt. Eine Minimierung ist zum Beispiel für die Durchlaufzeit oder die Wartezeit eines Auftrages oder der Leerzeit einer Maschine denkbar. Das entsprechende Kriterium wird dann durch den Parameter c symbolisiert.
Insbesondere aufgrund der Konstellationen der Parameter a und b stellt sich das Maschinenbelegungsproblem entweder als Problem der Taktabstimmung oder als Reihenfolgeproblem dar. Gibt es beispielsweise nur eine einzige Maschine, die in ihrer Produktionsgeschwindigkeit variabel eingestellt werden kann, so liegt ein reines Taktabstimmungsproblem vor.
Im Folgenden werden ausschließlich Reihenfolgeprobleme behandelt. Es wird dabei stets angenommen, dass zu einem bestimmten Zeitpunkt auf einer Maschine nur ein Job und jeder Job auf höchstens einer Maschine bearbeitet wird. Des weiteren werden nur Aufträge betrachtet, deren Produktion mehrere Arbeitsgänge erfordert und bei denen jeder Arbeitsgang auf verschiedenen Maschinen bearbeitet wird. Hierbei wird sowohl die Bearbeitungszeit tij eines Arbeitsganges auf einer bestimmten Maschine, als auch die Reihenfolge µim, in welcher die einzelnen Maschinen Mj zu durchlaufen sind, als bekannt und gegeben vorausgesetzt.[6]
In Kapitel 2 wird das grundlegende graphische Verfahren von S.B. Akers für den speziellen Fall mit zwei Aufträgen vorgestellt. Ebenfalls werden einige Modifizierungen vorgestellt. Das von G. Mensch entwickelte Diagonal-Verfahren wird in Kapitel 3 behandelt. In Kapitel 4 werden Möglichkeiten der Erweiterung auf den allgemeinen Fall mit mehr als zwei Aufträgen aufgezeigt. Abschließend erfolgt in Kapitel 5 ein kurzes Resümee.
Kapitel 2 Ausgewählte graphische Verfahren
In diesem Kapitel werden einige ausgewählte graphische Verfahren zur Lösung des Reihenfolgeproblems vorgestellt. Das grundlegende Verfahren von Akers, welches im nächsten Abschnitt ausführlich beschrieben wird, gilt dabei als Basismodell. Die in den anschließenden Abschnitten vorgestellten Verfahren stellen in erster Linie Erweiterungen und Verbesserungen des ursprünglichen Modells dar. Ergänzend zu den bereits in Kapitel 1 getroffenen Annahmen besteht die Zielsetzung im Folgenden stets darin, die Zykluszeit (Z := max {Fi | i = 1,...,n} zu minimieren. Die Zykluszeit ist diejenige Zeitspanne, die vom Bearbeitungsbeginn des Auftrags i bis zur Fertigstellung aller zu bearbeitenden Aufträge vergeht. Fi kennzeichnet den Fertigstellungszeitpunkt des Auftrags i.[7] Da weiterhin angenommen wird, dass beide Aufträge im Zeitpunkt 0 beginnen, entspricht die Minimierung der Zykluszeit der Minimierung der maximalen Durchlaufzeit (Dmax := max {Di | i = 1,...,n} mit Di := Fi – ai, wobei ai den Bereitstellungs-zeitpunkt des Auftrages i beschreibt).[8] Insbesondere werden im Folgenden Werkstattfertigungsprozesse (engl. Job Shop-Problems) betrachtet. Dieses Produktionsverfahren spielt besonders im Rahmen von Einzel- und Kleinserienfertigungen eine Rolle. Die einzelnen Aufträge können hierbei in einer beliebigen, aber fest vorgegebenen, Reihenfolge auf den einzelnen Maschinen bearbeitet werden. Um eindeutige Bearbeitungszeiten tij angeben zu können, gilt zusätzlich die Annahme, dass jeder Job genau einmal auf jeder Maschine zu bearbeiten ist.
2.1 Das Verfahren von Akers
Das graphische Verfahren von Akers soll anhand eines Job Shop-Problems mit sieben Maschinen und zwei Aufträgen näher dargestellt werden. Unter Berücksichtigung der bereits getroffenen Annahmen läßt sich das Problem durch den Ausdruck [ J7 | n=2 | Z ] charakterisieren. Die gegebenen Bearbeitungszeiten und die Maschinenfolge µim eines Auftrags i werden zunächst durch Tabelle 1
und Tabelle 2 in Matrixform dargestellt.
Abbildung in dieser Leseprobe nicht enthalten
Der Maschinenfolgegantt liefert zunächst Informationen über die Dauer der Aufträge bzw. der einzelnen Arbeitsgänge eines Auftrages auf den entsprechenden Maschinen. Des weiteren ist der Fertigstellungszeitpunkt Fi eines jeden Auftrags i direkt ablesbar. Es ist jedoch unmittelbar zu erkennen, dass hier die Maschinen M2 und M7 zu einem identischen Zeitpunkt an beiden Aufträgen arbeiten. Annahmegemäß wurde diese Produktionsweise jedoch ausgeschlossen. Es ist eine Änderung der Maschinenbelegung notwendig, so dass solche Konfliktsituationen während des Produktionsablaufs nicht entstehen.[9]
Bei dem 1956 von Akers vorgestellten graphischen Verfahren werden solche Konfliktsituationen umgangen. Dazu wird zunächst ein konventionelles XY-
Koordinatensystem konstruiert. Die beiden Achsen repräsentieren hierbei den Bearbeitungsfortschritt fi der beiden Aufträgen A1 und A2. An den Achsen wird für jeden Arbeitsgang von Auftrag i die auf der Maschine j beanspruchte Zeit tij eingetragen, wobei j = µi1,...,µim gilt.[10] Ausgangspunkt ist der Koordinatenursprung S = (a1,a2) mit a1 = a2 = 0. Wird ein Auftrag i nun ohne Unterbrechung bzw. Wartezeit gefertigt, so stellt Fi := Sjtij den frühestmöglichen Zeitpunkt der Fertigstellung von Ai dar.[11] Die Punkte S und F = (F1,F2) spannen ein Rechteck, das Operationsfeld, auf. Der Punkt F stellt gleichzeitig das Ende des Produktionsprozesses dar.
In einem nächsten Schritt werden die sogenannten Konfliktfelder innerhalb des Operationsfeldes bestimmt. Für jeden Auftrag kann das Intervall [Si,Fi] in genau m disjunkte Intervalle [Yij, Wij] unterteilt werden, die entsprechend der jeweiligen Maschinenfolge µim in der Reihenfolge j = µi1,...,µim angeordnet sind. Das Symbol Yij kennzeichnet hierbei den Bearbeitungsbeginn des Auftrags bzw. Arbeitsganges i auf der Maschine j und Wij entsprechend das Bearbeitungsende. Durch [Y1j,W1j] x[Y2j,W2j] wird für jede Maschine j ein Rechteck definiert, wobei alle Punkte innerhalb dieses Rechteckes eine gleichzeitige Bearbeitung der beiden Aufträge auf der selben Maschine j implizieren.[12] Solche Konfliktfelder werden in den jeweiligen Abbildungen gesondert gekennzeichnet.
Gesucht ist nun eine durchgehende Linie, die mit der geringsten Anzahl von Schritten von Punkt S zu Punkt F durchlaufen werden kann. Ein Schritt ist hierbei jede Verbindung zwischen zwei benachbarten Punkten die ganzzahlige Koordinatenwerte aufweisen.[13] Die Linie oder der Weg darf dabei nur aus vertikalen, horizontalen und diagonalen Teilstrecken bzw. Segmenten bestehen. Die vertikalen und horizontalen Segmente werden dabei nur in positiver Richtung, d.h. von unten nach oben bzw. von links nach rechts, durchlaufen. Diagonale Strecken sind im Folgenden Strecken mit einem Winkel von 45 Grad bzw. mit einer Steigung von eins. Ein Durchlaufen von Konfliktfeldern ist ebenfalls nicht zulässig.[14] Ein horizontaler Streckenabschnitt bedeutet somit die alleinige Bearbeitung des an der Abszisse abgetragenen Auftrags und ein vertikaler Ab-schnitt symbolisiert die ausschließliche Fertigung des an der Ordinate abgetragenen Auftrags. Diagonale Abschnitte kennzeichnen eine gleichzeitige Bearbeitung
beider Aufträge. Die Zykluszeit Z ergibt sich aus der Anzahl der benötigten Schritte bzw. durch Sver + Shor + (Sdia * 2-½).
[...]
[1] Vgl. NEUMANN/MORLOCK (1993, S. 474).
[2] Vgl. SIEGEL (1974, S. 13ff).
[3] Vgl. NEUMANN/MORLOCK (1993, S. 474).
[4] Vgl. DOMSCHKE et al. (1997, S. 283).
[5] Siehe DOMSCHKE et al. (1997, S. 286ff).
[6] Vgl. DOMSCHKE et al. (1997, S. 285).
[7] Siehe DOMSCHKE et al. (1997, S. 292).
[8] Ebenda (1997, S. 294).
[9] Siehe FANDEL et al. (1996, S. 28).
[10] Vgl. AKERS (1956, S. 244).
[11] Siehe DOMSCHKE et al. (1997, S. 301).
[12] Ebenda (1997, S. 301f).
[13] Siehe FANDEL et al. (1996, S. 33f).
[14] Siehe AKERS (1956, S. 244).
-
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X.