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

Authors: Mohamed N. Kashkoush; Mohamed A. Shalaby; Ehab A. Abdelhafiez

Addresses: Department of Mechanical Design and Production, Cairo University, Giza 12613, Egypt ' Department of Mechanical Design and Production, Cairo University, Giza 12613, Egypt ' Department of Mechanical Design and Production, Cairo University, Giza 12613, Egypt

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.

DOI: 10.1504/IJOR.2012.050147

International Journal of Operational Research, 2012 Vol.15 No.4, pp.391 - 405

Published online: 11 Jan 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article