Detailansicht
New extreme points packing heuristics for the 2 dimensional strip packing problem
Baris Tandogan
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
Karl Franz Dörner
DOI
10.25365/thesis.74847
URN
urn:nbn:at:at-ubw:1-18632.38381.299387-9
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Diese Arbeit konzentriert sich auf Konstruktionsmethoden für die orthogonalen Packungsprobleme, insbesondere das zweidimensionale strip packing Problem. Die Extreme Point basierte Konstruktionsheuristik, die ursprünglich für Bin-Packing-Probleme entwickelt wurde, wird hier für das zweidimensionale strip packing Problem angepasst. Das Ziel dieser Arbeit ist es, die einzigartigen Eigenschaften des Strip-Packing-Problems zu demonstrieren und seine deutliche Abkehr von Lösungsabhängigkeiten von der Artikelreihenfolge im Gegensatz zu ähnlich komplexen Problemen wie Vehicle Routing Problemen aufzuzeigen. Durch Parameteroptimierung und experimentelle Erkenntnisse kann die Studie die Trennung der Lösungsqualität von der Artikelsequenzierung validieren und Möglichkeiten vorschlagen, trotz fester Sequenzen qualitativ hochwertige Lösungen zu erzielen, die für reale Szenarien von hoher Bedeutung sind. Während der Schwerpunkt weiterhin auf zwei Dimensionen liegt, ebnet die Forschung den Weg für mögliche Erweiterungen auf Probleme mit zusätzlichen Dimensionen und Einschränkungen. Die implementierte Extreme Point Heuristic erweist sich als effektiv und generiert wettbewerbsfähige Lösungen, die mit modernsten Methoden vergleichbar sind, steht jedoch bei größeren Instanzen vor Herausforderungen hinsichtlich der Recheneffizienz. Die Schlussfolgerungen heben Engpassmerkmale hervor, die die Leistung des Algorithmus beeinträchtigen, und bieten Hinweise für zukünftige Forschung.
Abstract
(Englisch)
This thesis focuses on construction methods for the Orthogonal Packing Problems, particularly the two-dimensional strip packing problem. The Extreme Point Based Construction Heuristic, originally devised for bin packing problems, is adapted here for the two-dimensional strip packing problem. This thesis aims to demonstrate the unique characteristics of the Strip Packing Problem, showcasing its significant departure from solution dependencies on item sequence, unlike analogous problems such as vehicle routing problems. Through parameter optimization and experimental findings, the study can validate the detachment of solution quality from item sequencing and proposes opportunities to achieve high-quality solutions despite fixed sequences, crucial for real-life scenarios. While the focus remains on two dimensions, the research paves the way for potential extensions to problems involving additional dimensions and constraints. The implemented Extreme Point Heuristic proves itself to be effective, generating competitive solutions comparable to state-of-the-art methods, yet faces challenges in computational efficiency for larger instances. The conclusions highlight bottleneck characteristics hindering the algorithm's performance, offering directions for future research.
Schlagwörter
Schlagwörter
(Deutsch)
Heuristik Kontruktionsmethoden Packing Probleme Extreme Points
Schlagwörter
(Englisch)
heuristics construction methods packing problems extreme points
Autor*innen
Baris Tandogan
Haupttitel (Englisch)
New extreme points packing heuristics for the 2 dimensional strip packing problem
Paralleltitel (Deutsch)
Neue extreme Point Heuristiken für die zweidimensionale Strip Packing Problem
Publikationsjahr
2023
Umfangsangabe
VI, 53 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Karl Franz Dörner
Klassifikation
85 Betriebswirtschaft > 85.99 Betriebswirtschaft. Sonstiges
AC Nummer
AC17012344
Utheses ID
69339
Studienkennzahl
UA | 066 | 915 | |