Maschinenbelegung mittels Ameisenalgorithmus

Prof. Dr. K.-W. Hansmann 1

Infos

Die letzten Übungstermine:Mi, 25.01.2006 14.15 – 15.45 Uhr ErzWiMi, 01.02.2006 13.30 – 15 Uhr ErzWi

Für die Übung morgen sind KEINE Aufgaben im Netz!

Passwort für Download des Vortrags: ibl3


Operatives Management

Hier Übersicht über die Vorlesungenrein !!!

Termin Thema 1. 25.10.05 Grundlagen des operativen Produktionsmanagements

2. 01.11.05 Produktionsprogrammplanung I (Absatzprognose)

3. 08.11.05 Produktionsprogrammplanung II (Optimierungsrechnung) 4. 15.11.05 Grundlagen der Materialbereitstellung 5. 22.11.05 Brutto-Netto-Rechnung 6. 29.11.05 Losgrößenplanung I (Andler & heuristische Verfahren) 7. 06.12.05 Losgrößenplanung II (Wagner-Whitin-Algorithmus) 8. 13.12.05 Zeit- und Kapazitätsplanung

9. 20.12.05 JIT-Konzept / Produktionssteuerung mit Prioritätsregeln 10. 10.01.06 Produktionssteuerung mit Akzeptanzalgorithmen 11. 17.01.06 Vortrag Horst Wickborn, Produktionsleiter Beiersdorf AG 12. 24.01.06 Produktionssteuerung mit Ameisenalgorithmen 13. 31.01.06 Integration von Auftragsfreigabe und Maschinenbelegung 14. 07.02.06 Keine Veranstaltung


Operatives Management


nAufträge

m>1mehreren Maschinen

Arten von Problemen der Maschinenbelegung

m=1einer Maschine

Zuordnung zu

heuteletzteWoche


Zielsetzung &Praxisbeispiele

Schleifmittel

Zigarettenproduktion

Paint Shop im Automobilbau

Neue Problemstellung:Minimierung der Rüstzeiten


Reihenfolgeabhängige Rüstzeiten – Einführendes Beispiel

5 ZEA2 ZEB

8 ZECInpu

tdat

en:

A B CA - 2 1B 2 - 1 C 1 1 -Rüstmatrix

Rüstzeit von B nach C

=RBC

A

A

B

B CRBC

RAC RCBC

RAB

17

18

∑Rüstzeiten = 3

∑Rüstzeiten = 2


Äquivalenz zum Travelling Salesman Problem (TSP)

A

CB

A B CA - 2 1B 2 - 1 C 1 1 -

Entfernung

Rüstzeit

TSP: Minimiere die zurückgelegte Entfernungbei einer Rundreise durch alle Städte

=Minimiere die reihenfolgeabhängigen Rüstzeiten einer Fertigungsfolge von gegebene Aufträgen

A BRAC RCBC


Komplexität des Problems

20 Orte 2 432 902 008 176 640 000 Routen

Ein großer Computer braucht dazu ca. 77 140 Jahre Rechenzeit(bei 1 Mio. Routen pro Sekunde).

Anzahl möglicher Routen = n!

Anforderung an ein Verfahren:• in kurzer Zeit• ein gute Lösung


Erfinden einer Lösungsmethode

Unsystematisches Probieren ist aussichtslos.(zu viele Routen)

Einfache Regel: Wähle immer den nächst gelegenen Ort. (nicht schlecht, aber Verfahren ohne Gesamt-Überblick)

Optimierungs-Methode: Versuche durch wiederholte Anwendung „kluger“ Regeln immer bessere Lösungen zu erreichen und schließlich die kürzeste Route zu finden.

Die Evolution hat viele „kluge“ Regeln hervor gebracht.


Verhalten von Ameisen auf Futtersuche

• Ameisen besitzen eine Drüse am Hinterleib, mit der sie einen chemischen Lockstoff namens Pheromon auf ihrem Weg hinterlassen können.

• Nachfolgende Ameisen orientieren sich am Pheromon ihrer Vorgänger und wählen mit höherer Wahrscheinlichkeit den am stärksten markierten Weg.


Wie finden Ameisen ihren Weg zwischen Futterquelle und Ameisenhaufen?

HindernisAmeisen-

haufen Futter-quelle

Weg A = 1 Min

Weg B = 0,5 MinBei der Rückkehr hinterlassen die Ameisen eine Pheromon-

Einheit auf dem Weg



Nach 1 Minute

HindernisAmeisen-


Weg A: Pheromon = 0

Weg B: Pheromon = 1



Nach 2 Minute

HindernisAmeisen-


Weg A: Pheromon = 1

Weg B: Pheromon = 3



Nach 10 Min.

HindernisAmeisen-


Die Ameisenstrasse ist auf dem kürzesten Weg entstanden !


Übertragung auf einen Computeralgorithmus

erzeugen einen Weg

bis die maximale Iterationszahl erreicht istgeben Pheromon ab

alle Ameisen der Kolonie


Repräsentation einer Rundreiseim Rechner

2 3 1 4Weg =

10

14

1 2

43

1 2 3 41 - 10 10 14 2 10 - 14 103 10 14 - 104 14 10 10 -

Distanzmatrix14 10 14

10

Länge des Weges= 48


Ablauf der Wegkonstruktion einer Ameise

Weg =1. Ein Lösungsvektor wird sukzessive gefüllt.

2. Für jede Variable wird die Menge NBS der noch nichtbesuchten Städte ermittelt.

3. Für jede Stadt aus NBS wird die Auswahlwahrscheinlichkeit anhand der Pheromonmatrix und eines Prioritätswertes bestimmt.

4. Eine Monte-Carlo-Auswahl trifft die Entscheidung über die nächsten Stadt.

5. Gehe zu 1. wenn Lösungsvektor noch nicht gefülltsonst Ende der Wegkonstruktion


Wegkonstruktion einerAmeise 1. Schritt

Weg =

NBS={1,2,3,4}

Lösung

Menge dernicht besuchenStädte

1

1. Schritt: Zufallsauswahl

NBS={2,3,4}


Wegkonstruktion einerAmeise Schritte 2…n

NBSid

)x(Pi1

i1i1 ∈∀=

τ

1 2 3 41 - 10 10 14 2 10 - 14 103 10 14 - 104 14 10 10 -

Distanzmatrix

1 2 3 41 - 0,5 0,4 0,3 2 0,4 - 0,3 0,23 0,4 0,2 - 0,34 0,2 0,4 0,3 -

Pheromon

1 ?Weg =

(a) Menge NBS der nicht besuchten Städte bestimmen

(b) Bewertung aller Alternativen mit:

(c) Monte-Carlo-Auswahl



12

1212 d

)x(P τ=

1 2 3 412 10 - 14 103 10 14 - 104 14 10 10 -

Distanzmatrix

Pheromon

1 ?Weg =

NBS = { , , }

Bewertung

1 2 3 41234

--

--

0,5 0,40,40,4

0,4

0,3

0,30,3

0,3

0,20,2

0,2

- 10 10 14

2 3 4

Ergebnis P(x12) = 0,05



13

1313 d

)x(P τ=

1 2 3 412 10 - 14 103 10 14 - 104 14 10 10 -

Distanzmatrix

Pheromon

1 ?Weg =

NBS = { , , }

Bewertung

1 2 3 41234

--

--

0,5 0,40,40,4

0,4

0,3

0,30,3

0,3

0,20,2

0,2

- 10 10 14

2 3 4




14

1414 d

)x(P τ=

1 2 3 412 10 - 14 103 10 14 - 104 14 10 10 -

Distanzmatrix

Pheromon

1 ?Weg =

NBS = { , , }

Bewertung

1 2 3 41234

--

--

0,5 0,40,40,4

0,4

0,3

0,30,3

0,3

0,20,2

0,2

- 10 10 14

2 3 4



2

3

4

Monte-Carlo-Auswahl

NBS = { 2, 3, 4}

1 ?Weg =

Bewertung = {0.05, 0.04, 0.02}

1 2Weg =

Weiter zur nächsten Stadt

Ausgangspunkt

Menge derAlternativen

Bewertung derAlternativen

Monte-Carlo-Auswahl


Pheromonabgabe der besten Ameise

1 2 3 4Weg =Länge der Rundreise F(x) = 48Wenn die Rundreise

bestimmt ist…

Pheromonabgabe:

τ(t) = Pheromon in Iteration t

1 2 3 41 - 0,5 0,4 0,3 2 0,4 - 0,3 0,23 0,4 0,2 - 0,34 0,2 0,4 0,3 -

+=+

0

)x(F1

)t()1t( ijij ττwenn Kante von Ort i nach jin der Rundreise verwendet wird

sonst

τ(t+1) = Pheromon in Iteration t+1

1 2 3 41 - 0,52 0,4 0,3 2 0,4 - 0,32 0,23 0,4 0,2 - 0,324 0,22 0,4 0,3 -


Und so weiter…

2 4 3 1Weg =

10

14

1 2

43

1 2 3 41 - 10 10 14 2 10 - 14 103 10 14 - 104 14 10 10 -

Distanzmatrix10 10 10

10

optimale Lösung= 40


Kritik am Ameisenalgorithmus

Zeitbedarf fürBerechnung und

Umsetzung

Lösungsgüte

Prioritätsregel

TA Ameisenalgorithmus

Documents

Maschinenbelegung mittels Ameisenalgorithmus