A mixed-integer model for two-dimensional polyominoes strip packing and tiling problems

Mohamed N. Kashkoush, Mohamed A. Shalaby and Ehab A. Abdelhafiez

International Journal of Operational Research, 2012, vol. 15, issue 4, 391-405

Abstract: Two-dimensional irregular strip packing problem is one of the common cutting and packing problems, where it is required to assign (cut or pack) a set of 2D irregular-shaped items to a rectangular sheet. The sheet width is fixed, while its length is extendable and has to be minimised. In this paper, a new mixed-integer programming (MIP) model is introduced to optimally solve a special case of the problem, where item shapes are polygons with orthogonal edges, named polyominoes. Polyominoes strip packing may be classified as polyominoes tiling; a problem that can also be handled by the proposed model. Reasonable problem sizes (e.g. 45 polyominoes inside a 10 × 25 sheet) are solvable using an ordinary PC. Larger problem sizes are expected to be solvable when using state-of-the-art computational facilities. The model is also verified via a set of benchmark problems that are collected from the literature and provided optimal solution for all cases.

Keywords: strip packing; tiling; polyominoes; 2D polygons; mixed-integer programming; MIP; modelling; stock cutting. (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=50147 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijores:v:15:y:2012:i:4:p:391-405

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().