A 2-exchange heuristic for nesting problems

• Type: Article in International Scientific Journal
• Date: 2002

Authors

Gomes, AM (Author) Other; Oliveira, JF (Author) FEUP

Journal

Title: European Journal of Operational Research

Vol. 141 No. 2

Pages: 359-370

ISSN: 0377-2217

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 70 Citations

ISI Web of Science

Scopus - 97 Citations

COMPENDEX

Scientific classification

CORDIS: Physical sciences > Mathematics > Applied mathematics > Operations research

FOS: Engineering and technology > Industrial biotechnology

Other information

Authenticus ID: P-000-N3G

DOI: 10.1016/s0377-2217(02)00130-3

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 12