Detailansicht
Impact of different levels of solution-representations on the performance of a hybrid genetic algorithm for a dual-resource constrained re-entrant flow shop problem
Philipp Kerl
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Betriebswirtschaft
Betreuer*in
Richard Hartl
Mitbetreuer*in
Yannick Scherr
DOI
10.25365/thesis.80439
URN
urn:nbn:at:at-ubw:1-15783.48867.820794-7
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
In dieser Masterarbeit wird untersucht, welchen Einfluss die Wahl der Lösungsrepräsentation auf die Leistungsfähigkeit hybrider genetischer Algorithmen (HGAs) am Beispiel des Dual Resource Constrained Re-entrant Flexible Flow Shop Problems (DRCRFFSP) hat. Das zugrunde liegende Problem ist durch das reale Siebdruck-Produk-tions¬system motiviert, mit Re-Entrant-Routing, parallelen Maschinen und teilweise flexiblen, qualifizierten Mitarbeitern, welches auf die Minimierung des Makespans abzielt. Ausgehend von einem veröffentlichten Single-Level-HGA mit indirekter Kodierung wird eine neue Multi-Level-Repräsentation entwickelt, die Operationsreihenfolge, Maschinenzuordnung und Mitarbeiterzuordnung in drei aufeinander abgestimmten Chromosomen abbildet. Im Rahmen eines gemeinsamen C++-Frameworks werden vier Varianten implementiert und verglichen: SL-GA, SL-HGA, ML-GA und ML-HGA. Zusätzlich wird eine Random-Crossover-Baseline für die Multi-Level-Variante berücksichtigt. Alle Varianten werden auf einem standardisierten DRCRFFSP-Benchmark getestet, wobei für kleine Instanzen Optimierungsergebnisse aus Constraint Programming (CP) herangezogen werden und für große Instanzen identische Zeitlimits gelten. Auf kleinen Instanzen erzeugt die Single-Level-HGA bessere Lösungen als ihre Multi-Level-Gegenstücke, wobei SL-HGA im Durchschnitt weniger als ein Prozent vom Optimum abweicht. Bei größeren Problemen sind die Multi-Level-Varianten deutlich schneller in der Lösungsfindung, weisen jedoch weiterhin eine spürbare Qualitätslücke gegenüber den Single-Level-Lösungen auf. Für große Instanzen liegen die Multi-Level-Kodierungen typischerweise um etwa 30 % über den Single-Level-Lösungen in Bezug auf den Makespan, sowohl für den Standard-GA als auch für den Hybrid-GA. Insgesamt zeigen die Ergebnisse, dass die Lösungsrepräsentation den stärksten Einfluss auf die HGA-Performance hat, gefolgt von Local Search und der Gestaltung der Operatoren. Bei der Suche nach der besten Qualität der Pläne sind Single-Level HGAs zu bevorzugen. Wo es darauf ankommt, schnell zu einer Lösung zu kommen, sind Multi-Level HGAs eine gute Wahl, auch wenn dadurch die Lösungsqualität leiden muss.
Abstract
(Englisch)
This thesis investigates how solution representation affects the performance of hybrid genetic algorithms (HGAs) for the Dual Resource Constrained Re-entrant Flexible Flow Shop Problem (DRCRFFSP). The problem is motivated by a real screen-printing production system with re-entrant routing, parallel machines and partially flexible, skilled workers, where the objective is to minimize makespan. Building on a published single-level HGA with an indirect encoding, a new multi-level representation is designed that stores operation sequence, machine assignment and worker assignment in three aligned chromosomes. Within a common C++ framework, four variants are implemented and compared: SL-GA, SL-HGA, ML-GA and ML-HGA, Additionally, a random-crossover ML baseline was included. All variants were evaluated on a standard DRCRFFSP benchmark, utilizing optimization results from constraint programming for smaller instances and equal time limits for larger ones. On small instances, the single level HGA produced better solutions than their multi-level counterpart, with SL-HGA being on average less than one percent from the optimal solution. On larger problems, the multi-level versions were much quicker at producing solutions. However, they still had a noticeable quality gap compared to the single level solutions. On large problems, it was common for the multi-level encodings to be approximately 30 percent worse than single-level in terms of makespan, for both standard and hybrid GA. Overall, these studies indicated that how a problem is defined as a representation is by far the most significant influence on HGA performance, and that local search and the choice of operators can provide additional performance advantages. Thus, single-level HGAs are the preferred option if the primary concern is the quality of the schedules generated, while multi-level HGAs will be a better option if there is a need to generate solutions quickly and compromises on solution quality are acceptable.
Schlagwörter
Schlagwörter
(Deutsch)
Genetischer Algorithmus Produktionsplanung Hybrid
Schlagwörter
(Englisch)
Genetic Algorithm Scheduling Flow Shop Hybrid Genetic Algorithm multi-level single-level
Autor*innen
Philipp Kerl
Haupttitel (Englisch)
Impact of different levels of solution-representations on the performance of a hybrid genetic algorithm for a dual-resource constrained re-entrant flow shop problem
Publikationsjahr
2025
Umfangsangabe
72 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Richard Hartl
Klassifikationen
85 Betriebswirtschaft > 85.03 Methoden und Techniken der Betriebswirtschaft ,
85 Betriebswirtschaft > 85.35 Fertigung
AC Nummer
AC17786394
Utheses ID
79107
Studienkennzahl
UA | 066 | 915 | |