| |
| Autor |
 Lösungen für Job Shop Probleme umrechnen Disjunctiven Graphen / Permutationen |
|
Delastelle
Senior 
Dabei seit: 17.11.2006
Mitteilungen: 1995
 |  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 
Dabei seit: 26.11.2005
Mitteilungen: 4069
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
Dabei seit: 17.11.2006
Mitteilungen: 1995
| 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
Dabei seit: 26.11.2005
Mitteilungen: 4069
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
Dabei seit: 17.11.2006
Mitteilungen: 1995
| 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
Dabei seit: 17.11.2006
Mitteilungen: 1995
| 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. |
|
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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
