A fast layer-based heuristic for non-guillotine strip packing

In this paper, an orthogonal strip packing problem with rotation of items and without the guillotine packing constraint is considered. A fast heuristic algorithm for the large-scale problems is presented. This heuristic algorithm is mainly based on heuristic strategies inspired by the wall-building rule of bricklayers in daily life. The heuristics is simple and the setting of parameter is not required. Each layer is initialized with either a single item or a bunch of equal-width items. The remaining part of the layer is filled by a bottom-left strategy preferring items which eliminate corners of the current layout. Items can also be placed across several layers. Then, the evaluation rule, which is based on the fitness value for different rectangles to a given position, is able to select an appropriate rectangle to pack. The computational results on a broad range of benchmark problems show that the fast layer-based heuristic algorithm can compete with other latest heuristics and meta-heuristics from the literature in terms of both solution quality and computational time. The fast layer-based heuristic algorithm can compete with the latest published algorithms. In particular, it performs better for large-scale problem instances. © 2010 Elsevier Ltd. All rights reserved.