Parallel greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid

Given a finite set of spheres of different sizes we study the three-dimensional StripPacking Problem (3D-SPP) as well as the three-dimensional Knapsack Problem (3D-KP).The 3D-SPP asks for a placement of all spheres within a cuboidal strip of fixed width andheight so that the variable length of the cuboidal strip is minimized. The 3D-KP requirespacking of a subset of the spheres in a given cuboid so that the wasted space isminimized. To solve these problems some greedy algorithms were developed whichadapt the algorithms proposed by Huang et al. (2005) to the 3D case with someimportant enhancements.[...]

MoreLess

Year of publication:	2009-08-01
Authors:	Kubach, Timo ; Bortfeldt, Andreas ; Tilli, Thomas ; Gehring, Hermann
Institutions:	Fernuniversität <Hagen> / Fachbereich Wirtschaftswissenschaft
Subject:	Algorithmus \| Parallelisierung \| Habsucht \| greedy method \| Parkettierung \| Packing

freely available

Full text |

More access options

Check Google Scholar

In German libraries (KVK)

I need help

1 Introduction
2 Greedy algorithms for the KP and the SPP with unequal spheres
2.1 The methods B1.0 and B1.5 proposed by Huang et al.
2.2 Adaptation of basic concepts to the 3D case
2.3 Algorithm B1.6_3DKP for the 3D Knapsack Problem
2.4 Algorithm B1.6_3DSPP for the Strip Packing Problem
2.5 Parallelization of the algorithms
3 New benchmark instances
4 Experimental results and analysis
4.1 Results and analysis for the new benchmark instances
4.2 Comparison of methods B1.6_3DSPP and SYS
5 Summary
References

Persistent link: https://www.econbiz.de/10005870648