Neuere Algorithmen in der Produktionssteuerung

Inhaltsverzeichnis

Abkürzungsverzeichnis:

Abbildungsverzeichnis:

Tabellenverzeichnis:

1 Einführung
1.1 Problemstellung
1.2 Gang der Untersuchung
1.3 Definition und Einordnung der Fließfertigung im PPS – System

2 Tabu – Search Verfahren
2.1 Historische Entwicklung
2.2 Mathematische Grundlagen
2.3 Allgemeiner Ansatz des Tabu Search Verfahrens
2.3.1 Erläuterung grundlegender Begriffe
2.3.1.1 Zug
2.3.1.2 Tabuliste
2.3.1.3 Tabudauer
2.3.2 Das Tabu Search Verfahren als Algorithmus
2.4 Verwendung des Tabu Search Verfahrens zur Lösung eines Maschinenbelegungsproblems

3 Ameisenalgorithmus
3.1 Anwendungsbereiche
3.2 Das Brückenexperiment
3.3 Modellierung von künstlichen Ameisen
3.4 Allgemeiner Ansatz des Ameisenalgorithmus
3.5 Verwendung des Ameisenalgorithmus zur Lösung des Traveling Salesman Problems (TSP)
3.6 Beispielhafte Belegung des Algorithmus anhand eines Ein-Maschinen- Planungsproblems
3.7 Verwendung des Ameisenalgorithmus zur Lösung eines Ein- Maschinen- Planungsproblems

4 Schlussbetrachtung

Literaturverzeichnis

Anhang

Abkürzungsverzeichnis:

Abbildung in dieser Leseprobe nicht enthalten

Abbildungsverzeichnis:

Abbildung 1: Fertigungsverfahren im Industriebetrieb

Abbildung 2: Darstellung des Brückenexperimentes

Tabellenverzeichnis:

Tabelle 1: Rüstmatrix

Tabelle 2: 1. Iteration bei Auftrag j = 1...

Tabelle 3: 2. Iteration bei Auftrag j = 5...

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.^[1] 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.^[3] 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.

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.

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“.^[4] verstehen. Die Fließfertigung ist dadurch gekennzeichnet, dass Maschinen und Arbeitsplätze räumlich nach dem Fertigungsablauf angeordnet sind.^[5] 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 Raumbedarf

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

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

Abbildung in dieser Leseprobe nicht enthalten

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^[9] bzw. P.Hansen und B. Jaumard^[10] 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.^[11] Die Grundlagen zur Lösung kombinatorischer Optimierungsprobleme haben sich im Zeitablauf durch die 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 [Abbildung in dieser Leseprobe nicht enthalten] S in Rn.

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.^[13] Man spricht dann vom zulässigen Suchraum.

Abbildung in dieser Leseprobe nicht enthalten

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

Abbildung in dieser Leseprobe nicht enthalten

führt zu einer neuen Lösung

Abbildung in dieser Leseprobe nicht enthalten

Wenn

Abbildung in dieser Leseprobe nicht enthalten

dann handelt es sich um eine unzulässige Lösung, in allen anderen Fällen um eine zulässige. Die Nachbarschaft N (x) ist dann definiert als Menge aller erreichbaren x1:

Abbildung in dieser Leseprobe nicht enthalten

Bezogen auf S wird wieder von einer zulässigen und einer unzulässigen Nachbarschaft gesprochen. Die zulässige ist die Schnittmenge aus N (x) und F:

Abbildung in dieser Leseprobe nicht enthalten

Eine wichtige Kennzahl für die Nachbarschaft ist ihre Größe. Sie gibt die Zahl der möglichen Züge vom Lösungsvektor x aus an.

Abbildung in dieser Leseprobe nicht enthalten

Zu beachten gilt: Je komplexer und weitreichender die erlaubten Operationen auf x, desto größer wird auch die Nachbarschaft von x und damit der Aufwand diese zu untersuchen. Im Extremfall entspricht die Nachbarschaft N (x) dem gesamten Suchraum der Problemstellung S und man ist wieder am Anfang angelangt und müsste eine Vollenumeration durchführen.^[14]

2.3 Allgemeiner Ansatz des Tabu Search Verfahrens

Tabu Search (TS) ist eine intelligente Metaheuristik zur Lösung kombinatorischer Optimierungsprobleme.^[15] Es hat sich als sehr erfolgreich bei einer Reihe von klassischen und praktischen Problemlösungen gezeigt.^[16]

TS soll nicht die einfachen Algorithmen ablösen, sondern dient eher dazu, diese Algorithmen zu führen, ihre Schwächen zu vermeiden oder zu beseitigen.^[17] Für Ansätze, die nur „blind“ ein lokales Minimum suchen, heißt das, sie aus dieser „Falle“ zu befreien. Deswegen spricht man bei TS und Simulated Annealing (SA) auch von Metaheuristiken.^[18] Während bei SA zufällig Lösungsmöglichkeiten aus der Nachbarschaft ausgewählt und genutzt werden, geht TS wesentlich zielstrebiger, „aggressiver“ vor, wie Glover es ausdrückt.^[19] Es wird strikt die größte Verbesserung aller benachbarten Lösungsmöglichkeiten gewählt oder – wenn dies nicht möglich ist – diese Lösungsmöglichkeit, bei der die Verschlechterung im Vergleich zur aktuellen Lösung am geringsten ist. Um lokale Optima zu überwinden, werden auch vorübergehend Züge erlaubt, die zu Zielfunktionswertverschlechterungen führen. Beim Tabu Search wird also die Auswahl einer Nachbarschaftslösung dahingehend abgeändert, dass immer die beste Nachbarschaftslösung gewählt wird, unabhängig davon, ob sie einen besseren oder einen schlechteren Zielfunktionswert als die vorige besitzt.

Damit im Fall einer Zielfunktionswertverschlechterung bei der nächsten Auswahl der letzte Schritt nicht wieder rückgängig gemacht wird, wird ein Kurzzeitgedächtnis eingeführt, welches diese Umkehrung verbietet, also „tabu“ setzt.^[20] Hierzu wird eine Tabuliste eingeführt, welche das Kurzzeitgedächtnis verkörpert und in der die verbotenen Züge für eine gewisse Zeit festgehalten werden.^[21] Glover stellt allerdings fest, dass die Nutzung des „besten verfügbaren Zuges“ oftmals die optimale Strategie ist, während andere Methoden teilweise gar nicht zum Erfolg führen können.^[22]

2.3.1 Erläuterung grundlegender Begriffe

2.3.1.1 Zug

Ein Zug ist eine Funktion, die eine Lösung in eine andere Lösung transformiert. Jede von einer Lösung x durch Ausführung eines Zuges erreichbare andere Lösung x’ wird als Nachbarlösung bezeichnet. Die Menge aller Nachbarn X’ = { x’1, ..., x’n } bildet die Nachbarschaft von x. In jeder Iteration wird ein solcher Zug ausgeführt, um von einer ermittelten Lösung x zu einer benachbarten Lösung x’ zu wandern.

Ein Zug wird durch Vertauschen oder Verschieben von Elementen durchgeführt. Hat sich im Laufe der Iterationen z.B. der Vektor [1,2,3] für die Reihenfolge der Aufträge auf den Maschinen ergeben, so wird ein Zug ausgeführt, indem die Reihenfolge zweier Variablen geändert wird. Durch einen Zug wird der Vektor [1,2,3] z.B. zum Vektor [1,3,2]. Bei einem Maschinenoptimierungsproblem besteht ein Zug darin, Maschinenreihefolgen eines Produktes zu verändern. Ein Zug, der die Wirkung eines Zuges rückgängig macht, wird als dessen Komplement bezeichnet. Ferner ist es möglich, die Problemformulierung mit Hilfe von Binärvariablen zu lösen.^[23]

2.3.1.2 Tabuliste

Die Tabuliste speichert den Suchverlauf des Algorithmus. Sie beinhaltet entgegengesetzte Aktionen von früheren Zügen. Die Leistung von TS wird hauptsächlich durch die Länge der Tabuliste und die Operatoren, die die Liste verändern, bestimmt. Operatoren legen das Hinzufügen bzw. das Entfernen von Tabuzügen fest. Bei komplexeren Aufgaben besteht das Problem, dass der Umfang der bereits besuchten Lösungen mit der Anzahl der durchgeführten Iterationen steigt.^[24] Da ein Speichern aller Lösungen hohe Speicherkapazitäten erfordert, setzt man Züge „tabu“, d.h., man beachtet sie für eine bestimmte Zeit (Tabudauer) nicht. Die Zahl der Iterationen, in denen man Züge „tabu“ setzt, ist dabei selbst festzulegen. Nach Ablauf der definierten Tabudauer wird dieser Zug wieder aus der Tabuliste gelöscht bzw. überschrieben. Hierbei gilt in der Regel das FIFO-Prinzip, dass heißt, dass der erste Zug, der tabu gesetzt wurde, auch als erstes wieder raus geht.^[25] Wesentlich bedeutender als der Startwert ist ein intelligentes Handhaben der Tabuliste, wozu auch die Länge der Tabuliste t gehört. Eine zu kurz gewählte Länge kann ein lokales Optima nicht verhindern, eine zu lange Tabuliste wird dagegen viele möglicherweise sehr gute Züge von vornherein ausschließen oder gar für den Abbruch des Verfahrens sorgen, falls alle Züge zu einer Lösung in der Nachbarschaft bereits auf der Tabuliste stehen. Grundsätzlich scheint t im Intervall von 7 bis 10 sehr gute Lösungen zu liefern.^[26]

Dadurch, dass Glover ein optimales Intervall vorgibt, kann man die Listenlänge als stochastisch bezeichnen. Ein gezielteres Vorgehen zur dynamischen Berechnung der Listenlänge bieten Battiti und Tecchiolli mit Reactive Tabu Search. Dabei wird die Länge der Tabuliste vergrößert, wenn eine Lösung mehrmals auftritt und ein lokales Optimum bereits gefunden ist.^[27]

2.3.1.3 Tabudauer

Die Tabudauer bestimmt die Größe des Erinnerungsvermögens des Algorithmus. Sie ist an die Größe des Problems anzupassen. Dies geschieht in der Regel durch umfangreiches Experimentieren.

Da experimentelles Verhalten keine optimale Vorgehensweise ist, haben sich in letzter Zeit Methoden herauskristallisiert die Tabudauer zu bestimmen.

Die statische Methode gibt die Tabudauer t zu Beginn der Ausführung des Algorithmus vor. Bei der einfach-dynamischen Methode wird t zufällig zwischen einem festen tmin und tmax gewählt.

Vereinfacht ausgedrückt, ist die Tabudauer die Zahl der Iterationen während derer ein Zug tabu gesetzt wird und bestimmt somit die Länge der Tabuliste. Glover hat in seinen Untersuchungen zum TS herausgefunden, dass eine Tabulistengröße von sieben sinnvoll ist, da dann ein hoher Effektivitätsgrad vorherrscht. Ferner ist er der Meinung, dass es empfehlenswert sei, die Tabudauern von der fünften bis zur zwölften Iteration kürzer werden zu lassen.

Problematisch kann es werden, wenn eine Verbesserung des Zielfunktionswertes nicht mehr möglich ist, da alle wichtigen Elemente tabu gesetzt worden sind. In diesem Fall setzt man sogenannte Aspirationskriterien ein. Diese sorgen dafür, dass der Lösungsraum weiter untersucht werden kann und Zyklen vermieden werden. Tabu gesetzte Züge, die eine neue beste Lösung erzeugen können, werden so trotzdem durchgeführt, um den besten Leistungsstand erreichen zu können.^[28]

[...]

---

^[1] Vgl. Domschke/Scholl/Voss (1997), S. 39-45.

^[2] Vgl. Domschke/Klein/Scholl (1996), S. 606-610.

^[3] Ebenda.

^[4] Vgl. Mäckbach/Kienzle (1926), zitiert bei Hansmann (2001), S. 137.

^[5] Vgl. Schneeweiß/Söhner (1991), S. 21.

^[6] Vgl. Hansmann (2001), S. 141.

^[7] Ebenda.

^[8] Vgl. Wöhe (2000), S. 441.

^[9] Vgl. Glover (1977) sowie Glover (1986).

^[10] Vgl. Domschke/Drexl (1998), S. 117.

^[11] Vgl. Voß (1993), S. 333-353.

^[12] Vgl. Dowidath/Zeeb (2002), S. 14.

^[13] Vgl. Glover (1989), S. 190.

^[14] Vgl. Eiselt/Sandblom (2000), S. 232 ff..

^[15] Vgl. Glover (1989), S. 190.

^[16] Vgl. Glover (1990a), S.4 ff..

^[17] Vgl. Glover (1989), S. 191 f..

^[18] Vgl. Eiselt/Sandblom (2000), S. 230.

^[19] Vgl. Glover (1989), S. 192.

^[20] Vgl. Domschke/Drexl (2002), S. 119 f..

^[21] Vgl. Glover (1989), S. 191ff. und siehe Abschnitt 2.3.1.2..

^[22] Vgl. Glover (1989), S. 192.

^[23] Vgl. Eiselt/Sandblom (2000), S. 245.

^[24] Vgl. Taillard (1991), S. 447.

^[25] Vgl. Höck (1998), S. 251.

^[26] Vgl. Eiselt/Sandblom (2000), S. 248.

^[27] Vgl. Battiti/Tecchiolli (1994a), S. 126-140.

^[28] Vgl. Glover (1990), S. 83.