Two-dimensional cutting and packing problems with tetris-like items

• Grant number: 18/11877-4
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Effective date (Start): November 01, 2018
• Effective date (End): August 31, 2019
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Leonardo Junqueira
• Grantee: Artur Gil de Vasconcellos
• Host Institution: Escola Politécnica (EP). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings, AP.TEM

Abstract

This research project addresses variants of two-dimensional cutting and packing problems involving tetris-like items. In these problems, the items have shapes of tetrominoes and must be arranged without overlapping and completely inside a rectangular plate. The objective may be either to maximize the occupied area of the plate or to minimize one of the dimensions of the plate. Some real applications of these problems may include the cutting of fabric and leather, the stamping of metal sheets, the cutting of ceramic coating, the design of printed circuit boards and the layout of magazines, newspapers and internet pages. They consist in hard combinatorial optimization problems, and, to our knowledge, there are no studies in the literature that addressed these problems and that proposed mixed integer linear programming models to describe them. In this research project, we aim to develop mathematical programming models based on mixed integer linear programming to describe these problems, to implement them using modeling languages and optimization solvers, and to perform computational experiments with instances randomly generated and obtained from the available literature.