What question did this study set out to answer?

This research examines how solution representation affects hybrid genetic algorithm performance in factory scheduling.

February 26, 20260 citationsOpen Access

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

Key Points

This research examines how solution representation affects hybrid genetic algorithm performance in factory scheduling.
Developed Single-Level and Multi-Level representations for scheduling problems.
Implemented four algorithm variants: SL-GA, SL-HGA, ML-GA, ML-HGA in a C++ framework.
Conducted tests on standardized benchmarks using constraint programming for small instances.
Single-Level HGAs performed better on smaller problems, deviating less than 1% from optimal solutions.
Multi-Level variants were faster for large instances but had about 30% longer makespan than Single-Level HGAs.
Solution representation significantly impacts hybrid genetic algorithm performance, followed by local search configurations.

Abstract

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.

AIに質問

Bookmark

View Full Paper