Thema 9: Graphische Verfahren zur Lösung der Maschinenbelegung L. Laboch Zusammenfassung

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 Ausgangsbasis 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 Koordinatensystem 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

Thema 9: Graphische Verfahren zur Lösung der Maschinenbelegung L. Laboch Abstract

When we consider a scheduling problem, the aim is to find an optimized production process concerning various jobs which have to pass various machines. Due the process we have to pay attention to given constraints and a determined target value criterion. In this paper the production scheduling problem is understood as a sequencing problem, also called job shop-problem. The determination of an optimal production process by using algebraic methods and algorithms requires a relatively high level of computational time, even if there are only a few machines and jobs considered. To solve such problems with the aid of graphical methods can be seen as an alternative approach. Some graphical methods for the special case that only two jobs have to pass the machines are introduced in this paper. The model developed by S.B. Akers can be seen as a starting point. It is necessary to find shortests paths in a coordinate system. The production process is described by these paths. By using this procedure there are only a few rules which have to be followed, so it is not always guaranteed to find a shortest path. Because of this disadvantage two completely different modifications have been developed. Both improvements are described in detail by regarding a specifc scheduling problem.

Another graphical procedure for solving a scheduling problem with only two jobs was established in 1968 by G. Mensch and is known as „Diagonal-Verfahren“. The main differences between this model and the basic model can be seen in a different construction of the coordinate system and in a different form of presentation. The mentioned graphical methods are reaching their limits when there are more than two jobs to be done because it is nearly impossible to draw a solution of a scheduling problem with more than two jobs in one single coordinate system. But it is still possible to solve even problems consisting of more than two jobs with graphical procedures. Such procedures are introduced and their generally practicalness is analysed in this paper.

Keywords

Job shop-problem, graphical approaches, scheduling problem, sequencing problem, combinatorial optimization.

  Graphische Verfahren zur Lösung der Maschinenbelegung  I

Inhaltsverzeichnis

  Abbildungs- und Tabellenverzeichnis  II

  Übersicht verwendeter Algorithmen  III

  Symbolverzeichnis  IV

1.  Grundlagen zur Maschinenbelegungsplanung.  1

2.  Ausgewählte graphische Verfahren  3

2.1  Das Verfahren von Akers.  3

2.2  Die Verfahrenserweiterung durch W. Szwarc  8

2.2.1  Das Verfahren bei einem fest vorgegebenen Produktionsablauf  8

   9

2.2.2  Das Verfahren zur generellen Bestimmung von Z  

2.3  Die Verfahrensmodifikation durch Hardgrave / Nemhauser  12

3.  Das Diagonal-Verfahren.  14

4.  Graphische Verfahren für n 2  18

5.  Abschließende Bemerkungen.  22

  Literaturverzeichnis  23

  Graphische Verfahren zur Lösung der Maschinenbelegung  II

  Abbildungs- und Tabellenverzeichnis  

I  Abbildungsübersicht  

  Abbildung 1: Maschinenfolgegantt für zwei Aufträge auf sieben Maschinen  4

  Abbildung 2: Mögliche Wege für J7 n 2 Z nach der Methode  

  von Akers  6

  Abbildung 3: Produktionsablauf für L 1 (S, A, B , C , D, E, J , F)  7

  Abbildung 4: Ermittelte Wege nach der Methode von W. Szwarc  11

  Abbildung 5: Verzweigung bei Erreichen der linken Kante  13

  Abbildung 6: Verzweigung bei Erreichen der unteren Kante  13

  Abbildung 7: Einfügen einer Wartezeit für A 1 bei M j  15

  Abbildung 8: Graphische Darstellung des Produktionsablaufs III  16

  Abbildung 9: Maschinenfolgegantt für J7 n 3 Z  18

  Abbildung 10: Ablaufgantt für die Gesamtlösung G 1  20

II  Tabellenübersicht  

Tabelle 1:  Bearbeitungszeit von Auftrag i auf Maschine j.  4

Tabelle 2:  Maschinenfolgen der beiden Aufträge  4

Tabelle 3:  Ermittelte Wartezeit für A 1 nach Anwendung  

  von Algorithmus 2.  10

Tabelle 4:  Übersicht relevanter Produktionsabläufe für  

  das Problem J7 n 2 Z  17

Tabelle 5:  Optimale Programmabläufe aller Einzelprobleme  19

Tabelle 6:  Auftragsreihenfolgen auf den einzelnen Maschinen  

  für G 1 und G 2  20

Graphische Verfahren zur Lösung der Maschinenbelegung III

Übersicht verwendeter Algorithmen

Algorithmus 1 .................................................................................................. 9 Vorgehensweise zur Bestimmung von kürzesten Wegen bzw. Linien in einem Operationsfeld, wenn der Produktionsablauf gegeben ist.

Algorithmus 2 .................................................................................................. 10 Verfahrensanweisung zur Ermittlung eines Produktionsablaufs mit minimaler Zykluszeit.

Algorithmus 3 .................................................................................................. 12 Vorschrift zur Verzweigung eines Weges wenn dieser auf ein Konfliktfeld trifft.

Graphische Verfahren zur Lösung der Maschinenbelegung IV

Symbolverzeichnis

A i : Abkürzung für Auftrag i a i : Bereitstellungszeitpunkt eines Auftrags i : Beschreibung der Zielsetzung : Menge von Linien, relevant in Abschnitt 2.2.2 D i : Durchlaufzeit des Auftrags i d(...) : Distanz bzw. Schrittanzahl zwischen zwei benachbarten Knoten F i : Zeitpunkt der Fertigstellung von Auftrag i f i : Bearbeitungsfortschritt von Auftrag i G k : Gesamtlösung, mit Index versehen i : Variable zur Kennzeichnung eines Auftrags, auch für einzelne Arbeitsgänge nach Hinweis im Text verwendet J : Symbol für Job Shop-Problem (Werkstattfertigung) j : Variable zur Kennzeichnung einer Maschine L : Abkürzung für Linie bzw. Weg, mit Index versehen l, l : Bezeichnung von Linien in Abschnitt 2.2.1 M : Abkürzung für Maschine M j : Bei Produktionsablauf: Auftrag mit kleinerem Index zuerst M j : Bei Produktionsablauf: Auftrag mit größerem Index zuerst m : Anzahl der vorhandenen Maschinen µ : Symbol für die Maschinenfolge, mit entsprechendem Index n : Anzahl der zu bearbeitenden Aufträge bzw. Jobs P : Produktionsablauf, beim Diagonal-Verfahren mit röm. Index p ij : Wartezeit des Auftrags i auf Bearbeitungsbeginn auf Maschine j p iZ : Wartezeit von A i bis Produktionsprozess abgeschlossen ist (w) : Menge der mit w benachbarten Knoten S : Beginn des Produktionsprozesses, Koordinatenursprung s j : Frühestmöglicher Bearbeitungsbeginn beider Aufträge auf M ^j t : Bearbeitungszeit, mit entsprechendem Index versehen w : Symbol für einen Knoten (x,y) : Koordinatenangaben

Graphische Verfahren zur Lösung der Maschinenbelegung V

Z : Abkürzung für Zykluszeit ZE : Zeiteinheit(en) z : Zeitverlauf, ein Index steht für den jeweiligen Auftrag ij : Bearbeitungsbeginn von Auftrag i auf Maschine j ij : Bearbeitungsende von Auftrag i auf Maschine j * : Kennzeichnet Optimalität der entsprechenden Variablen

Mathematische Symbole

: = : Definiert als

= > : Größer

m : Größer gleich * : Malzeichen A x B : Kreuzprodukt oder kartesisches Produkt hor : Anzahl horizontaler Schritte (=Länge der horizontalen Segmente) ver : Anzahl vertikaler Schritte (= Länge der vertikalen Segmente) ^-0,5 dia : Länge aller diagonalen Segmente einer Linie, wenn mit 2 multipliziert ergibt sich die Anzahl diagonaler Schritte max : Maximum min : Minimum

Graphische Verfahren zur Lösung der Maschinenbelegung 1 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

¹ Die praktische Relevanz ist hauptsächlich im Rahmen der industriellen sind.

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

² ist die Maschinenbelegungsplanung Produktionsprozessplanung zusammensetzt,

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 A i (i = 1,...,n) auf m Maschinen M j (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

³ Aufgrund verschiedener Kombinationsmöglichkeiten von Minimum erreicht.

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 ⁴ Die abkürzenden Schreibweise, bestehend aus den Tripeln [ | | ] verwendet. Symbole entsprechen dabei:

¹ Vgl. NEUMANN/MORLOCK (1993, S. 474).

² Vgl. SIEGEL (1974, S. 13ff).

³ Vgl. NEUMANN/MORLOCK (1993, S. 474).

⁴ Vgl. DOMSCHKE et al. (1997, S. 283).

Graphische Verfahren zur Lösung der Maschinenbelegung 2 : Maschinencharakteristik

Der Parameter = 1 , 2 wird zur Beschreibung der Maschinenart- und : Auftragscharakteristik

: Zielsetzung

Insbesondere aufgrund der Konstellationen der Parameter und 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 t ij eines Arbeitsganges auf einer bestimmten Maschine, als auch die Reihenfolge µ im , in welcher die einzelnen

⁶ Maschinen M j zu durchlaufen sind, als bekannt und gegeben vorausgesetzt. 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.

⁵ Siehe DOMSCHKE et al. (1997, S. 286ff).

⁶ Vgl. DOMSCHKE et al. (1997, S. 285).

Graphische Verfahren zur Lösung der Maschinenbelegung 3 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 {F i | 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. F i

⁷ Da weiterhin kennzeichnet den Fertigstellungszeitpunkt des Auftrags i. angenommen wird, dass beide Aufträge im Zeitpunkt 0 beginnen, entspricht die Minimierung der Zykluszeit der Minimierung der maximalen Durchlaufzeit (D max : = max {D i | i = 1,...,n} mit D i : = F i - a i , wobei a i den Bereitstellungs- ⁸ Insbesonderewerden im Folgenden zeitpunkt des Auftrages i beschreibt).

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 t ij 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

⁷ Siehe DOMSCHKE et al. (1997, S. 292).

⁸ Ebenda (1997, S. 294).

Graphische Verfahren zur Lösung der Maschinenbelegung 4

und Tabelle 2 in Matrixform dargestellt.

Tabelle 1 Tabelle 2

Bearbeitungszeit von Auftrag i auf Maschine j Maschinenfolgen der beiden Aufträge

(Quelle: Eigene Darstellung) (Quelle: Eigene Darstellung)

Das vorliegende Problem kann durch ein Gantt-Diagramm veranschaulicht werden. Über der Zeitachse werden die Bearbeitungszeiten der beiden Aufträge in Balkenform abgetragen. Die Länge eines Teilstücks des Balkens ist dabei proportional zu der jeweiligen Operationszeit. Diese Form der Darstellung wird als Maschinenfolgegantt bezeichnet. Eine andere Darstellungsform ist als Auftragsfolgegantt bekannt. Bei dieser Variante werden die Auftragsfolgen auf den

⁹ einzelnen Maschinen in Balkenform über der Zeitachse abgetragen. Auftrag i

^A 2 ^µ 21 ^{= M 4 A} 1

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 F i eines jeden Auftrags i direkt ablesbar. Es ist jedoch unmittelbar zu erkennen, dass hier die Maschinen M ² und M 7 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. Bei dem 1956 von Akers vorgestellten graphischen Verfahren werden solche Konfliktsituationen umgangen. Dazu wird zunächst ein konventionelles XY-

⁹ Siehe FANDEL et al. (1996, S. 28).

Graphische Verfahren zur Lösung der Maschinenbelegung 5

Koordinatensystem konstruiert. Die beiden Achsen repräsentieren hierbei den Bearbeitungsfortschritt f i der beiden Aufträgen A 1 und A 2 . An den Achsen wird für jeden Arbeitsgang von Auftrag i die auf der Maschine j beanspruchte Zeit t ij

¹⁰ Ausgangspunkt ist der Koordinatenursprung eingetragen, wobei j = µ i1 ,...,µ im gilt.

S = (a 1 ,a 2 ) mit a 1 = a 2 = 0. Wird ein Auftrag i nun ohne Unterbrechung bzw. Wartezeit gefertigt, so stellt F i : = j t ij den frühestmöglichen Zeitpunkt der ¹¹ Die Punkte S und F = (F 1 ,F 2 ) spannen ein Rechteck, Fertigstellung von A i dar.

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 [S i ,F i ] in genau m disjunkte Intervalle [ ij , ij ] unterteilt werden, die entsprechend der jeweiligen Maschinenfolge µ im in der Reihenfolge j = µ i1 ,...,µ im angeordnet sind. Das Symbol ij kennzeichnet hierbei den Bearbeitungsbeginn des Auftrags bzw. Arbeitsganges i auf der Maschine j und ij entsprechend das Bearbeitungsende. Durch [ 1j , 1j ] x [ 2j , 2j ] wird für jede Maschine j ein Rechteck definiert, wobei alle Punkte innerhalb dieses Rechteckes eine gleichzeitige Bearbeitung der beiden Aufträge auf

¹² Solche Konfliktfelder werden in den der selben Maschine j implizieren. 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

¹³ Die Linie oder der Weg darf dabei nur aus Koordinatenwerte aufweisen.

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

¹⁴ Ein horizontaler Streckenabschnitt bedeutet somit die alleinige zulässig.

Bearbeitung des an der Abszisse abgetragenen Auftrags und ein vertikaler Abschnitt symbolisiert die ausschließliche Fertigung des an der Ordinate abgetragenen Auftrags. Diagonale Abschnitte kennzeichnen eine gleichzeitige Bearbeitung

¹⁰ Vgl. AKERS (1956, S. 244).

¹¹ Siehe DOMSCHKE et al. (1997, S. 301).

¹² Ebenda (1997, S. 301f).

¹³ Siehe FANDEL et al. (1996, S. 33f).

¹⁴ Siehe AKERS (1956, S. 244).

Graphische Verfahren zur Lösung der Maschinenbelegung 6

beider Aufträge. Die Zykluszeit Z ergibt sich aus der Anzahl der benötigten

^-½ Schritte bzw. durch ver + hor + ( dia * 2 ).

Etwas einfacher zu handhaben als die von Akers verwendete Bestimmung der

¹⁵ ist die Berechnung der Summe aus F i und der Länge Durchlauf- oder Zykluszeit

von denjenigen Teilstrecken, die eine Nichtbearbeitung des jeweiligen Auftrags i darstellen.

^* sollten demnach möglichst viele Für die gesuchte minimale Zykluszeit Z Z diagonale Teilstrecken durchlaufen werden. Dabei sind = max {F 1 ,F 2 } als untere

¹⁶ Z Schranke und = F 1 + F 2 als triviale obere Schranke gegeben. Für das Problem [ J7 | n=2 | Z ] ergibt sich die folgende Graphik: Auftrag 2

S = (0,0)

An den Achsen sind die einzelnen Teilintervalle des jeweiligen Auftrags entsprechend seiner Maschinenfolge angedeutet. Die schraffierten Flächen stellen das Konfliktfeld pro Maschine dar. Da bei dem Verfahren von Akers beliebig viele Wege konstruiert werden können, wurde jeder eingezeichnete Verzweigungspunkt eindeutig durch eine alphabetische Kennzeichnung hervorgehoben. Auf diese ¹⁵ Siehe AKERS (1956, S. 244).

¹⁶ Vgl. DOMSCHKE et al. (1997, S. 302).