ProLog Endterm

In welcher Reihenfolge soll eine Menge an gegbenen Orten, bei möglichst geringen Kosten, besucht werden?

Minimierung der Reisezeit/Reisestrecke (Kosten)

Rundreisen, Paketauslieferung, Einkaufslisten im Supermarkt, Leiterplatten

bestmögliche Lösung

nicht optimal, erfüllt aber alle Bedingungen

Kurzzyklen

Beginnt mit Inputdaten, zur Bestimmung einer zulässigen Startlösung (z.B. Nearest-Neighbor), meist nur zulässig und selten optimal

Verbesserung ausgehend von einer bereits gefundenen (zulässigen) Startlösung (z.B. 2-opt), im Idealfall bis zur optimalen Lösung

1. Startstadt wählen

2. Wurden alle Städt besucht?

3. Wenn ja —> Rückfahrt zum Startpunkt

4. Wenn nein —> Fahrt zur nächstgelegnen, noch nicht besuchten Stadt

5. zurück zu Punkt 2

aus allen Nachbarlösungen zufällig auswählen

sobald eine bessere Nachbarlösung (besserer Zielfunktionswert) gefunden wurde, wird diese als neue Ausgangslösung akzeptiert

suche alle möglichen Nachbarlösungen (die mit einer Anwendung der Auswahlregel erreicht werden können) und wähle die beste davon

sobald keine verbessernde Lösung mehr gefunden werden kann

Frühestmöglicher Startzeitpunkt

Spätestmöglicher Startzeitpunkt

Frühestmöglicher Endzeitpunkt

Spätestmöglicher Endzeitpunkt

Alle Vorgänge mir Puffer = 0 bilden den/die kritischen Pfad/e

durch zusätzliche Maschinen, zusätzliche Mitarbeiter oder Überstunden

nichts, denn nur der kritische Pfad beeinflusst die Gesamtdauer des Projektes

Kostenminimierung oder Projektdauer minimieren

Berechnung des FEZ mit Hilfe eines Netzplans

• Anzahl der Vorgänge

• Normalzeit

• Crashkosten

• Menge der unmittelbaren Vorgänger

• gewünschtes Projektende bzw. Budgetrestriktionen

• maximal einzusparende Zeit bei einem Vorgang

In welcher Reihenfolge sollen welche Aufträge auf welchen Maschinen bearbeitet werden?

Um Wartezeit, Gesamtproduktionszeit, Verspätungen usw. zu minimieren?

Minimierung der Wartezeiten, Durchlaufzeit, Zykluszeit, Verspätungen…

jede Maschine bearbeitet höchstens einen Auftrag zur gleichen Zeit

jeder Auftrag wird von höchstens einer Maschine zur gleichen Zeit bearbeitet

Bei einer Maschine: 𝛂=1

Bei mehreren Maschinen:

• 𝛂=F —> Flow Shop

• 𝛂=PF —> Permutation Flow Shop

• 𝛂=J —> Job Shop

pmtn —> Unterbrechung von Aufträgen möglich

dynamisches Maschinenbelegungsproblem

• aj —> Vorlaufzeiten (Auftragsfreigabe-, Bereitstellungstermin)

• nj —> Nachlaufzeiten (z.B. Kühlen, Reifung, Trocknen…)

Durchlaufzeitbezogene Ziele:

• Minimierung der Summe der Wartezeiten

• Minimierung der Summe der Durchlaufzeiten

• Minimierung der maximalen Durchlaufzeiten

Kapazitätsorienteierte Ziele:

• Minimierung der Zykluszeit

• Minimierung der Leerzeiten

Terminorientierte Ziele:

• Minimierung der maximalen Verspätung

SPT —> Sortierung der Aufträge nach monoton wachsenden Bearbeitungszeiten

—> geringe durchschnittliche bzw. Gesamt-Durchlaufzeit

EDD —> Sortierung nach monoton wachsenden gewünschten Fertigstellungsterminen

—> gerninge durchschnittlichte bzw. Gesamt-Verspätung

LPT —> sortierung nach monoton fallenden Bearbeitungszeiten

—> geringe Zykluszeit

ERD —> sortierung nach monoton wachsenden Bereitstellungsterminen

• [1| |Z] —> jede Reihenfolge liefert eine optimale Lösung

• [1|aj|Z] —> Earliest Release Date Regel liefert optimale Lösung

• [1|nj|Z] —> Aufträge nach monoton fallenden Nachlaufzeiten einplanen

Schrage mit Unterbrechung liefert die untere Schranke für das Problem ohne Untrerbrechung —> falls die Zykluszeiten (=Zielfunktionswerte) von Schrage ohne Unterbrechung und Schrage mit Unterbrechung übereinstimmen folgt, dass die Lösung für Schrage ohne Unterbrechung optimal ist

jeder Auftrag besteht aus genau m Arbeitsgängen, die die Maschinen jeweils in der gleichen Maschinenfolge zu durchlaufen haben —> Unterschiedliche Auftragsfolgen auf den Maschinen möglich

(z.B. Burger bei McDonalds)

Aufträge können einander nicht “überholen” —> die Auftragsfolge muss auf allen Maschinen gleich sein

jeder Auftrag besteht aus genau m Arbeitsgängen, die die Maschinen jeweils in unterschiedlichen Maschinenfolgen durchlaufen können —> dabei kann ein Auftrag auf jeder Maschine auch mehrmals bearbeitet werden oder aber auch einzelne Maschinen auslassen

anwendbar bei Flow-Shop Problemen

Ablauf:

• suche kleinstes Element der Bearbeitungsmatrix

• tritt dieses bei Maschine 1 auf, ordne den Auftrag am Ende der Liste L1 an, sonst am Beginn der Liste L2

• wenn kleinstes Element 2-mal (oder öfter) auf einer Maschine vorkommt, wähle von diesen den Auftrag mit d. größten Elementen auf d. anderen Maschine

• wenn der Auftrag angeordnet wurde, streiche ihn aus der Auswahlliste

• Auftragsreihenfolge = L1+L2

anwendbar bei Job-Shop Problemen

• JA —> Jobs, die nur auf Maschine A bearbeitet werden müssen

• JB —> Jobs, die nur auf Maschine B bearbeitet werden müssen

• JAB —> Jobs, die zuerst auf Maschine A, dann auf Maschine B bearbeitet werden müssen

• JBA —> Jobs, die zuerst auf Maschine B, dann auf Maschine A bearbeitet werden müssen

Ablauf:

• Bestimmen der Mengen JA, JB, JAB und JBA

• Reihenfolge für JAB und JBA mit Johnson Algorithmus bestimmen

• beliebige Reihenfolge für JA und JB wählen

• Ordne Aufträge auf Maschine A zur Auftragsfolge (JAB, JA, JBA)

• Ordne Aufträge auf Maschine B zur Auftragsfolge (JBA, JB, JAB)

Wenn es auf der Maschine, welche die Zykluszeit bestimmt, keine Leerzeiten gibt