Mathematical models for the irregular strip packing problem

• Grant number: 13/14147-3
• Support Opportunities: Scholarships in Brazil - Master
• Start date: October 01, 2013
• End date: February 28, 2015
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Franklina Maria Bragion de Toledo
• Grantee: Marcos Okamura Rodrigues
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil
• Associated research grant: 10/10133-0 - Cutting, packing, lot-sizing and scheduling problems and their integration in industrial and logistics settings, AP.TEM

Abstract

The irregular strip packing problem consists of cutting a set of two-dimensional piecesfrom an object of fixed width using the smallest possible length. Despite its economicimportance for many industrial sectors, few exact studies have been made on this problemdue to its difficulty of resolution. Recently, Toledo et al. (2013) proposed a mixed-integermodel to this problem in which the pieces are placed on a grid. This model has workedsuccessfully proving the optimality for instances up to 21 pieces. However, the model hasa large number of non-overlapping constraints, which grows quickly in accordance with thediscretization resolution and number of distinct pieces. In this work, we propose new math-ematical formulations based on this model in order to reduce the number of constraints.In the first approach, we present two reduced models that have shown to be effective forinstances with few repetitions of pieces. In the second approach, it was proposed a cliquecovering model for the problem. This model achieved a greater or equal performancethan the literature for all instances, getting an optimal solution for instances up to 28 pieces.

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

RODRIGUES, MARCOS OKAMURA; TOLEDO, FRANKLINA M. B.. A clique covering MIP model for the irregular strip packing problem. Computers & Operations Research, v. 87, p. 221-234, NOV 2017. (13/07375-0, 10/10133-0, 14/23900-0, 13/14147-3)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

RODRIGUES, Marcos Okamura. Mathematical models for the irregular packing problem. 2015. Master's Dissertation - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) São Carlos.