Die Mathe-Redaktion [Home] - Neues auf einen Blick 29.05.2023 08:12 [Neues] [Forum] [Suche] - Registrieren/Login
 
Tools
GliederungspunktLatex-Bibliographie in HTML umwandeln
Mathematik: Lösen von Job Shop Problemen Teil 2 - mit dem Programmpaket "LiSA"
Released by matroid on Fr. 28. Januar 2022 06:42:50 [Statistics] [Comments]
Written by Delastelle - 178 x read [Outline] Printable version Printer-friendly version -  Choose language   
Software

\(\begingroup\) Beim Lösen von Job Shop Problemen stellen sich manche Instanzen (Beispieldaten) als besonders schwierig heraus. Mit dem Programmpaket "LiSA" kann ich das klassische 10x10 MT10 Problem (gestellt von Muth und Thompson 1963) und auch das 15x15 LA40 Problem (gestellt von Lawrence 1984) lösen. Benutzt wurde dabei Branch&Bound.

[Edit]
[To the bottom]

Einleitung

Bild 1: die Lösung von MT06 mit Funktionswert ff = 55 Definition Unter einem Job Shop Problem mit m Jobs und n Maschinen und m*n Vorgängen versteht man folgendes: jeder der m Jobs besteht aus n Vorgängen die auf den n Maschinen bearbeitet werden müssen. Für m = n ist ein Job eine Permutation der n Vorgänge. Die n Vorgänge eines Jobs müssen in der vorgegebenen Reihenfolge bearbeitet werden. Pro Maschine kann jeweils nur 1 Vorgang zu einer bestimmten Zeit bearbeitet werden. Gesucht ist eine Maschinenbelegung die möglichst wenig Gesamtzeit braucht (minimiere cmax). Bemerkung: im Artikel werden nur quadratische Probleme, also m = n betrachtet. Kritischer Pfad Der kritische Pfad ist der Grund warum die Lösung nicht kürzer ist. Er ist eine lückenlose Abfolge von Vorgängen mit der Gesamtzeit cmax. Es kann mehrere kritische Pfade (Wege) geben. Anmerkung: Job Shop Scheduling ist NP-vollständig und somit für größere Dimensionen - wie 20x20 oder größer - nur schwer exakt lösbar. Selbst bestimmte 10x10 Probleme waren viele Jahre nicht beweisbar optimal lösbar.
[Edit]

Das Programm Paket "LiSA"

Bild 2: der Startbildschirm von "LiSA" LiSA - A Library of Scheduling Algorithms ist ein kostenloses Programmpaket zur Mathematischen Optimierung (Scheduling). Entwickelt wurde es von ca. 25 Leuten die vor allem bei der Fakultat fur Mathematik Otto-von-Guericke Universitat Magdeburg gearbeitet/studiert/promoviert haben. Es existiert ein Handbuch von aktuell 109 Seiten als pdf-Datei. Man kann eigene xml-Problem-Dateien einlesen und mit einer Vielzahl von Algorithmen lösen lassen. An Problemen können gelöst werden: Flow Job, Job Shop, Open Shop und andere Probleme. Als Algorithmen dienen 2 Branch&Bound-Verfahren, Prioritätsregeln, iterative Verfahren wie Simulated Annealing oder Tabu Suche. Auch möglich sind genetische Algorithmen bzw. Ameisenalgorithmen. Download des Programmpakets hier (Jahr 2022): www.math.ovgu.de/Lisa.html Das Handbuch gibt es hier (Jahr 2022): www.math.uni-magdeburg.de/~werner/handbuch.pdf
[Edit]

lösen von MT10 (Muth/Thompson 1963) mittels Branch&Bound

Vorgehensweise: - besorge Instanzdaten vom MT10 - berechne Eingabedaten für "LiSA" mittels lisa.m - Starte "LiSA", öffne mt10cmax.xml (siehe unten) - Starte "Algorithmen" / "Exakte Verfahren" / "Brucker's Job-Shop B&B" - warte 4 Sekunden - speichere ggf. die Lösung \showon Octave File lisa.m \sourceon % function lisa k = 5; if (k == 1) % ff = 7 az_jobs = 3; az_masch = 3; m = [1 3 2 1 2 3 3 2 1]; l = [2 2 1 1 2 2 1 1 4]; end if (k == 4) % MT6, ff = 55 az_jobs = 6; az_masch = 6; 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]; end if (k == 5) % MT10, ff 930 az_jobs = 10; az_masch = 10; m = [1 2 3 4 5 6 7 8 9 10 1 3 5 10 4 2 7 6 ... 8 9 2 1 4 3 9 6 8 7 10 5 2 3 1 5 7 9 ... 8 4 10 6 3 1 2 6 4 5 9 8 10 7 3 2 6 4 ... 9 10 1 7 5 8 2 1 4 3 7 6 10 9 8 5 3 1 ... 2 6 5 7 9 10 8 4 1 2 4 6 3 10 7 8 5 9 ... 2 1 3 7 9 10 6 4 5 8]; l = [29 78 9 36 49 11 62 56 44 21 43 90 75 11 69 28 46 46 ... 72 30 91 85 39 74 90 10 12 89 45 33 81 95 71 99 9 52 ... 85 98 22 43 14 6 22 61 26 69 21 49 72 53 84 2 52 95 ... 48 72 47 65 6 25 46 37 61 13 32 21 32 89 30 55 31 86 ... 46 74 32 88 19 48 36 79 76 69 76 51 85 11 40 89 26 74 ... 85 13 61 7 64 76 47 52 90 45]; end if (k == 6) % JS225, ff waere 1222 az_jobs = 15; az_masch = 15; m = [10 11 5 13 3 15 6 9 7 4 2 8 14 12 1 1 2 12 3 5 10 15 9 14 13 7 4 ... 11 6 8 15 4 2 13 7 6 9 12 8 11 3 14 1 10 5 2 7 8 5 15 11 10 6 12 ... 3 14 9 4 13 1 13 6 10 5 15 14 1 9 12 2 3 8 7 11 4 2 6 3 14 5 15 ... 7 8 10 11 12 1 4 13 9 10 8 7 15 4 14 3 5 13 9 2 11 1 6 12 4 8 5 ... 9 6 3 15 13 12 1 14 11 2 7 10 4 9 7 10 15 2 6 5 14 8 12 13 11 3 1 ... 1 6 8 5 11 13 2 14 7 9 12 10 3 15 4 3 1 7 5 4 6 13 10 15 14 9 8 ... 12 11 2 11 15 5 10 4 2 13 14 7 9 12 8 6 3 1 1 14 4 7 2 15 12 5 11 ... 10 6 9 8 3 13 11 13 14 5 2 4 9 6 10 1 7 8 3 15 12 2 11 7 13 5 9 ... 4 8 14 12 6 10 3 15 1]; l = [65 28 74 33 51 75 73 32 13 81 35 59 38 55 27 64 53 83 33 6 52 72 7 90 21 23 10 ... 39 49 72 73 82 23 62 88 21 65 70 53 81 93 77 61 28 78 12 51 33 15 72 98 94 12 42 ... 24 15 28 6 99 41 97 7 96 15 73 43 32 22 42 94 23 86 78 24 31 72 88 93 13 44 66 ... 63 14 67 17 85 35 68 5 49 15 82 21 53 72 49 99 26 56 45 68 51 8 27 96 54 24 14 ... 38 36 52 55 37 48 93 60 70 23 23 83 12 69 26 23 28 82 33 45 64 15 9 73 59 37 62 ... 87 12 80 50 48 90 72 24 14 71 44 46 15 61 92 54 22 61 46 73 16 6 94 93 67 54 75 ... 32 40 97 92 36 22 9 47 77 79 36 30 98 79 7 55 6 30 49 83 73 82 82 92 73 31 35 ... 54 7 37 72 52 76 98 34 52 26 28 39 80 29 70 43 48 58 45 94 96 70 17 90 67 14 23 ... 21 18 43 84 26 36 93 84 42]; end nn = az_jobs*az_masch; feld = zeros(nn,2); % Start und Ende der Belegung % berechne Eingaben von Lisa. erg = zeros(az_jobs,az_masch); m = reshape(m',az_jobs,az_masch)'; l = reshape(l',az_jobs,az_masch)'; az_jobs; az_masch; % (1) Matrix der Dauer erg = zeros(az_jobs,az_masch); for zeile = 1:az_jobs for spalte = 1:az_masch merk = m(zeile,spalte); erg(zeile,merk) = l(zeile,spalte); end end erg % (2) MO-Matrix erg2 = zeros(az_jobs,az_masch); for zeile = 1:az_jobs for spalte = 1:az_masch for wert = 1:az_masch merk = m(zeile,spalte); if (merk == wert) erg2(zeile,merk) = spalte; break; end end end end erg2 \sourceoff \showoff \showon mt10cmax.xml \sourceon { { 29 78 9 36 49 11 62 56 44 21 } { 43 28 90 69 75 46 46 72 30 11 } { 85 91 74 39 33 10 89 12 90 45 } { 71 81 95 98 99 43 9 85 52 22 } { 6 22 14 26 69 61 53 49 21 72 } { 47 2 84 95 6 52 65 25 48 72 } { 37 46 13 61 55 21 32 30 89 32 } { 86 46 31 79 32 74 88 36 19 48 } { 76 69 85 76 26 51 40 89 74 11 } { 13 85 61 52 90 47 7 45 64 76 } } { { 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 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 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 4 5 6 7 8 9 10 } { 1 6 2 5 3 8 7 9 10 4 } { 2 1 4 3 10 6 8 7 5 9 } { 3 1 2 8 4 10 5 7 6 9 } { 2 3 1 5 6 4 10 8 7 9 } { 7 2 1 4 9 3 8 10 5 6 } { 2 1 4 3 10 6 5 9 8 7 } { 2 3 1 10 5 4 6 9 7 8 } { 1 2 5 3 9 4 7 8 10 6 } { 2 1 3 8 9 7 4 10 5 6 } } \sourceoff \showoff
Bild 3: die Lösung von MT10 mit ff = 930
[Edit]

lösen von LA40 (Lawrence 1984) mittels Branch&Bound

Bild 4: Branch&Bound rechnet, ff aktuell 1238 (reduziert sich im Laufe der Rechnung) Vorgehensweise: - analog zu MT10 - Starte "Algorithmen" / "Exakte Verfahren" / "Brucker's Job-Shop B&B" - warte 2 h 23 Minuten (siehe ein Beispielbild der Berechnung) - wenn die Lösung 1222 da ist, dann lasse hier auch den kritischen Weg anzeigen - auffällig ist, dass der Branch&Bound-Algorithmus nicht schneller wird, wenn man beispielsweise mit der Lösung 1224 (fast optimal; siehe unten) startet \showon la40cmax.xml \sourceon { { 27 35 51 81 74 73 13 59 32 65 28 55 33 38 75 } { 64 53 33 10 6 49 23 72 7 52 39 83 21 90 72 } { 61 23 93 82 78 21 88 53 65 28 81 70 62 77 73 } { 41 12 24 6 15 12 51 33 28 94 98 42 99 15 72 } { 32 94 23 31 15 7 78 86 22 96 24 42 97 43 73 } { 35 72 93 68 44 88 63 14 49 67 17 85 5 13 66 } { 8 68 99 72 26 27 21 82 45 15 51 96 56 49 53 } { 93 23 52 54 14 36 23 24 38 83 70 48 37 60 55 } { 62 82 37 12 45 33 26 15 69 23 59 9 73 64 28 } { 87 72 15 92 50 12 14 80 71 46 48 44 90 24 61 } { 22 97 54 73 46 16 61 75 54 94 40 32 6 67 93 } { 30 77 6 47 22 55 30 7 98 9 92 79 79 36 36 } { 49 82 52 73 31 7 82 72 37 54 35 73 76 83 92 } { 43 28 45 39 26 29 48 58 80 70 98 96 34 52 94 } { 42 70 93 21 14 26 90 18 23 36 17 84 67 43 84 } } { { 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 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 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 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 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 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 1 1 1 } } { { 15 11 5 10 3 7 9 12 8 1 2 14 4 13 6 } { 1 2 4 12 5 14 11 15 8 6 13 3 10 9 7 } { 13 3 11 2 15 6 5 9 7 14 10 8 4 12 1 } { 15 1 10 13 4 8 2 3 12 7 6 9 14 11 5 } { 7 10 11 15 4 2 13 12 8 3 14 9 1 6 5 } { 12 1 3 13 5 2 7 8 15 9 10 11 14 4 6 } { 13 11 7 5 8 14 3 2 10 1 12 15 9 6 4 } { 10 13 6 1 3 5 14 2 4 15 12 9 8 11 7 } { 15 6 14 1 8 7 3 10 2 4 13 11 12 9 5 } { 1 7 13 15 4 2 9 3 10 12 5 11 6 8 14 } { 2 15 1 5 4 6 3 12 11 8 14 13 7 10 9 } { 15 6 14 5 3 13 9 12 10 4 1 11 7 8 2 } { 1 5 14 3 8 11 4 13 12 10 9 7 15 2 6 } { 10 5 13 6 4 8 11 12 7 9 1 15 2 3 14 } { 15 1 13 7 5 11 3 8 6 12 2 10 4 9 14 } } \sourceoff \showoff
Bild 5: die Lösung von LA40 mit ff = 1222; gefunden nach weniger als 2h30 Min Rechnung
Bild 6: der Kritische Pfad/Weg der Lösung 1222 in Rot
[Edit]

Abschluß

Rechenzeiten 1992 und 2022: So zum Vergleich: Wir besaßen 1990 einen 286 er Computer mit 16 MHz Taktfrequenz. Heute(2022) arbeite ich viel an einem Laptop mit 4 GHz Taktfrequenz. Paper: Brucker/Jurisch/Sievers "A branch and bound algorithm for the job-shop scheduling problem" 1992 veröffentlicht Jahr 1992 (Brucker) - MT10 -> ff=930, 1138 Sekunden Rechenzeit - LA40 -> ???, 5 Stück 15x15 Probleme mit Rechenzeiten von 64336 bis 396484 Sekunden (nicht immer Optimum gefunden) Jahr 2022 (ich) - MT10 -> ff = 930, 4 Sekunden Rechenzeit Laptop 4 GHz - LA40 -> ff = 1222, Rechenzeit ca.8580 Sekunden (ca. 2 h 23 Min) Laptop 4 GHz Noch ein Alternativweg zu guten Lösungen von MT10 und LA40: Funktionswerte und Wege zu den Funktionswerten bei Tabu Search: "MT 10" LiSA: Regel 1.LPT(ff=1295) dann 2.Tabu Search 50 Mio Iterationen, 40 Tabuliste, 40 Nachbarn, SC_Trans Nachbarschaft liefert ff = 930 (opt) "LA 40" Regel 1.EDD (ff=1778) 2.Tabu 5 Mio Iter, 40 TL, 40 Nachbarn, CR_Trans liefert ff = 1229 bzw. etwas besser "LA 40" Regel 1.EDD (ff=1778) 2.Tabu 5 Mio Iter, 40 TL, 45 Nachbarn, CR_Trans liefert ff = 1224 (Optimum wäre 1222) Begriffe: Regel (LiSA Handbuch S.20): LPT(default) -> mit größter Bearbeitungszeit (largest processing time first) EDD -> mit kleinstem Fälligkeitstermin (earliest due date first) Nachbarschaften [LiSA Handbuch S.40] CR_TRANS -> (crtitical TRANS) : Auf einer Maschine wird die Reihenfolge der Jobs zwischen zwei kritischen Operationen umgedreht. Fertig! Viele Grüße Ronald
[Edit]
\(\endgroup\)
[Show outline only]
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Write a comment

Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Software :: automatisch eingefügt und unbearbeitet :: NP-Vollständigkeit :: diskrete Optimierung :: Branch&Bound :
Lösen von Job Shop Problemen Teil 2 - mit dem Programmpaket "LiSA" [von Delast  
Beim Lösen von Job Shop Problemen stellen sich manche Instanzen (Beispieldaten) als besonders schwierig heraus. Mit dem Programmpaket "LiSA" kann ich das klassische 10x10 MT10 Problem (gestellt von Muth und Thompson 1963) und auch das 15x15 LA40 Problem (gestellt von Lawrence 1984) lösen. Benut
[Edit]
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]
 


 
 
Aufrufzähler 178
 
Aufrufstatistik des Artikels
Insgesamt 3 externe Seitenaufrufe zwischen 2022.06 und 2023.03 [Anzeigen]
DomainAnzahlProz
https://google.com3100%100 %



[Top of page]



"Mathematik: Lösen von Job Shop Problemen Teil 2 - mit dem Programmpaket "LiSA"" | 0 Comments
The authors of the comments are responsible for the content.

 
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]