Advanced search
Start date
Betweenand

Mathematical models for the irregular strip packing problem

Grant number: 13/14147-3
Support type:Scholarships in Brazil - Master
Effective date (Start): October 01, 2013
Effective date (End): February 28, 2015
Field of knowledge:Engineering - Production Engineering
Principal Investigator:Franklina Maria Bragion de Toledo
Grantee:Marcos Okamura Rodrigues
Home 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. Web of Science Citations: 2.
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 São Carlos.

Please report errors in scientific publications list by writing to: cdi@fapesp.br.