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 Strip Packing Problem (3D-SPP) as well as the thre e-dimensional Knapsack Problem (3D-KP). The 3D-SPP asks for a placement of all sphere s within a cuboidal strip of fixed width and height so that the variable length of the c uboidal strip is minimized. The 3D-KP requires packing of a subset of the spheres in a given cuboid so that the wasted space is minimized. To solve these problems some greedy algorithms were developed which adapt the algorithms proposed by Huang et al. (2005) to the 3D case with some important enhancements. Furthermore, the new greedy algorithms were parallelized using a master slave approach. The resulti ng parallel methods were tested using the instances introduced by Stoyan et al. (2003 ). Additionally, two sets of 288 instances each for the 3D-SPP and for the 3D-KP were generated and results for these new instances are also reported.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten