Detailansicht
Solving the two-dimensional bin packing problem
Lukas Baumgartner
Art der Arbeit
Diplomarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Betreuer*in
Richard Hartl
DOI
10.25365/thesis.14122
URN
urn:nbn:at:at-ubw:1-29697.01845.639663-6
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Das ”two-dimensional bin packing” Problem mit orientierten Elementen und freiem Schneiden (2BP|O|F) wurde in dieser Arbeit diskutiert. Für dieses Problem müssen ein Set kleiner, rechteckiger Elemente in ein unbegrenztes Set von einheitlichen großen Objekten gepackt werden. Orientiert heißt, dass die Elemente nicht gedreht werden dürfen und freies Schneiden heißt, dass die Elemente überall im großen Objekt platziert werden können, solange sie innerhalb von diesem platziert werden und sich dabei nicht überlappen. Es gibt eine große Anzahl an Variationen für das Problem, wie zum Beispiel eine unterschiedliche Dimensionalität, unterschiedlich große Objekte, unregelmäßig geformte Elemente, rotierbare Elemente oder dass nur Guillotineschnitte vorgenommen werden können. Für diese Arbeit wurde ein neues ILP Modell entwickelt. Weiters wurde eine bereits existierende Heuristik (LGFi) verbessert, indem ein auf Wahrscheinlichkeiten basierender Ansatz verwendet wurde. Die Heuristik besteht aus einem Vorverarbeitungsschritt und einem zweiten Schritt in dem die Elemente gepackt werden. Das Ziel des Vorverarbeitungsschrittes ist es die Elemente zu sortieren und das Ziel des zweiten Schrittes ist es die sortierten Elemente zu packen. Was verändert wurde ist, dass die Elemente nicht mehr auf eine deterministische Weise sortiert werden sondern basierend auf Wahrscheinlichkeiten. Diese verbesserte Heuristik wurde mit Hilfe von drei verschiedenen Ansätzen auf 500 Instanzen, die von der Literatur zur Verfügung gestellt wurden, angewendet. Diese drei sind ein multi-start Ansatz, Beam Search und Variable Neighborhood Search. Alle drei übertreffen die bisher dagewesenen Ansätze, wobei Beam Search die schlechteste ist und der multi-start Ansatz und Variable Neighborhood Search am besten und etwa gleich gut sind. Außerdem wurden drei neue beste Lösungen für die 500 Instanzen gefunden.
Schlagwörter
Schlagwörter
(Deutsch)
Bin Packing Metaheuristik Heuristik Beam Search Variable Neighborhood Search 2DBP
Autor*innen
Lukas Baumgartner
Haupttitel (Englisch)
Solving the two-dimensional bin packing problem
Paralleltitel (Deutsch)
Lösen des zweidimensionalen "Bin Packing" Problems
Publikationsjahr
2011
Umfangsangabe
X, 74 S. : graph. Darst.
Sprache
Englisch
Beurteiler*in
Richard Hartl
Klassifikationen
85 Betriebswirtschaft > 85.35 Fertigung ,
85 Betriebswirtschaft > 85.99 Betriebswirtschaft: Sonstiges
AC Nummer
AC08509156
Utheses ID
12677
Studienkennzahl
UA | 157 | | |