A 2-exchange heuristic for nesting problems

This paper describes a new heuristic for the nesting problem based on a 2-exchange neighbourhood generation strategy. This mechanism guides the search through the solution space consisting of the sequences of pieces and relies on a low-level placement heuristic to actually convert one sequence in a feasible layout. The placement heuristic is based on a bottom-left greedy procedure with the ability to fill holes in the middle of the layout at a later stage. Several variants of the 2-exchange nesting heuristic were implemented and tested with different initial solution ranking criteria, different strategies for selecting the next solution, and different neighbourhood sizes. The computational experiments were based on data sets published in the literature. In most of the cases, the 2-exchange nesting algorithm generated better solutions than the best known solutions. (C) 2002 Elsevier Science B.V. All rights reserved.