Article ID: | iaor20126867 |
Volume: | 15 |
Issue: | 4 |
Start Page Number: | 391 |
End Page Number: | 405 |
Publication Date: | Oct 2012 |
Journal: | International Journal of Operational Research |
Authors: | Kashkoush Mohamed N, Shalaby Mohamed A, Abdelhafiez Ehab A |
Keywords: | polyominoes, stock cutting, mixed integer programming |
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.