Parallel greedy algorithms for packing unequal circles into a strip or a rectangle

Given a finite set of circles of different sizes we study the Strip Packing Problem (SPP) as well as the Knapsack Problem (KP). The SPP asks for a placement of all circles (without overlap) within a rectangular strip of fixed width so that the variable length of the strip is minimized. The KP requires packing of a subset of the circles in a rectangle of fixed dimensions so that the wasted area is minimized. To solve these problems some greedy algorithms were developed that enhance the algorithms proposed by Huang et al. [15] Furthermore, these greedy algorithms were parallelized using a master slave approach and following the subtree-distribution model. The resulting parallel methods were run on a dualcore 64 bit PC uner Linux. For the six instances introduced by Stoyan and Yaskov [18] competitive results in terms of solution quality as well as runtime effort were achieved. In order to stimulate more detailed comparisons of different methods dealing with the problems studied here two sets of 128 instances each for the SPP and for the KP were generated. For this several parameters of the instances such as total number of circles, number of different circle types, radius of smallest and of biggest circle, respectively, were varied in a systematic manner. Results for these new benchmark instances are also reported and analysed.