Guillotineable bin packing: A genetic approach

For a constrained, two-dimensional Bin Packing Problem this paper introduces a sequential and a parallel genetic algorithm. A guillotine constraint is directly reflected by the encoding mechanism and thus is ensured at any stage of the algorithm. As an enlargement, the concept of meta-rectangles is proposed and incorporated into the algorithm. Each meta-rectangle temporarily fixes (retangular) hyperplanes of existing solutions. By this the hierarchical structure of guillotineable packing schemes is exploited to reduce the problem's complexity without affecting the quality of the generated solutions. The presented algorithm is able to generate almost optimal packing schemes and even in its sequential version the algorithm empirically is proven to be superior to different approaches such as random search or simulated annealing.