Solving irregular strip packing problems with free rotations using separation lines

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

Authors

Jeinny Peralta (Author) Other; Marina Andretta (Author) Other; José Fernando Oliveira (Author) FEUP

Journal

Title: Pesquisa Operacional

Vol. 38

Pages: 195-214

ISSN: 0101-7438

Publisher: Sociedade Brasileira de Pesquisa Operacional

Indexing

Scopus - 5 Citations

Other information

Authenticus ID: P-00P-GWM

DOI: 10.1590/0101-7438.2018.038.02.0195

Abstract (EN): Solving nesting problems or irregular strip packing problems is to position polygons on a fixed width and unlimited length strip, obeying polygon integrity containment constraints and non-overlapping constraints, in order to minimize the used length of the strip. To ensure non-overlapping, we use separation lines, i.e., straight lines that separate polygons. We present a nonlinear programming model that considers free rotations of the polygons and of the separation lines. This model uses a considerable smaller number of variables than the few other approaches proposed in the literature. We use the nonlinear programming solver IPOPT (an algorithm of interior points type), which is part of COIN-OR. Computational tests were run using established benchmark instances and the results were compared with the ones obtained with other methodologies in the literature that use free rotations. © 2018 Brazilian Operations Research Society.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 20