Detailansicht
GRASP for the two-dimensional strip packing problem
Daniel Rovenský
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 F. Hartl
Mitbetreuer*in
Andrea Seidl
DOI
10.25365/thesis.63070
URN
urn:nbn:at:at-ubw:1-16298.99812.555053-7
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Stip-Packing-Propleme repräsentieren einen Typ von NP-harten Problemen, welche in den
verschiedensten Industrien auftreten. In dieser Masterarbeit wird der Einsatz von verschiedenen
einfachen Heuristiken, wie Bottom-Left oder Touching Perimeter, für eine komplexere GRASP
Metaheuristik untersucht. In jeder Phase der GRASP Metaheuristik werden dann die Heuristiken mit
der besten Performance genutzt. Nach der Implementierung und Optimierung wird die GRASP
Metaheuristik an den meistgenutzten Instanzen aus der Literatur getestet und mit den besten und
neuesten Metaheuristiken verglichen. Als Fazit kann man feststellen, dass die implementierte GRASP
Metaheuristik erreicht unter Berücksichtigung seiner Simplizität relativ gute Ergebnisse und stellt eine
brauchbare Alternative zur Lösung der Strip-Packing-Problemen dar.
Abstract
(Englisch)
The strip packing problem represents an NP-hard problem with applications in various
industries. This thesis is exploring the employment of different simple heuristics like the Bottom-Left
heuristic or Touching Perimeter heuristic inside of a more complex GRASP metaheuristic setting. The
best performing heuristic is chosen for every phase of the GRASP metaheuristic. The implemented and
optimized GRASP metaheuristic is tested on the instances most commonly used in literature and
compared to some of the best and newest metaheuristic algorithms used for solving this type of
problems. In conclusion the implemented metaheuristic performs reasonably well considering its
simplicity and represents a viable option for solving various strip packing problems.
Schlagwörter
Schlagwörter
(Englisch)
Metaheuristic GRASP Strip packing problem Bottom-Left Touching Perimeter
Schlagwörter
(Deutsch)
Metaheuristik GRASP Strip-Packing-Proplem Bottom-Left Touching Perimeter
Autor*innen
Daniel Rovenský
Haupttitel (Englisch)
GRASP for the two-dimensional strip packing problem
Paralleltitel (Deutsch)
GRASP für das zweidimensionale Strip-Packing-Problem
Publikationsjahr
2020
Umfangsangabe
V, 49 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Richard F. Hartl
Klassifikationen
85 Betriebswirtschaft > 85.32 Beschaffung, Materialwirtschaft ,
85 Betriebswirtschaft > 85.35 Fertigung
AC Nummer
AC16071485
Utheses ID
55852
Studienkennzahl
UA | 066 | 915 | |