Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Lösungen für Job Shop Probleme umrechnen Disjunctiven Graphen / Permutationen
Autor
Kein bestimmter Bereich Lösungen für Job Shop Probleme umrechnen Disjunctiven Graphen / Permutationen
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2002
  Themenstart: 2022-01-17

Hallo Leute! Ich möchte verschiedene Lösungsdarstellungen für Job-Shop-Probleme umrechnen. Bisher habe ich eingeschränkte Permutationen verwendet und daraus z.B. Gantt-Diagramme erzeugt. (a) Eine Lösung von MT06 mit ff = 55 als Permutaion. perm = [1 2 7 19 31 13 8 25 14 32 ... 9 20 15 3 16 21 33 34 26 22 ... 27 23 10 4 17 11 35 12 28 36 ... 5 24 29 18 6 30]; Mit so einer Reihenfolge kann man die Vorgänge gut in ein Gantt-Diagramm eintragen. https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_MT06_Gantt.gif (a) ein Gantt-Diagramm für MT06 erzeugt aus einer Permutation perm' = [13 1 7 19 31 2 8 25 14 32 ... 9 20 15 26 16 21 33 34 3 22 ... 27 23 10 4 17 11 18 12 5 35 ... 28 24 29 36 6 30] https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_MT06_Gantt_permstrich.gif (a') ein Gantt-Diagramm für MT06 aus der Permutation perm' (ergibt Bild wie (c) unten) https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_Henning_MT6_L_sung_kleiner.jpg (b) Eine Lösung von MT06 als Disjunctiven Graphen. https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_Henning_MT6_L_sung_Gantt_kleiner.jpg (c) Eine Lösung von MT06 als Gantt-Diagramm. Was mich interessiert: (1) Wie kann ich Lösungen von Permutationen in eine Darstellung von Disjunctiven Graphen umwandeln? (2) Wie kann ich Lösungen von Disjunctiven Graphen in Darstellungen von Permutationen umwandeln? Viele Grüße Ronald Edit: ich habe mal oben die Permutation perm' gebildet; mit Angleichung an das untere (c) Gantt Diagramm


   Profil
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 4074
Wohnort: Raun
  Beitrag No.1, eingetragen 2022-01-22

Hallo Ronald, nach längerem Draufschauen bin ich zu dem Ergebnis gekommen, dass die farbigen Elemente in jeweils einem Graph den Zeilen im anderen Graph entsprechen, mit Berücksichtigung der vorgegebenen Reihenfolge. Um einen Graph in den anderen umzuwandeln, muss man also gleichfarbigen Elemente in je eine Zeile schreiben und die ursprünglichen Zeilen dann unterschiedlich farbig markieren. Viele Grüße, Stefan


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2002
  Beitrag No.2, vom Themenstarter, eingetragen 2022-01-22

Hallo StefanVogel! Um dieses klassische MT06 Beispiel noch besser zu verstehen, hier mal noch weitere Daten des Problems (anhand der Gantt-Diagramme schon zu sehen): m = [2 0 1 3 5 4 1 2 4 5 0 3 2 3 5 0 1 4 1 0 2 3 4 5 2 1 4 5 0 3 1 3 5 0 4 2]; m = m + 1; l = [1 3 6 7 3 6 8 5 10 10 10 4 5 4 8 9 1 7 5 5 5 3 8 9 9 3 5 4 3 1 3 3 9 10 4 1]; mit m als Maschinen von 0 bis 5 [oder 1 bis 6 verschoben] und den Zeiten l für die Vorgänge 1 bis 36. Anmerkung: Der kritische Pfad/kritische Weg in meinem Gantt-Diagramm (a') stimmt nicht ganz: der Vorgang 4 ist nicht kritisch, da der nachfolgende Vorgang 5 nicht kritisch ist und auf 4 nicht unmittelbar ein kritischer Vorgang folgt der Vorgang 3 ist nicht kritisch, da der nachfolgende Vorgang 4 nicht kritisch ist und auf 3 nicht unmittelbar ein kritischer Vorgang folgt Richtige kritische Pfade sind im 2.Beispiel (c) zu sehen.


   Profil
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 4074
Wohnort: Raun
  Beitrag No.3, eingetragen 2022-01-22

Dann verstehe ich jetzt, was in Bild (a') mit den "X" gemeint war: Die Bestandteile vom kritischen Pfad. Dann fehlt noch ein X in 21, 22, 23 und 27 verglichen mit Bild (c).


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2002
  Beitrag No.4, vom Themenstarter, eingetragen 2022-01-22

Ich hatte bisher einen kritischen Pfad (leider bisher nicht ganz richtig) berechnet; nicht mehrere falls es die gibt. Manche Optimierungsverfahren benutzen die Information des kritischen Pfades. Nur eine Veränderung des kritischen Pfades kann zu einer Reduzierung der Zielfunktion (bei mir verwendet Makespan = Gesamtzeit) führen. Bei lokalen Suchverfahren werden teilweise 2 Vorgänge aus Blöcken getauscht. In Bild (c) ist 8,25,21 ein Block oder auch 27,23,18,35,6 oder auch 7. Man hat festgestellt, das nur der Tausch von 2 Vorgängen in einem Block eine verringerte Zielfunktion bringen kann, falls es die ersten 2 oder letzten 2 Vorgänge eines Blocks sind (hier 8,25 // 25, 21 // 27, 23) mit Ausnahme der ersten 2 Vorgänge des 1.Blockes bzw. der letzten 2 Vorgänge des letzen Blockes (hier 35,6).


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2002
  Beitrag No.5, vom Themenstarter, eingetragen 2022-01-24

Hallo, ich habe jetzt mal das kostenlose Scheduling-Programm Lisa entdeckt. Dort wird das Programm MT06 aber anders codiert. Aber wie? \showon MT06cmax.xml { { 3 6 1 7 6 3 } { 10 8 5 4 10 10 } { 9 1 5 4 7 8 } { 5 5 5 3 8 9 } { 3 3 9 1 5 4 } { 10 3 1 3 4 9 } } { { 1 1 1 1 1 1 } { 1 1 1 1 1 1 } { 1 1 1 1 1 1 } { 1 1 1 1 1 1 } { 1 1 1 1 1 1 } { 1 1 1 1 1 1 } } { { 3 1 2 4 6 5 } { 2 3 5 6 1 4 } { 3 4 6 1 2 5 } { 2 1 3 4 5 6 } { 3 2 5 6 1 4 } { 2 4 6 1 5 3 } } \showoff liefert mittels Branch&Bound diese Lösung (ff=61 statt 55): https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_MT06_Loesung_ff61_Lisa.jpg Zielfunktion cmax -> müsste Makespan Minimierung sein. Viele Grüße Ronald Edit: und wenn man die Daten aus dem Internet so übernimmt und einträgt, stimmt es auch nicht ff=54 statt ff=55: \showon { { 1 3 6 7 3 6 } { 8 5 10 10 10 4 } { 5 4 8 9 1 7 } { 5 5 5 3 8 9 } { 9 3 5 4 3 1 } { 3 3 9 10 4 1 } } { { 1 1 1 1 1 1 } { 1 1 1 1 1 1 } { 1 1 1 1 1 1 } { 1 1 1 1 1 1 } { 1 1 1 1 1 1 } { 1 1 1 1 1 1 } } { { 3 1 2 4 6 5 } { 2 3 5 6 1 4 } { 3 4 6 1 2 5 } { 2 1 3 4 5 6 } { 3 2 5 6 1 4 } { 2 4 6 1 5 3 } } \showoff https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_MT06_Loesung_ff61_Lisa_Daten_aus_Literatur.jpg Edit: MT06 mit Lisa-Programm funktioniert: \showon { { 3 6 1 7 6 3 } { 10 8 5 4 10 10 } { 9 1 5 4 7 8 } { 5 5 5 3 8 9 } { 3 3 9 1 5 4 } { 10 3 1 3 4 9 } } { { 1 1 1 1 1 1 } { 1 1 1 1 1 1 } { 1 1 1 1 1 1 } { 1 1 1 1 1 1 } { 1 1 1 1 1 1 } { 1 1 1 1 1 1 } } { { 2 3 1 4 6 5 } { 5 1 2 6 3 4 } { 4 5 1 2 6 3 } { 2 1 3 4 5 6 } { 5 2 1 6 3 4 } { 4 1 6 2 5 3 } } \showoff https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_MT06_Loesung_ff55_Lisa_Daten_korrekt.jpg


   Profil
Delastelle hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]