Mathematik: Lösen von Job Shop Problemen Released by matroid on Fr. 26. April 2019 08:48:04 [Statistics] Written by Delastelle - 636 x read [Outline] Printer-friendly version -  Choose languageDE EN   \(\begingroup\) Eine Problemstellung der diskreten Optimierung sind Job Shop Probleme. Im Artikel werden mehrere Programme vorgestellt, die gute Lösungen erzeugen. Gelöst wird unter anderem das klassische Muth-Thompson 10x10 Problem (mt10) von 1963 dessen Lösung 930 erst 1989 mittels Branch & Bound verifiziert wurde. [Edit] [To the bottom] Einleitung 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 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. [Edit] Probleme Problem 1 Bild: eine Lösung von "JS9" mit ff = 7. Mit X ist ein kritischer Pfad bezeichnet. Ein sogenanntes Gantt-Diagramm. \sourceon Problem 1 "JS9.txt" Maschinen = [ 1 3 2 ... Job 1 -> rot 1 2 3 ... Job 2 -> blau 3 2 1]; Job 3 -> grün Dauer = [ 2 2 1 ... Job 1 -> rot 1 2 2 ... Job 2 -> blau 1 1 4]; Job 3 -> grün \sourceoff Eine Belegung mit Lösung 7 ist folgende: Belegung2 = [1 7 8 4 5 2 9 3 6]; oder auf die Jobs bezogen: Belegung = [1 3 3 2 2 1 3 1 2]; Problem 2 Bild: eine Lösung von "JS25" mit ff = 17. Mit X ist ein kritischer Pfad bezeichnet. \sourceon Problem 2 "JS25.txt" Maschinen = [ 0 1 2 3 4 ... 1 0 3 2 4 ... 0 4 1 2 3 ... 2 3 1 0 4 ... 3 4 1 2 0]; Dauer = [ 1 3 2 1 4 ... 3 3 4 2 1 ... 5 1 2 1 3 ... 2 1 2 3 1 ... 4 3 1 5 1]; \sourceoff belegung2 = [6 16 1 21 11 22 17 2 3 4 12 7 23 18 5 19 24 13 8 25 20 14 9 15 10]; ist eine Lösung mit ff = 17. Problem 3 Bild: eine Lösung von "MT06" mit ff = 55. Mit X ist ein kritischer Pfad bezeichnet. \sourceon Problem 3 "MT06.txt" Maschinen = [ 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]; Dauer = [ 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]; \sourceoff belegung2 = [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]; ist eine Lösung mit ff = 55. Bild: eine Lösung von "MT06" oder "FT06" aus der Literatur(André Henning "Praktische Job-Shop Scheduling-Probleme"). Der kritische Pfad ist rot eingetragen. Die Probleme 1 bis 3 werden mittels Lokaler Suche in weniger als 1 Sekunde gelöst. Auch Branch & Bound benötigt nur 1 Sekunde für diese Probleme. Problem 4 Das Problem 4 ist das klassische MT10-Problem mit Dimension 10x10. Die Problemdaten findet man beispielsweise in dem File "mt10.prb". Problem 5 Das Problem 5 ist das LA40-Problem mit Dimension 15x15. Die Problemdaten findet man beispielsweise in dem File "la40.prb". [Edit] ein einfaches Programm mit Lokaler Suche Hier ist ein einfaches Verfahren zum Lösen von kleinen bis mittleren Job Shop Problemen beschrieben. Es ist für quadratische Probleme bis 15x15 gedacht. Nachbarschaft Tausch-Nachbarschaft(shift-shift) mit rechtem Nachbar, falls (a) Nachbarn gehören zu verschiedenen Jobs (b) mindestens 1 Nachbar auf Kritischem Pfad Hinweis: für sehr kleine Probleme wie 3x3, 5x5 oder 6x6 ist (b) nicht notwendig. Verfahren Lokale Suche mit sidesteps \sourceon Pseudocode - nn := jobs*maschinen - bilde eine Zufallspermutation(perm) mit dimension (nn-1) - berechne zeit := cmax und kweg ("bilde plan") - Sidesteps := 0 - ende := 0 oder false - while (not ende) do - for i = 1 to nn-1 - pos1 = perm(i) - pos2 = pos1 + 1 - tausche Vorgänge pos1 und pos2 aus falls: (a) Nachbarn gehören zu verschiedenen Jobs (b) mindestens 1 Nachbar auf Kritischem Pfad berechne NeueZeit := cmax und kweg - falls NeueZeit schlechter als alte Zeit Tausch rückgängig machen - falls NeueZeit = zeit sidesteps := sidesteps + 1 - falls NeueZeit besser als alte Zeit speichere neue Lösung mit NeueZeit, sidesteps := 0 - falls Sidesteps > Grenze ende := 1 oder True - end for - end while \sourceoff Beispiel: Problem 4 Bild: die Lösung von mt10 - dem Muth-Thompson-Problem von 1963. Gefunden mittels Lokaler Suche und einer Rechenzeit von weniger als 3600 Sekunden. Mit X ist ein kritischer Pfad bezeichnet. Das Bild eignet sich als Poster gedruckt als Weihnachtsgeschenk für Mathematiker mit Fachrichtung diskrete Optimierung. belegung2 = [11 31 51 32 71 81 52 41 61 1 91 62 53 12 33 34 54 42 ... 82 55 92 35 43 63 13 44 56 93 64 36 83 21 14 84 72 65 ... 45 73 57 94 46 66 67 85 37 74 58 22 86 2 59 23 75 95 ... 47 87 60 48 76 3 4 24 15 68 5 25 88 96 6 97 38 26 ... 16 49 98 69 77 7 17 89 27 70 78 8 9 28 39 79 90 29 ... 18 99 19 30 40 100 10 20 80 50]; ist die im Bild gezeigte Lösung Beispiel: Problem 5 Bild: eine gefundene Lösung von la40 - einem 15x15 Problem. Ich habe die Lösung 1228 mittels Lokaler Suche gefunden. Die beste Lösung ist 1222 - gefunden mittels Branch & Bound. Mit X ist ein kritischer Pfad bezeichnet. belegung2 = [106 136 166 61 62 181 137 46 47 121 107 108 31 182 48 91 211 49 109 32 1 212 2 76 110 167 16 ... 77 168 196 3 33 92 151 17 213 122 111 34 50 123 169 197 63 112 93 138 170 94 78 64 4 183 198 ... 171 139 199 124 125 65 5 79 113 95 18 200 35 96 19 51 97 66 80 152 153 36 214 37 215 154 184 ... 216 172 114 201 20 126 217 52 202 218 53 67 127 219 38 54 115 21 220 185 128 203 173 204 81 155 68 ... 140 129 82 69 174 175 98 156 39 141 55 157 6 142 158 7 130 70 83 116 84 143 131 8 205 186 40 ... 206 187 221 99 100 85 207 22 176 188 9 101 41 132 189 71 222 10 208 56 57 190 133 42 86 58 159 ... 191 144 59 145 160 223 11 23 87 102 72 117 209 134 177 103 161 43 60 146 88 12 118 24 192 162 25 ... 135 147 44 178 148 210 26 27 73 119 179 149 104 193 28 163 89 45 13 164 74 90 150 75 194 14 165 ... 224 180 225 195 120 29 105 15 30]; ist die im Bild gezeigte Lösung. [Edit] Lekin Scheduler Download bei: web-static.stern.nyu.edu/om/software/lekin/ kostenloses Lösen bis ca. 10x10 Probleme Lösungsverfahren: - Regel (Heuristiken) / Rechenzeit ca. 1 Sekunde - Shift-Bottleneck-Heuristik / Rechenzeit wenige Sekunden - Lokale Suche / Rechenzeit z.B. 60 Sekunden oder mehr Für das MT10 Beispiel findet das Programm nach weniger als 3600 Sekunden die Optimallösung von 930. Berechnet mit Lokaler Suche. Siehe Bild. [Edit] Branch&Bound-Algorithmus Mehrere Programme zum Lösen von Job Shop Problemen findet sich hier: www.math.uwaterloo.ca/~bico/jobshop/ Das Programm dumbo.c ist dabei ein Branch & Bound Algorithmus. Er untersucht systematisch alle möglichen Lösungen und findet die beste. MT 10 lösen (1) Download files code.tar.gz und prob.tar.gz von www.math.uwaterloo.ca/~bico/jobshop/ (2) Entpacke files (zip-Files) (3) trage in makefile den C-Compiler ein: bei mir CC=mingw32-gcc (4) make ausführen (5) Dumbo.exe mit MT 10 Beispiel und Schranke 930 ausführen: dumbo -0 mt10.prb 930 (6) über Lösung freuen: \sourceon dumbo.exe Ausgaben head times: 119 445 523 532 568 640 651 721 792 893 76 637 224 568 355 759 713 813 885 474 408 308 532 493 893 699 759 709 609 848 185 0 84 637 256 805 355 416 364 766 269 286 210 370 430 308 848 530 499 593 361 84 0 138 499 86 420 505 233 281 148 86 375 233 698 421 388 668 520 442 275 399 179 813 519 445 557 777 699 718 0 217 421 294 668 370 517 579 718 506 256 132 314 735 787 593 375 885 416 517 8041 (930) killed Node 8042: value = 930 8042 nodes evaluated, optimal solution = 930 \sourceoff Für die weitere Verwendung der Ausgaben kann man noch jede Zeile sortieren. gerechnete Benchmarks Bild: Ein besonders leichtes 10x10 Problem la17 mit ff = 784 und einer Rechenzeit von weniger als 1 Sekunde. Mit X ist ein kritischer Pfad bezeichnet. \array(Problem,Dimension,bound,ff,Nodes,Zeit(Sekunden);abz5,10x10,9999,1234,79476,?;abz5,10x10,1234,1234,5910,23;abz6,10x10,943,943,532,2;la16,10x10,945,945,3189,10;la17,10x10,784,784,20,1;la18,10x10,848,848,109,1;la19,10x10,842,842,1024,4;la20,10x10,902,902,7164,25;mt06,6x6,9999,55,148,1;mt06,6x6,55,55,10,1;mt10,10x10,9999,930,108408,510;mt10,10x10,930,930,7473,30;orb1,10x10,9999,1059,615738,7260;orb1,10x10,1059,1059,51817,183;orb2,10x10,9999,888,49521,?;orb2,10x10,888,888,3497,12;orb3,10x10,9999,1005,1891246,?;orb3,10x10,1005,1005,182861,741;orb4,10x10,1005,1005,18979,80;orb5,10x10,887,887,215758,730;orb6,10x10,1010,1010,12436,51;orb7,10x10,397,397,4340,16;orb8,10x10,899,899,575,3;orb9,10x10,934,934,3194,14;orb10,10x10,944,944,9318,31) Die Rechenzeiten beziehen sich auf einen AMD 3 GHz Computer. Bild: Ein besonders schweres 10x10 Problem orb3 mit ff = 1005 und langer Rechenzeit. Mit X ist ein kritischer Pfad bezeichnet. Einfluß von bound (Schranke) Einfluß von bound (Schranke) auf die Anzahl der untersuchten Lösungen (Nodes) für das Programm dumbo.c. Gerechnet wurde das Problem mt10. bound = 929 / 6931 Nodes, keine Lösung bound = 930 / 7473 Nodes, Lösung bound = 931 / 8042 bound = 932 / 8513 bound = 933 / 9118 bound = 934 / 9778 bound = 935 / 10519 bound = 936 / 11261 bound = 937 / 12270 bound = 938 / 13049 bound = 939 / 13925 bound = 940 / 14857 bound = 941 / 15705 bound = 942 / 16497 bound = 943 / 17508 bound = 944 / 18480 bound = 945 / 19511 bound = 946 / 20570 bound = 947 / 21743 bound = 948 / 22881 bound = 949 / 24051 bound = 950 / 25497 bound = 951 / 26826 bound = 952 / 28031 bound = 953 / 29559 bound = 954 / 30676 bound = 955 / 31943 bound = 956 / 33246 bound = 957 / 34524 bound = 958 / 36057 bound = 959 / 37348 bound = 960 / 38615 Es zeigt sich, dass ein niedriger Wert für bound die Rechenzeit (berechnete Nodes) stark verkürzt. Größere Probleme als 15x15 sollte man besser nicht mit dem hier verwendenten Branch & Bound-Algorithmus rechnen - es sei denn man hat Jahre Zeit. [Edit] Abschluß In meinem Notizbuch findet man obiges Programm zur Lokales Suche in Fortran und die Octave-Programme "gantt.m" und "dumbo.m" zur Anzeige von Lösungen. Des weiteren habe ich gespiegelt die Quelltexte zu den C-Programmen (u.a.dumbo.c) und die prb-Problemfiles im Notizbuch. Für schnellere heuristische Lösungsmethoden (z.B. Lokale Suche mit Tabu-Suche) wird ein Blick in die Literatur empfohlen. Genug für heute! Viele Grüße Ronald [Edit] \(\endgroup\) [Show outline only] Get link to this article   Printer-friendly version -  Choose languageDE EN     Comments   Für diesen Artikel gibt es keine pdf-Datei Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen: : Optimierung :: Software :: Diskrete Optimierung :: NP-Vollständigkeit : Lösen von Job Shop Problemen [von Delastelle]   Eine Problemstellung der diskreten Optimierung sind Job Shop Probleme. Im Artikel werden mehrere Programme vorgestellt, die gute Lösungen erzeugen. Gelöst wird unter anderem das klassische Muth-Thompson 10x10 Problem (mt10) von 1963 dessen Lösung 930 erst 1989 mittels Branch & Bound verifizier [Edit] [Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

Aufrufzähler 636   Aufrufstatistik des Artikels Insgesamt 111 externe Seitenaufrufe zwischen 2020.06 und 2023.03 [Anzeigen] Domain Anzahl Proz https://google.com 73 65.8% https://google.de 32 28.8% https://www.startpage.com 2 1.8% https://yandex.ru 2 1.8% https://www.ecosia.org 1 0.9% https://duckduckgo.com 1 0.9% Häufige Aufrufer in früheren Monaten Insgesamt 102 häufige Aufrufer [Anzeigen] Datum Aufrufer-URL 2020-2023 (70x) https://google.com/ 2020-2022 (23x) https://google.de/ 2020-2021 (9x) https://google.de [Top of page]

"Mathematik: Lösen von Job Shop Problemen" | 1 Comment

The authors of the comments are responsible for the content.

Re: Lösen von Job Shop Problemen von: Delastelle am: Mi. 08. Dezember 2021 00:12:38

\(\begingroup\)Hallo, mein Fortran Programm zur Lokalen Suche funktioniert relativ gut. Es hat aber auch Ungenauigkeiten in der Programmierung enthalten: - der kritische Weg kann sich ändern falls eine schlechtere Lösung gefunden wird - falls ein Plan mit schlechterer Zeit gefunden wird, wird die Belegung zwar zurückgesetzt nicht aber die Zeit (so kann die Zeitschranke zwischendurch angehoben werden) Aber auch mit den 2 Einschränkungen arbeitet das Programm besser als andere Programm-Versuche von mir. Viele Grüße Ronald Edit: 1/2022 Der kritische Pfad wird bei den verwendeten Programmen nicht immer völlig korrekt berechnet.\(\endgroup\)