Inhaltsverzeichnis

Abk  ürzungsverzeichnis:  III

Abbildungsverzeichnis  :  III

Tabellenverzeichnis  :  III

1  Einführung.  1

1.1  Problemstellung  1

1.2  Gang der Untersuchung.  2

1.3  Definition und Einordnung der Fließfertigung im PPS - System.  3

2  Tabu - Search Verfahren  4

2.1  Historische Entwicklung  4

2.2  Mathematische Grundlagen.  5

2.3  Allgemeiner Ansatz des Tabu Search Verfahrens  6

2.3.1  Erläuterung grundlegender Begriffe  7

2.3.1.1  Zug  7

2.3.1.2  Tabuliste  8

2.3.1.3  Tabudauer  9

2.3.2  Das Tabu Search Verfahren als Algorithmus  10

2.4  Verwendung des Tabu Search Verfahrens zur Lösung eines  

Maschinenbelegungsproblems   11

3  Ameisenalgorithmus.  13

3.1  Anwendungsbereiche  13

3.2  Das Brückenexperiment.  14

3.3  Modellierung von künstlichen Ameisen  16

3.4  Allgemeiner Ansatz des Ameisenalgorithmus  17

3.5  Verwendung des Ameisenalgorithmus zur Lösung des Traveling  

Salesman  Problems (TSP)  18

3.6  Beispielhafte Belegung des Algorithmus anhand eines Ein-  

Maschinen  - Planungsproblems  21

3.7  Verwendung des Ameisenalgorithmus zur Lösung eines Ein-  

Maschinen  - Planungsproblems  21

4  Schlussbetrachtung.  23

Literaturverzeichnis.   IV

Anhang.   VIII

II

Abkürzungsverzeichnis:

ACO Ant Colony Optimization ACS Ant Colony System AS Ant System FIFO first in first out PPS Produktionsplanung und Steuerung SA Simulated Annealing TS Tabu Search TSP Traveling Salesman Problem

Abbildungsverzeichnis:

Abbildung 1: Fertigungsverfahren im Industriebetrieb.....................................3 Abbildung 2: Darstellung des Brückenexperimentes.....................................14

Tabellenverzeichnis:

Tabelle 1: Rüstmatrix.....................................................................................10 Tabelle 2: 1. Iteration bei Auftrag j = 1...........................................................11 Tabelle 3: 2. Iteration bei Auftrag j = 5...........................................................12

III

1 Einführung

1.1 Problemstellung

Angesichts des wachsenden Konkurrenzdruckes, der durch die Globalisierung zunehmend gefördert wird, müssen sich Unternehmen der Herausforderung stellen, den Produktionsablauf flexibel an die Marktbedingungen anzupassen.

Insbesondere das Maschinenbelegungsproblem birgt noch ein hohes Verbesserungspotential. Algorithmen werden ständig verbessert, angepasst oder auch neu entwickelt. Unter der Vielzahl von Lösungen die entwickelt wurden, lassen sich exakte, spezielle heuristische und metaheuristische Methoden unterscheiden. ¹ Die erste Gruppe der Verfahren, in die beispielsweise die ganzzahlige lineare Optimierung oder die Vollständige Enumeration eingeordnet werden können, sind lediglich für einige Spezialfälle (wie z.B. den Zwei-Maschinen flow shop unter der Zielsetzung der Minimierung der Zykluszeit) effizient lösbar. Heuristische Verfahren, wie beispielsweise unvollständig durchgeführte Branch-and-Bound -Verfahren, liefern keine befriedigende Lösung des Problems, da ihre Anwendung an Modellannahmen geknüpft sind, die das reale Problem nur unzureichend abbilden. 2

Ebenso wie die heuristischen Verfahren ermitteln metaheuristische Verfahren, wie das Simulated Annealing, Genetische Algorithmen oder Tabu Search keine optimalen, sondern Kompromisslösungen. Der Vorteil der Methoden der letzten Gruppe ist aber, dass sie flexibel, robust und einfach in der Anwendung sind. ³ Gegenstand dieser Arbeit ist daher eine kritische Auseinandersetzung mit metaheuristischen Verfahren insbesondere dem Ameisenalgorithmus und dem Tabu Search Verfahren und deren Einordnung in ein modernes PPS-System.

¹ Vgl. Domschke/Scholl/Voss (1997), S. 39-45.

² Vgl. Domschke/Klein/Scholl (1996), S. 606-610.

³ Ebenda.

1

1.2 Gang der Untersuchung

Im ersten Teil dieser Arbeit wird eine grundlegende Einführung in das Thema gegeben. Zusätzlich zu der Problemstellung wird insbesondere auf die Fließfertigung Bezug genommen, da sie eine häufig verwendete Fertigungsform der Industrie darstellt, auf die, die im Folgenden erläuterten Algorithmen anwendbar sind.

Das Tabu Search Verfahren ist Gegenstand des zweiten Teils. Hierbei wird zunächst die historische Entwicklung beschrieben. In einem weiteren Schritt werden die elementaren mathematischen Grundlagen der linearen Optimierung gelegt, um das Tabu Search Verfahren im Weiteren darauf aufbauen zu können. Ferner werden die wichtigsten Begriffe des Tabu Search Verfahrens erläutert, um dann auf das eigentliche Verfahren einzugehen, welches durch ein einfaches Maschinenoptimierungsproblem erläutert wird. Zusätzliche Erläuterungen zu diesem gewählten Beispiel sind dem Anhang entnehmbar.

Im dritten Teil der Arbeit wird der Ameisenalgorithmus in vielfältigen Ausführungen erläutert. Zunächst werden mögliche Anwendungsbereiche dargestellt. Im Folgenden wird eine Brücke zwischen den Beobachtungen der Natur und der daraufaufbauenden Theorie geschlagen. Aus Gründen der Veranschaulichung wird daher zunächst der Basisalgorithmus durch das Travelling Salesman Problem erklärt. Daraufhin wird die besondere Vorgehensweise des Algorithmus auf ein Ein-Maschinen-Planungsproblem angewandt.

Im vierten Teil der Arbeit findet sich eine kurze Gegenüberstellung der Algorithmen, sowie eine kurzen Ausblick auf zukünftige Entwicklung.

2

1.3 Definition und Einordnung der Fließfertigung im PPS -System

In der gängigen Literatur gibt es viele Ansätze um Fließfertigung zu definieren. Eine jedoch klassische Definition ist in den Beiträgen von Mäckbach/Kienzle zu entnehmen, die unter Fließfertigung die „örtlich fortschreitende, zeitlich bestimmte, lückenlose Folge von Arbeitsgängen“. ⁴ verstehen. Die Fließfertigung ist dadurch gekennzeichnet, dass Maschinen und Arbeitsplätze räumlich nach dem Fertigungsablauf angeordnet sind. ⁵ Hansmann nennt folgende Vorteile der Fließfertigung: 6

• Durch die geringe Durchlaufzeit ist für das Zwischenlager eine geringe Kapitalbindung erforderlich

• Der Produktionsablauf ist übersichtlich

• Es fallen niedrige innerbetriebliche Transportkosten an

• Es können Rationalisierungsmöglichkeiten ausgenutzt werden

• Fließfertigung ermöglicht geringeren Ra umbedarf

Demgegenüber sieht Hansmann folgende Nachteile: 7

• Die Einrichtung einer Fließstrecke erfordert einen hohen Kapitalbedarf

• Es gibt sehr hohe Fixkosten

• Beschäftigungsschwankungen und Produktvariationen führen zu hohen Kostenbelastungen

• Störungen auf einzelnen Maschinen wirken sich häufig auf gesamte Fließproduktion aus

• Die eintönige Arbeit erfordert eine hohe psychische Belastung der Mitarbeiter

⁴ Vgl. Mäckbach/Kienzle (1926), zitiert bei Hansmann (2001), S. 137.

⁵ Vgl. Schneeweiß/Söhner (1991), S. 21.

⁶ Vgl. Hansmann (2001), S. 141.

⁷ Ebenda.

3

Im Folgenden wird nun in Abbildung 1 die Fließfertigung aufgrund der häufigen Bezugnahme in die Systematik der Fertigungsverfahren eingeordnet.

Abbildung 1: Fertigungsverfahren im Industriebetrieb 8

2 Tabu - Search Verfahren

2.1 Historische Entwicklung

Das Tabu Search Verfahren ist ein Verfahren der Nachbarschaftssuche. F.Glover im Jahre 1977 und 1986 ⁹ bzw. P.Hansen und B. Jaumard ¹⁰ haben hierzu Ausarbeitungen bzw. Publikationen verfasst, die als Basis für die heutige Wissenschaft der Optimierungsprobleme im Industriebetrieb gelten. Traditionell wird Tabu Search für das Lösen kombinatorischer Optimierungsprobleme genutzt.

Die Entwicklung von Tabu Search wird zur Zeit im Wesentlichen von Voß, Glover und Laguna vorangetrieben. ¹¹ Die Grundlagen zur Lösung kombinatorischer Optimierungsprobleme haben sich im Zeitablauf durch die

⁸ Vgl. Wöhe (2000), S. 441.

⁹ Vgl. Glover (1977) sowie Glover (1986).

¹⁰ Vgl. Domschke/Drexl (1998), S. 117.

¹¹ Vgl. Voß (1993), S. 333-353.

4

Zuhilfenahme moderner Software deutlich verbessert, so dass die Forschung in diesem Bereich auch zunehmend auf die Informatik angewiesen ist. 12

2.2 Mathematische Grundlagen

Für ein kombinatorisches Optimierungsproblem gelten die Gesetze der Kombinatorik. Es wird repräsentiert in der Form min c(x): x ∈ S in R n . Dabei ist c(x) der Zielfunktionswert von x. x ist ein Lösungsvektor aus der Menge aller Lösungsvektoren S (auch Suchraum genannt), für die die Funktion c(x) im n-dimensionalen Raum definiert ist. Die Formel setzt ein Minimierungsproblem voraus, eine Maximierung von c(x) ist natürlich ebenso zulässig.

Des Weiteren kann man die Menge der Lösungsmöglichkeiten noch weiter einschränken, indem man nur diese Werte aus S zu lässt, für die auch alle eventuellen Nebenbedingungen erfüllt sind. ¹³ Man spricht dann vom zulässigen Suchraum.

min c(x): x ∈ F in R n mit F⊆ S

Eine wichtige Eigenschaft eines Lösungsvektors x ist seine Nachbarschaft N (x). Es handelt sich dabei um die Menge benachbarter Vektoren, die man durch eine Operation auf dem Vektor x erreichen kann. Eine solche Operation nennt man einen Zug m. In Abschnitt 2.3.1.1 wird dieser näher erläutert. Wie weit eine solche Operation reicht, wird vorher festgelegt. Beispielsweise könnte es sich in einer paarweisen Vertauschung von Elementen des Vektors ausdrücken. Ein Zug x⊕ m ∈ M führt zu einer neuen Lösung x 1 = x⊕ m ≠ x mit x 1 ∈ S Wenn

¹² Vgl. Dowidath/Zeeb (2002), S. 14.

¹³ Vgl. Glover (1989), S. 190.

5