AGVs und Algorithmen

• Maschinengruppen werden mit Material versorgt

• Aufträge werden von Station zu Station transportiert

• Fahrerlosen Transportsystemen (FTS) bzw. AutomatedGuidedVehicles(AGVs) wickeln den Transport ab

• Zuordnung von Transportaufträgen zu Fahrzeugen muss getroffen werden

• Es kann sinnvoll sein, die Reihenfolge auf den Maschinenmit den Transporten abzustimmen

Werkstattfertigung

−Produktionseinheiten werden nach Arbeitsaufgabe geordnet.−Routen der Aufträge variieren

J= Puffer

Flexible Fließfertigung

−Routen der Aufträge sind ähnlich

−Reentrante Flüsse (und Nacharbeit) möglich

−Die Reihenfolge der Aufträge kann an den Arbeitsstationen geändert werden

Buffer hängt von Orga ab

“the determination of the order in which a set of jobs (tasks) {i|i = 1, ..., n} is to be processed through a set of machines (processors, work stations) {k|k=1...m}.” [Haupt, 1982]

"die Festlegung der Reihenfolge, in der eine Menge von Aufträgen (Aufgaben) {i|i = 1, ..., n} durch eine Menge von Maschinen (Prozessoren, Arbeitsstationen) {k|k=1...m} zu bearbeiten ist." [Haupt, 1982]

Mit Standardsprioritätsreel (FIFO, LIFO; Short processin time)

--> Bei den Regeln hat man nie diese Optionen; Lassen keine Lücken

--> Komplexes problem

Gantt Chart: Reihenfolge bilden, die Aufträge verteilt

Abbildung zeigt Immer 2 Szenarien; Einer optimiert

Maschine 2 obere: In Optimierung zuerst den roten

Maschine 3: Anordnung der Reihenfolge verändert; Rote auftrag erst hinten fertig (unten) —> Veränderung in Maschine 2; kurze pause des grauens bewirkt, dass der Rote auftrag deutlich früher fertig ist

Komplexität: NP-vollständig(Praxis)

->Optimale Lösungen können i.d.R. nicht berechnet werden

Weitere Aspekte:

1. Dynamikaspekt (Probleme / Situationen: Personen ausfälle ressouscenausfälle ect)

2. Informationsaspekt (Mit anderen Standorten; anderen Dienstleistern...es liegen nicht immer alle Infos vor)

3. Rechenzeit (Rechenzeit, hört ab 20,5 auf - Lösung: nimmt in kauf, dass qualität nicht mehr top ist - kann rechenzeit verkürzen

4. Lösungsqualität

Ansätze:

Internet-of-Things

Cyberphysische (Produktions-) Systeme

Industrie 4.0

Zentral —-> Dezentral (Anhand von Einheiten entscheiden: man fährt teilweise dezentral besser als zentral; Komplett Dezentral auch nicht möglich)

Ca  1 Stunde im Computer lösbar bei (20,5)

Wachstum, was anzahl der möglichkeiten beträgt: Unzählig viele mögliche Reihenfolgen --> Wachstum exponentiel

Optimale Verfahren

Branch & Bound - Verzweigen; geht verschiedene Zweige lang

Mathematisch Optimale Verfahren

Vorteil: Optimale Lösung

Nachteil: Nur kleine Szenarien lösbar, Hohe Komplexität

Dezentral

• Ameisen-/ Bienen-algorithmen (Schaut in der Natur wie das passiert ... zB Ameisen laufen an pheromenspur und Bienen ucken lane in die richtun oder so ..)

• Prioritätsregeln (fifo lifo ....

  
  

• Baum geht weiter auf deiner Folie

  Klasische und Erweiterte Verfahren (Dynamische Selektion / Adaption von Prioritätsregeln)

Vorteil: flexibel bei Änderungen

Nachteil: -Lösungsqualität variiert

(-exaktePlanbarkeit)

Lösunsqualität variiert; muss schauen ob richtie reel ( Bei hoher auslastun wenier rüsten; bei geringer auslatunng mehr rüsten)

Exakte Planbarkeit: ständige änderungen, bei neuen aufträgen änderungen;

Zentral

• - Shifting bottleneck (Algorithmus; rechne Basisplan (Gantt Chart) aus - und schaut wo entsteht stau, Lässt stück für stück bottlenecks ???)

• Genetische Algorithmen (Empfinden die Natur nach - Immer nur 2. beste lösung: hat kein domain wissen wie bei bottlenack wo man sieht welches probleme sind )

Vorteil: - Einsetzbar in komplexen Szenarien

Neutral: - Lösungsqualität mittel

Nachteil: - Änderungen etc. erzwingen Neuberechnung

durch dynamisken immmer neu berechnen

Wichtig:

Die optimaleLösung liegt stets auf einem der Eckpunkt (ggf. auf einer gerade von zwei Eckpunkten)

Heuristik (altgr. εὑρίσκωheurísko„ich finde“; heuriskein, „(auf-)finden“, „entdecken“) bezeichnet die Kunst, mit begrenztem Wissen und wenig Zeit zu guten Lösungen zu kommen. Heuristiken dienen zur Einschränkung des Lösungsraumes, können aber die Erreichung des optimalen Ergebnisses nicht garantieren.

Vorgehensweise zur Lösung von mathematischen Problemen: Diese Lösungsverfahren ohne Konvergenzbeweis werden entweder für Probleme eingesetzt, für die keine konvergierenden Verfahren existieren, oder sie werden zur Beschleunigung von konvergierenden Verfahren eingesetzt. Heuristik wird dann angewandt, wenn keine effektiven Algorithmen existieren; so werden häufig Branch-and-Bound-Verfahren, dynamische Optimierung und begrenzte Enumeration bei wachsender Problemgröße durch heuristische Verfahren abgelöst.

*ohne Konvergenz bedeutet hier, dass auch nach beliebig langer Laufzeit nicht garantiert wird, dass das Optimum gefunden wird.

Klassische Algorithmen versuchen, einerseits die optimale Rechenzeit und andererseits die optimale Lösung zu garantieren. Heuristische Verfahren verwerfen einen oder beide dieser Ansprüche, um bei komplexen Aufgaben einen Kompromiss zwischen dem Rechenaufwand und der Güte der gefundenen Lösung einzugehen. Dazu wird versucht, mithilfe von Schätzungen, „Faustregeln“, intuitiv-intelligentem Raten oder unter zusätzlichen Hilfsannahmen eine gute Lösung zu erzeugen, ohne optimale Eigenschaften zu garantieren.

• Dezentrale Verfahren arbeiten nicht an zentraler Stelle (z.B. Leitstand oder Planungsbüro),

• sondern die einzelnen Elemente (Maschinen oder Fahrzeuge) entscheiden sich loka lvor Ort selbst, für eine Alternative (z.B.: welcher Auftrag als nächstes bearbeitet wird)

• An zentraler Stelle laufen alle Informationen zusammen und machen das Planungsproblem sehr komplex

• An dezentraler Stelle stehen nur die wichtigsten Informationen zur Verfügung

• Dezentrale Verfahren können keine Optimalität garantieren, sind aber robuster z.B.: gegenüber Ausfällen

FIFO

SPT

EDD

Das flexible Job-Shop-Szenario berücksichtigt die Aspekte Sequenzierung, Routing und Disposition der Transportfahrzeuge. Die farbigen Kästchen, die die Aufträge darstellen, werden von den autonomen, fahrerlosen Fahrzeugen zwischen den Maschinen bewegt.

Sequenzierung: Auswahl des als nächstes zu verarbeitenden Produkts anhand von Produkteigenschaften.

Routenplanung: Auswahl einer geeigneten Maschine zur Bearbeitung des nächsten Vorgangs eines Auftrags.

Disposition: Auswahl des Gabelstaplers, um das Produkt entsprechend der Route zu transportieren.

Die Regeln lassen sich klassifizieren, z.B. nach Single-Attribute und Multi-Attribute, Single Attribute Regeln treffen ihre Entscheidung auf Basis nur eines Kriteriums:

Zeitbasiert, bspw. zur Minimierung der Durchlaufzeit. Einfaches Beispiel: First-Come-First-Serve(FCFS) (Das freie FTS nimmt den Auftrag, der am längsten wartet).

Auslastungsbasierte Regeln (workload-based). Alle Maschinen sollen ausreichend (und möglichst gleichmäßig) mit Aufträgen versorgt werden: Die Regel wählt die Quelle aus, die am vollsten ist oder das Ziel, das am leersten ist.

Distanzbasierte Regeln versuchen die Fahrwege zu minimieren und wählen daher den räumlich nächsten Auftrag aus.

Diese einfachen Regeln (singleattribute) performen relativ gut für ein Zielkriterium, aber i.d.R. sehr schlecht bei anderen. Daher werden in der Praxis häufig zusammengesetzte Regeln oder komplexere Verfahren eingesetzt.

Generierung start: Mögliche Lösung; Generierung zufälliger

Berechnung der Fitness zeigt die Lösungsqualität

Abbruchbedingungen erfüllt? 40000 Generationen durchlaufen

oder bestimmten wert generieren - meistens definiert man vorher anzahl, kann aber auch vorher aufhören wenn man sieht, dass es keine großen änderungen mehr gibt

Crossover: erzeugt kinder und tauscht teile

Mutation: zufallsbasiert kleine veränderungen

Erstellung und Bewertung der Initialpopulation

Solange bis maximale Anzahl an Generationenerreicht:

• Selektion 1:Elternselektion

• Crossover (Rekombination): Generieren derNachkommen

• Mutation (Kleine Änderungen auf zufälliger Basis um Eigenschaften hinzuzufügen)

• Bewertung der Nachkommen

• Selektion 2: Welche Individuen aus der Menge {AltePopulation}∪{Nachkommen}bilden dienächste Generation? (Alte Population vereinigt mit Nachkommen - Beste bleibt drin, schlehcte fliegen raus und es kommenn neue dazu)

Allgemein:

Evolutionäre Algorithmen können für (fast alle Problemstellungen) eingesetzt werden, stellen aber i.d.R. die zweitbeste Lösung dar, denn sie verwenden kein Domainwissen (spezifische Informationen der Problemstellung, sondern „probieren“ gezielt aus.

EAs sind ein zentrales Verfahren und können nur zur vorgelagerten Planung eingesetzt werden (oder müssen ständig eine neue Lösung berechnen, sobald es zu einer Änderung kommt)

Nur die besten Individuen sollen für das Crossoverausgewählt werden (Selektion1)

Nur die besten Individuen sollen für die nächste Generation ausgewählt werden (Selektion2)

Beispiele für Selektionsverfahren:

Turnierselektion: (Man möchte einen breiten Pool haben; um bessere Lösungen zu finden)

Ziehe zufällig zwei oder mehr Individuen aus der Population.

Der Bessere gewinnt (evtl. auch probabilistisch, d.h. der Bessere gewinnt mit höherer Wahrscheinlichkeit).

Rangbasierte Selektion (bestimme Rangliste nach Güte und wähle aus)

Zusätzlich kann Elitismus eingesetzt werden: Das beste Individuum wird automatisch in die nächste Generation übernommen.

Verantwortlich für das Generieren neuer Lösungen

Verschiedene Rollen:

Crossover: Die neuen Individuen sollen möglichst viele Eigenschaften der Eltern„erben“ (Kombinationen: Kombination von einem Anfang und von anderen Ende)

Mutation: Geringfügige Modifikation eines Individuums

Da wir das TSP lösen wollen, müssen beide Operatoren auf Permutationen arbeiten:

Mutation mit Swap operator:

Tauscht 2 Knoten aus

Zufällig hat man Plan verändert weil man 2 Zahlen austauscht

Der hintere Teil nihct so gut, aber von 2 zu 7 ist gut

Swap mutationoperator

Wähle zufällig zwei Zahlen der Permutation und vertausche sie:

One-pointcrossover

Wähle zufällig den Crossover-Punkt

Behalte für jeden Elter den Teil der Permutation bis zum Crossover-Punkt. Die Zahlen nach dem Crossover-Punkt werden so sortiert, wie sie im anderen Elternteil vorliegen.

4 neue lösungen; 2 besten kommen weiter die anderen fliegen raus

rot - 768 getauscht, weil das die Reihenfolge ist im roten Beispiel oben um zu kombinieren

gelb - 854 ist oben nach sorierung 458 (im gelben)

(1, 2, 3, 4) besitzt eine Weglänge von

2 + 1 + 10 + 4 = 17

(1, 4, 2, 3) besitzt eine Weglänge von

4 + 2 + 1 + 2 = 9

Treten weitere stochastische Einflüsse auf (z.B. Ausfälle) können / müssen Individuen mit Simulationsläufen bewertet werden.

Wie könnte eine konkrete Implementierung für das TSPaussehen?

1. Erstelle 50 zufällige Permutationen (Initialpopulation) und bewertediese.

2. Wiederhole500-mal:

   • Selektion 1: Wähle 50 Elternpaare mittels Turnierselektion

   • Crossover: Erstelle 50 Kinder mittels One-Point-Crossover

   • Mutation: Führe auf jedem Kind mit einer Wahrscheinlichkeit von 1 % swapmutationaus.

   • Bewerte die Nachkommen

   • Selektion 2: Wähle aus den nun 100 vorhandenen Individuen 50 verschiedene Individuen mittels Tunierselektion für die nächste Generation aus. Übernehme auf jeden Fall das beste Individuum(Elitismus).

     
     

Aufgrund der Komplexität können nur sehr kleine Szenarien (bis zu 7 Aufträge im System) optimal, mathematisch berechnet werden.

Der Vergleich zeigt, dass die sehr einfache FIFO Regel deutlich schlechtere Leistung zeigt.

Forschung: Finden einer guten Heuristik

—-

Makespan optimiert; in welcher Reihenfolge werden Aufträge am schnellsten abgefertigt werdn

- vergleich Fifo von 500 auf 700 Zeiteinheiten

- Mathematische Modell (48h Rechenaufwand) --> mit 5-7 Aufträgen ist man schon an der Grenze der Kapazität; jetzt evtl 2-3 Aufträge mehr

-45-62%) Optimierung zwischen Fifo und  beste Rechnung; muss gute Heuristik finden

Gap: evtl. können bessere Lösungen gefunden weden mit mehr Zeit

Schwankende Auftragseingänge

mehrere AGVs

Beschränkte Puffer

Algorithmen für Fahrerlose Transportsysteme;

Haben neuronales Netz kreiert

• 𝑛𝑀 in 𝑀𝑆𝑖 denotes the number of material units in the 𝑖𝑡ℎ material source.

• 𝑛𝑀 in 𝑀𝐷𝑗 denotes the number of material units in the 𝑗𝑡ℎ material destination.

• 𝑛𝐼𝑉 in 𝑀𝐷𝑗 denotes the number of idle vehicle waiting in the 𝑗𝑡ℎ material destination.

• 𝑛𝑉 to 𝑀𝐷𝑗 denotes the number of loaded vehicle heading to the 𝑗𝑡ℎ material destination.

Die Ausgänge stehen jeweils für eine bestimmte Zuordnung. Der höchste Wert entscheidet.

Sollte die Zuordnung nicht möglich sein, wird die zweithöchste genommen.

• Die Gewichte der NN werden generiert.

• Die NN werden in einer Simulation als Auswahlregel eingesetzt. Die Güte des Ablaufs wir bestimmt (Fitness)

• Iteratives Verfahren analog zum Vorgehen der EAs

Nach 50 durchgängen keine bessere lösung gefunden

- waren am anfang bei 90%

• FIFO

• Nearast-Vehicle-First

• Neuronale Netze nach der Generierung

Auftrag der zuerst ankommt und Fahrzeug was am nächsten dran ist wird mit Neuronalen Netz verglichen; von 90% auf 94,5% --> 4,5% verbesserung

• Problemstellungen sind in der Praxis i.d.R. so komplex, dass optimale Abläufe nicht berechnet werden können (bei 7-10 aufträgen schluss)

• Heuristiken berechnen gute Lösungen mit vernünftigem Rechenwand

  • Weitere Potenziale werden erforscht und durch maschinelles Lernen und KI entwickelt

• Durch die CPS und die Veränderungen der Industrie 4.0 werden dezentrale Lösungen möglich und führen zu erhöhter Robustheit

LÖSUNG