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

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

0.00 Avg rating0 Votes
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: , ,
Keywords: polyominoes, stock cutting, mixed integer programming
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.

Reviews

Required fields are marked *. Your email address will not be published.