Graphische Verfahren zur Lösung der Maschinenbelegung

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).