Die Mathe-Redaktion [Home] - Neues auf einen Blick 25.03.2023 06:07 [Neues] [Forum] [Suche] - Registrieren/Login
 
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Lösungen für schwierige Job Shop Scheduling Probleme
Autor
Kein bestimmter Bereich J Lösungen für schwierige Job Shop Scheduling Probleme
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2250
  Themenstart: 2019-05-10

Hallo Leute! Wer möchte kann Lösungen zu schwierigen Job Shop Scheduling Problemen hier angeben. Ich persönlich finde Lösungen schwierig, wenn die Berechnungen zur Ermittlung der Lösung 1 Stunde oder länger auf einem modernen Computer (PC) dauern. Schwierig scheinen mir zumindest die 15x15 Probleme und das Muth-Thompson 20x5 Problem. Bei vielen Problemen kenne ich die Schwierigkeit/Komplexität bisher nicht. Zum Finden von Lösungen können Branch&Bound Programme oder Heuristiken genutzt werden. Viele Grüße Ronald

   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2250
  Beitrag No.1, vom Themenstarter, eingetragen 2019-05-10

temporäre Problemliste: teilweise übernommen von: https://www.math.uwaterloo.ca/~bico/jobshop/ Upper and Lower Bounds for the Test Problems NAME abz5 1234 (Opt) 10x10 // dumbo 5910 Nodes // 23 Sek.(*) abz6 943 (Opt) 10x10 // dumbo 532 Nodes // 2 Sek. abz7 (654, 668) 20x15 abz8 (635, 687) 20x15 abz9 (656, 707) 20x15 car1 7038 (Opt) 11x5 // dumbo 95 // ? car2 7166 (Opt) 13x4 // dumbo 41 // ? car3 7312 (Opt) 12x5 // dumbo 197 // ? car4 8003 (Opt) 14x4 // dumbo 171071 // ? car5 7702 (Opt) 10x6 // dumbo 218881 // ? car6 8313 (Opt) 8x9 // dumbo 1468 // ? car7 6558 (Opt) 7x7 // dumbo 671 // ? car8 8264 (Opt) 8x8 // dumbo 973 // ? // keine Lösung angezeigt la01 666 (Opt) 10x5 // dumbo 36 // ? la02 655 (Opt) 10x5 // dumbo 58 // ? la03 597 (Opt) 10x5 // dumbo 17 // ? la04 590 (Opt) 10x5 // dumbo 812 // ? la05 593 (Opt) 10x5 // dumbo 27 // ? la06 926 (Opt) 15x5 la07 890 (Opt) 15x5 la08 863 (Opt) 15x5 la09 951 (Opt) 15x5 la10 958 (Opt) 15x5 la11 1222 (Opt) 20x5 la12 1039 (Opt) 20x5 la13 1150 (Opt) 20x5 la14 1292 (Opt) 20x5 la15 1207 (Opt) 20x5 la16 945 (Opt) 10x10 // dumbo 3189 // 10 Sek. la17 784 (Opt) 10x10 // dumbo 20 // 1 Sek. la18 848 (Opt) 10x10 // dumbo 109 // 1 Sek. la19 842 (Opt) 10x10 // dumbo 1024 // 4 Sek. la20 902 (Opt) 10x10 // dumbo 7164 N. // 25 Sek. la21 (1040, 1053) 15x10 la22 927 (Opt) 15x10 la23 1032 (Opt) 15x10 la24 935 (Opt) 15x10 la25 977 (Opt) 15x10 la26 1218 (Opt) 20x10 la27 (1235, 1269) 20x10 la28 1216 (Opt) 20x10 la29 (1120, 1195) 20x10 la30 1355 (Opt) 20x10 la31 1784 (Opt) 30x10 // dumbo > 314000 N.(1784) // > 10h12 Min la32 1850 (Opt) 30x10 // dumbo > 303000 N.(1850) // > 10h12 Min la33 1719 (Opt) 30x10 la34 1721 (Opt) 30x10 la35 1888 (Opt) 30x10 la36 1268 (Opt) 15x15 // dumbo > 1039054 Nodes (1259) // > 10h30Min la37 1397 (Opt) 15x15 la38 (1184, 1217) 15x15 la39 1233 (Opt) 15x15 la40 1222 (Opt) 15x15 // dumbo 5246362 Nodes dann Out Of Memory (ca. 2[eher 4] GB RAM benutzt) // ca.31 h auf schnellen Computer -> (2) // LiSA Branch&Bound 2:23 h für Lösung mt06 55 (Opt) 6x6 // dumbo 10 // 1 Sek. mt10 930 (Opt) 10x10 // dumbo 7473 // 30 Sek. mt20 1165 (Opt) 20x5 // dumbo 10300579 Nodes dann Out Of Memory (ca. 2[eher 4] GB RAM benutzt) // > 15 h auf schnellen Computer -> (1) orb1 1059 (Opt) 10x10 // dumbo 51817 // 183 Sek. orb2 888 (Opt) 10x10 // dumbo 3497 // 12 Sek. orb3 1005 (Opt) 10x10 // dumbo 182861 // 741 Sek. orb4 1005 (Opt) 10x10 // dumbo 18979 // 80 Sek. orb5 887 (Opt) 10x10 // dumbo 215758 // 730 Sek. orb6 1010 (Opt) 10x10 // dumbo 12436 // 51 Sek. orb7 397 (Opt) 10x10 // dumbo 4340 // 16 Sek. orb8 899 (Opt) 10x10 // dumbo 575 // 3 Sek. orb9 934 (Opt) 10x10 // dumbo 3194 // 14 Sek. orb10 944 (Opt) 10x10 // dumbo 9318 // 31 Sek. (*) Rechenzeit auf AMD X4 3400 MHz Computer (1 Prozessor benutzt) (1) 21.300.000 Nodes, 7+GB RAM verwendet, 29+h auf 4GHz Laptop (1 Prozessor verwendet) ohne Endergebnis (2) 10.980.000 Nobdes, 7+GB RAM verwendet, 56+h auf 4GHz Laptop (1 Prozessor verwendet) ohne Endergebnis

   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2250
  Beitrag No.2, vom Themenstarter, eingetragen 2019-05-10

benutzbare Programme - Branch&Bound Programm dumbo.c von Webseite: https://www.math.uwaterloo.ca/~bico/jobshop/ nach Compilieren Aufruf mit z.B. dumbo -0 mt10.prb 930 - Lekin Scheduler: web-static.stern.nyu.edu/om/software/lekin - LiSA Scheduler: www.math.ovgu.de/Lisa.html

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

https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_Lekin_MT10_Lokale_Suche_3600Sekunden_930_kleiner.jpg (Lekin MT10 Lösung 930) https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_Lekin_MT20_1165_Lokale_Suche_3600_Sekunden_kleiner_50Prozent.jpg (Lekin MT20 Lösung 1165) Mal 2 grafische Lösungen aus Lekin. Zu MT10 (opt=930) und MT20 (opt=1165). Gefunden mit Lekin Lokale Suche je 3600 Sekunden.

   Profil
Delastelle hat selbst das Ok-Häkchen gesetzt.

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-2023 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]