Geleitwort | 6 |
Vorwort | 8 |
Inhaltsverzeichnis | 9 |
Abbildungsverzeichnis | 13 |
Tabellenverzeichnis | 16 |
Abkürzungsverzeichnis | 19 |
Verzeichnis ausgewählter Symbole | 22 |
1 Einleitung | 34 |
1.1 Gegenstand der Arbeit | 34 |
1.2 Aufbau der Arbeit | 36 |
2 Ablaufplanung | 39 |
2.1 Einordnung der Ablaufplanung in den Produktionsprozess | 39 |
2.2 Grundlagen der Ablaufplanung | 43 |
2.2.1 Begri. und Aufgaben der Ablaufplanung | 43 |
2.2.2 De.nitionen und Notationsvereinbarungen | 46 |
2.3 Klassi.kation von Ablaufplanungsproblemen | 53 |
2.3.1 Maschinencharakteristika a | 53 |
2.3.2 Auftragscharakteristika ß | 56 |
2.3.3 Zielkriterien . | 58 |
2.4 Der Losungsb¨ ereich – Arten von Ablaufpl¨anen | 65 |
2.4.1 Fallstudie FS1 | 65 |
2.4.2 Zul¨assige Ablaufpl¨ane | 67 |
2.4.3 Semiaktive Ablaufpl¨ane | 69 |
2.4.4 Aktive Ablaufpl¨ane | 70 |
2.4.5 Unverzogerte¨ Ablaufpl¨ane | 72 |
3 Fallstudie aus der Halbleiterindustrie | 74 |
3.1 Produktionsstufe Montage | 75 |
3.2 Produktionsstufe Endmessung | 77 |
3.3 Maschinenverfugbark¨ eit | 81 |
3.4 Alternative Maschinenfolgen | 84 |
3.5 Nachfrage | 86 |
3.6 Zielsetzung | 89 |
3.7 Zusammenfassung und Anmerkungen | 91 |
4 Job-Shop-Modelle der Ablaufplanung | 98 |
4.1 Das Prinzip des disjunktiven Graphen | 99 |
4.1.1 Allgemein | 99 |
4.1.2 Veranschaulichung mit Hilfe der Fallstudie FS1 | 101 |
4.2 Modellformulierung nach Manne fur¨ das klassische Job-Shop-Problem | 105 |
4.2.1 Herleitung der Modellformulierung | 105 |
4.2.2 Anwendung auf die Fallstudie FS1 | 107 |
4.3 Ein gemischt-ganzzahliges lineares Programm zur Modellierung der Fallstudie aus der Halbleiterindustrie | 109 |
4.3.1 Weitere Notationsvereinbarungen | 109 |
4.3.2 Modellierung der Fallstudie FSH: GGLP-Komplett | 112 |
4.3.3 Erl¨auterungen | 114 |
4.3.4 Fallstudie FS2 | 118 |
5Lösungsverfahren für Job-Shop-Probleme | 122 |
5.1 Anmerkungen zur Komplexit¨at | 122 |
5.2 Ub¨ erblick ub¨ er exakte und heuristische Losungsans¨ ¨atze | 126 |
5.2.1 Exakte Verfahren | 126 |
5.2.2 Heuristische Verfahren | 134 |
5.2.2.1 Ero.n¨ ungsverfahren | 135 |
5.2.2.2 Verbesserungsverfahren/Lokale Suchverfahren | 137 |
5.2.2.3 Weitere Verfahren | 145 |
5.3 Priorit¨atsregelverfahren | 145 |
5.3.1 Einfache Konstruktionsverfahren | 145 |
5.3.2 Priorit¨atregeln | 153 |
5.3.3 Anwendung des Gi.er&Thompson-Verfahrens auf die Fallstudie FS1 | 159 |
5.4 Genetische Algorithmen | 164 |
5.4.1 Hintergrund und Ablauf | 164 |
5.4.2 Konstruktion Genetischer Algorithmen | 169 |
5.4.2.1 Kodierung | 170 |
5.4.2.2 Losungsev¨ aluierung | 172 |
5.4.2.3 Ausgangspopulation | 176 |
5.4.2.4 Selektion | 177 |
5.4.2.5 Crossover | 180 |
5.4.2.6 Mutation | 185 |
5.4.2.7 Ersetzungsschema | 187 |
5.4.2.8 Abbruchkriterium | 188 |
5.4.3 Veranschaulichung an der Fallstudie FS1 | 189 |
6 Zweiphasen-Heuristik fur¨ die Fallstudie aus der Halbleiterindustrie | 194 |
6.1 1. Phase – Auswahl der Maschinenfolgen | 195 |
6.1.1 Ein gemischt-ganzzahliges lineares Programm zur Auswahl der Maschinenfolgen | 195 |
6.1.2 Notationsvereinbarungen | 197 |
6.1.3 Modellierung der Maschinenfolgeauswahl: | 198 |
6.1.4 Erl¨auterungen | 199 |
6.1.5 Fallstudie FS3 | 200 |
6.2 2. Phase – das Priorit¨atsregelverfahren | 204 |
6.2.1 Einleitung | 204 |
6.2.2 Erweiterungen | 207 |
6.2.2.1 Nachlaufzeit | 207 |
6.2.2.2 Rustzeit¨ und Auftragsgruppen | 207 |
6.2.2.3 Maschinen – Stillst¨ande und Anlaufzeit | 208 |
6.2.2.4 Kon.ikt-Begri. | 209 |
6.2.3 Der Ablaufplan-Generator [G&T-ext] | 212 |
6.2.4 Losung¨ der Fallstudie FS3 | 223 |
6.3 2. Phase – der Genetische Algorithmus | 227 |
6.3.1 Problemspezi.sche Ausgestaltung des Genetischen Algorithmus | 228 |
6.3.2 Der Ablaufplan-Generator [Decod-ext] | 230 |
6.3.3 Losung¨ der Fallstudie FS3 | 235 |
7 Evaluation | 238 |
7.1 Bestimmung und Generierung der Daten und Szenarien fur¨ die Simulationsstudie | 238 |
7.1.1 Unver¨anderliche Daten | 239 |
7.1.2 Ver¨anderliche Daten | 239 |
7.1.2.1 Planungshorizont | 239 |
7.1.2.2 Nachfrage | 240 |
7.1.2.3 Liefertermine | 240 |
7.1.2.4 Maschinenstillst¨ande | 241 |
7.1.2.5 Maschinenfolgen | 243 |
7.1.3 Betrachtete Szenarien | 243 |
7.2 Simulationsablauf und -ergebnisse der 1. Phase | 244 |
7.3 Simulationsablauf und -ergebnisse der 2. Phase | 248 |
7.3.1 Allgemeines | 248 |
7.3.2 Priorit¨atsregelverfahren | 251 |
7.3.3 Genetischer Algorithmus | 255 |
7.3.3.1 Populationsgroße¨ | 256 |
7.3.3.2 Anzahl Kinder | 257 |
7.3.3.3 Evolutionsstrategie | 258 |
7.3.3.4 Abbruchkriterium | 259 |
7.3.3.5 Selektion des Mating-Pool | 261 |
7.3.3.6 Crossover | 263 |
7.3.3.7 Mutation | 264 |
7.3.3.8 Zusammenfassung | 266 |
7.4 Ergebnisvergleich der beiden Losungsv¨ erfahren | 268 |
7.4.1 Zielfunktionswert | 268 |
7.4.2 Fertigstellung nach dem Ende des Planungszeitraums | 269 |
7.4.3 Zykluszeit | 270 |
7.4.4 Terminub¨ erschreitung | 270 |
7.4.4.1 Anzahl Terminub¨ erschreitungen | 270 |
7.4.4.2 Hohe¨ Terminub¨ erschreitung | 272 |
7.4.5 Abschlussbemerkungen | 273 |
8 Schlussbetrachtung | 278 |
8.1 Zusammenfassung | 278 |
8.2 Ausblick | 283 |
A Anhang | 285 |
A.1 Weitere Ablaufgraphen und -pl¨ane zu denFallstudien | 285 |
A.1.1 Beispiel f¨ur Unzul¨assigkeit | 285 |
A.1.2 Aktiv | 286 |
A.1.3 Unverz¨ogert | 286 |
A.1.4 Optimal | 287 |
A.1.5 Optimales Gantt-Diagramm von Fallstudie FS3 | 289 |
A.2 Modellformulierung nach Manne f¨ur Fallstudie FS1 | 290 |
A.3 Simulationsergebnisse zur 1. Phase | 291 |
A.4 Simulationsergebnisse zur 2. Phase | 293 |
A.4.1 Simulationsergebnisse zum Priorit¨atsregelverfahren | 293 |
A.4.2 Simulationsergebnisse zum Genetischen Algorithmus | 295 |
Literaturverzeichnis | 299 |