Inhaltsverzeichnis

Symbol  - und Abkürzungsverzeichnis  2

1  Einleitung  3

2  Fließbandfertigung  4

2.1  Überblick.  4

2.2  Merkmale der Fließbandproduktion.  4

3  Einproduktmodelle.  6

3.1  Das Grundproblem der Fließbandabstimmung  6

3.2  Zielsetzung  8

3.3  SALBP-1  9

4  Lösungsverfahren für SALBP-1  12

4.1  Heuristiken und exakte Lösungsverfahren.  12

4.2  Das Verfahren von SALOME.  12

4.2.1  Verzweigung mit der Local Lower Bound Methode  13

4.2.2  Schrankenberechnung  16

4.2.3  Verzweigungsregeln.  17

4.2.4  Möglichkeit der bidirektionalen Einplanung  18

5  Fazit.  23

Literaturverzeichnis   24

Symbol- und Abkürzungsverzeichnis

n Anzahl der Arbeitsgänge j Index für Arbeitsgänge (j=1,…,n) V Menge aller Arbeitsgänge (={1,…,n}) c Taktzeit m Anzahl der Stationen m obere Schranke für die Anzahl der Stationen k Index für Stationen (k=1,…,m) t j Bearbeitungszeit des Arbeitsganges j t max maximale Bearbeitungszeit (=max {t j | j=1,…,n}) t sum Summe der Bearbeitungszeiten a j Vorlaufzeit des Arbeitsganges j n 0 Nachlaufzeit eines fiktiven Arbeitsganges 0 P j Menge der Vorgänger des Arbeitsganges j F j Menge der Nachfolger des Arbeitsganges j G Vorranggraph (=(V,A,t)) A Menge der direkten Vorrangbeziehungen (={(i,j) | i∈V und j∈F j }) A Anzahl von Elementen in der Menge A (Kardinalität von A)

S k Stationsbelegung, Menge aller zu der Station k zugeordneten Arbeitsgänge t(S k ) Belegungszeit der Station k x jk Binäre Zuordnungsvariable E j Früheste Station für Arbeitsgang j L j Späteste Station für Arbeitsgang j BD Gesamtleerzeit Verbleibende Leerzeit RI k

Bandwirkungsgraph BG Untere Schranke LB Obere Schranke UB

SALBP Simple Assembly Line Balancing Problem LLB Local Lower Bound ZE Zeiteinheit Abb. Abbildung

2

1 Einleitung

Das Produktlayout legt die Aufmerksamkeit auf eine Vereinfachung des Produktflusses. Wenn die Nachfrage nach dem Produkt hoch genug ist und über eine längere Zeit anhält, ist es üblicherweise kostengünstig die Ressourcen (Stationen; Betriebsmittel und/oder Arbeitskräfte) bei dem Herstellungsprozess nah beieinander anzuordnen. Diese typische Organisationsform der flussorientierten Produktion, die vorwiegend in der Massenfertigung vorkommt und sich durch eine hohe Ausbringungsmenge und eine niedrige Flexibilität der Produktion auszeichnet, wird als Fließfertigung bezeichnet. Insbesondere in der Produktion von Gebrauchsgütern wie z.B. Automobile, Haushalts- und Elektrotechnik wird auf diesen Typ der Fertigung zurückgegriffen.

Das Optimierungsproblem der Leistungsabstimmung der Fließbänder entsteht, wenn das Fließband umstrukturiert oder neu eingerichtet werden muss. Die Systemkapazität für Arbeitsaufgaben muss bestimmt und die Arbeitsoperationen den Stationen zugeteilt werden, sodass spezifische produktionswirtschaftliche Teilziele erreicht werden.

Entwickler und Praktiker des Operations Research beschäftigen sich mit dem Grundproblem der Fließbandabstimmung (engl.: Simple Assembly Line Balancing Problem, SALBP), das bereits seit über fünf Jahrzehnten eine bedeutende Fragestellung der Produktionsplanung ist.

In der vorliegenden Arbeit wird die Leistungsabstimmung bei der Einprodukt -Fließfertigung behandelt. Nach einer kurzen Beschreibung der Fließfertigung in Kapitel 2 werden vier Typen des Grundmodells der Fließbandabstimmung mit verschiedenen Zielsetzungen, wie insbesondere der Minimierung der Gesamtleerzeit oder der Maximierung des Bandwirkungsgrades, in Kapitel 3 erläutert. In diesem Beitrag werden das Problem des Typs 1 bzw. SALBP-1 und exakte Lösungsverfahren (Kapitel 4) betrachtet. Insbesondere der jüngste Algorithmus SALOME wird ausführlich vorgestellt. Kapitel 5 schließt die Arbeit und fasst die wichtigsten Schlussfolgerungen zusammen.

Die Methode wird in Scholl, Klein (1997), Scholl (1995) sowie Domschke, Scholl, Voß (1997) ausführlich dargestellt. Das Verfahren zur Lösung der Probleme, die sowohl zeitlich als auch räumlich beschränkt sind, wird in Bautista, Pereira (2006) auf Basis des Ameisenalgorithmus vorgestellt.

3

2 Fließbandfertigung

2.1 Überblick

In der Fließproduktion werden Anlagen mit ähnlichen Operationen zu Arbeitsstationen, die streng hintereinander angeordnet sind und eine beschränkte

Bearbeitungsdauer aufweisen, zusammengefasst. Die Arbeitsoperationen ¹ stellen elementare Tätigkeiten dar, die bei der Herstellung des Produktes ausgeführt werden müssen. Ein Transportsystem, meist ein Fließband, bewegt die Werkstücke unter

Berücksichtigung des technologischen Produktionsablaufs durch Arbeitsstationen fort. ² Die einzelnen Arbeitsgänge haben zudem eine fest vorgegebene Bearbeitungszeit. Um alle Arbeitsgänge auszuführen, weist das System eine bestimmte Taktzeit auf, die beispielsweise mithilfe von Erfahrungswerten der Produktnachfrage vergangener Perioden ermittelt wird. Aufgrund der technologischen Vorrangbeziehungen können die Arbeitsgänge nicht wahllos, sondern nur unter Einhaltung der Reihenfolgerestriktion

hintereinander angeordnet werden. 3

2.2 Merkmale der Fließbandproduktion

Für die Klassifizierung verschiedener Modelle ist eine genauere Betrachtung der Merkmale der Fließbandfertigung von Bedeutung.

Wird kontinuierlich nur ein homogenes Produkt gefertigt, so handelt es sich um die Einprodukt-Fließfertigung. In Rahmen der Sorten- bzw. Varianten-Fließfertigung (engl. mixed-model assembly) werden mehrere Modelle des Grundproduktes (z.B. verschiedene Typen eines Prozessors) in einer mehr oder weniger beliebigen Reihenfolge produziert. Dabei können sich die Arbeitsgänge verschiedener Varianten insbesondere durch Bearbeitungszeiten an den einzelnen Stationen unterscheiden. Sobald mehrere verschiedene Produkte auf einem oder mehreren Fließbänden produziert werden, spricht man hingegen von der Mehrprodukt-Fließfertigung (engl. multi-model assembly). Aufgrund unterschiedlicher Produkteigenschaften der einzelnen

Fertigungstücke sind Umrüstvorgänge hierbei unerlässlich. 4

¹ Weiterhin werden Arbeitsgang und Arbeitsoperation als Synonyme verwendet.

² Vgl. Bautista, Pereira (2006), S. 2016

³ Vgl. Baybars (1986), S. 909

⁴ Vgl. Scholl (1995), S. 7; Boysen et al. (2006), S. 5ff.

4

Können die Produkte nur innerhalb einer festgelegten Zeitspanne, der so genannten Taktzeit, an den einzelnen Arbeitsstationen verbleiben bevor das Band dieses Werkstück zur nächsten Station transportiert, handelt es sich um eine zeitlich gebundene bzw. getaktete Fertigung. Insbesondere im Zusammenhang mit dem Just-in-time-Prinzip ist ein bedeutender Vorteil der getakteten Fließfertigung, dass die Materialbedarfswerte sehr genau absehbar sind und der entsprechende Ort für die Bereitstellung bekannt ist. Ist dagegen bei der Durchführung eines Arbeitsganges die Arbeitsstation zeitlich nicht beschränkt, liegt eine ungetaktete Fließfertigung vor. Um die Stationen zeitlich zu entkoppeln, wird die Einrichtung von Pufferlagern benötigt. Diese nimmt die gefertigten Zwischenprodukte und Komponenten auf, bis die nächste

zu durchlaufende Arbeitstation wieder frei ist. ⁵ Anhand der Bearbeitungszeiten wird zwischen deterministischen und stochastischen Modellen unterschieden. Deterministische Modelle gehen von fixen Bearbeitungszeiten der einzelnen Arbeitsgänge aus. In einigen Fällen können sich diese, z.B. aufgrund der Lerneffekte oder durch steigende Automatisierungsvorgänge, verkürzen. Die stochastischen Modelle basieren hingegen auf der Annahme, dass die Bearbeitungszeiten nicht prognostizierbar sind. Die konkreten Abweichungen können dabei verschiedene Ursachen haben. So führen beispielsweise zufällige Maschinenausfälle in der getakteten Fließbandfertigung aufgrund der fehlenden Puffer unmittelbar zur Unterbrechung in der Produktion.

Das Zeitintervall, in dem das Werkstück bearbeitet wird, kann entweder konstant (fixe Anstoßrate) oder veränderlich (variable Anstoßrate) sein. Im ersten Fall werden die Werkstücke in gleich bleibender Zeitspanne, die gleich der Taktzeit ist, auf das Fließband aufgelegt. Bei variabler Anstoßrate wird das Werkstück erst dann bearbeitet,

wenn die nächste zu durchlaufende Arbeitsstation wieder frei ist. 6

⁵ Vgl. Scholl, Voß (1995), S. 920

⁶ Vgl. Scholl (1995), S. 17

5

3 Einproduktmodelle

3.1 Das Grundproblem der Fließbandabstimmung

Der Produktionsprozess für jedes in der Fließfertigung herzustellende Produkt kann in einzelne Arbeitsaufgaben untergliedert werden und stellt ein lückenloses Aufeinanderketten von n Arbeitsgängen dar. Diese aus verschiedenen Tätigkeiten bestehende Abfolge wird den linear angeordneten (Arbeits-)Stationen k=1,…,m zugewiesen. Das Fließband leitet dabei das herzustellende Produkt in einer fest vorgegebenen Reihenfolge von Station zur Station weiter. Jeder Arbeitsgang j (j=1,…,n) weist eine Bearbeitungszeit t j > 0 auf und wird genau einer Station

zugeordnet. Eine Arbeitsstation kann dagegen mehrere Arbeitsgänge beinhalten. ⁷ Alle Typen des Grundproblems zielen auf das Erreichen einer leistungsfähigen Ausgewogenheit des Fließbandes unter Beachtung der Vorrangrestriktionen ab. Das am häufigsten in der Literatur betrachtete Modell SALBP geht von folgenden Prämissen

und Nebenbedingungen ⁸ aus:

• Ein einzelnes homogenes Produkt wird in n Arbeitsgängen hergestellt

• Produktionsprozess ist fest vorgegeben

• Für alle Arbeitsgänge j=1,…,n sind deterministische Bearbeitungszeiten t j

• Reihenfolgebeziehungen sind durch einen Vorranggraph festgelegt

• Alle Arbeitsstationen k=1,…,m sind hinsichtlich der Belegung mit

Personal und Betriebsmitteln gleichwertig ausgestattet

• Alle Arbeitsstationen haben dieselbe Taktzeit c

• Die Anstoßrate ist fix

• Arbeitsstationen sind seriell angeordnet

Die zeitlichen Restriktionen bzw. Vorrangbeziehungen zwischen den Arbeitsgängen können anhand eines Vorranggraphen dargestellt werden.

⁷ Vgl. Bautista, Pereira (2006), S. 2016f.

⁸ Vgl. Scholl, Becker (2006), S. 667

6