Verfahren für das Packen von Kreisen und Kugeln

Tilli, Thomas GND

Die vorliegende Arbeit beschäftigt sich mit dem Packen von Kreisen in rechteckige Container und von Kugeln in quaderförmige Container. Diese Packprobleme gehören zu der Klasse der Cutting- und Packing-Probleme. Insgesamt werden in dieser Arbeit vier verschiedene Aufgabenstellungen betrachtet: das zweidimensionale Strip-Packing-Problem (2D-SPP) und das beschränkte zweidimensionale Knapsack-Problem (2D-KP) mit Kreisen, sowie das dreidimensionale Strip-Packing-Problem (3D-SPP) und das beschränkte dreidimensionale Knapsack-Problem (3D-KP) mit Kugeln. In dieser Arbeit werden verschiedene zur Lösung der genannten Probleme entwickelte Verfahren vorgestellt und evaluiert: einfache Heuristiken, Greedy-Verfahren, Hill-Climbing und Beam-Search-Verfahren. Die Implementierung der Verfahren erfolgt in Java. Die Verfahren sind parallelisiert und nutzen einen Dual-Quadcore-Rechner effizient aus. Die Verfahren werden mit einer großen Zahl von Benchmark-Instanzen evaluiert und mit bestehenden Verfahren verglichen. Am besten schneidet das entwickelte Beam-Search-Verfahren mit Vorrausschau und fester Beam-Weite ab. Es erzielt ähnliche oder höhere Packungsdichten als bestehende Verfahren bei teilweise sehr viel geringeren Laufzeiten.

Vorschau

Zitieren

Zitierform:

Tilli, Thomas: Verfahren für das Packen von Kreisen und Kugeln. Hagen 2012. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe