An efficient solution method for relaxed variants of the nesting problem

摘要

Given a set of irregular shapes, the strip nesting problem is the problem of packing the shapes within a rectangular strip of material such that the strip length is minimized, or equivalently the utilization of material is maximized. If the packing found is to be repeated, e.g., on a roll of fabric or a coil of metal, then the separation between repeats is going to be a straight line. This constraint can be relaxed by only requiring that the packing produced can be repeated without overlap. Instead of minimizing strip length one minimizes the periodicity of these repeats.

We describe how to extend a previously published solution method (Egeblad, Nielsen & Odgaard 2006) for the nesting problem such that it can also handle the relaxation above. Furthermore, we examine the potential of the relaxed variant of the strip packing problem by making computational experiments on a set of benchmark instances from the garment industry. These experiments show that considerable improvements in utilization can be obtained.