Two-Dimensional Cutting Problems: Mathematical Formulations and Solution Methods

• Grant number: 16/08039-1
• Support Opportunities: Scholarships in Brazil - Doctorate
• Effective date (Start): June 01, 2016
• Effective date (End): September 30, 2018
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Reinaldo Morabito Neto
• Grantee: Mateus Pereira Martin
• Host Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil
• Associated research grant: 13/07375-0 - CeMEAI - Center for Mathematical Sciences Applied to Industry, AP.CEPID

Abstract

This project addresses the Constrained Two-Dimensional Guillotine Cutting Problems (C2DCP). These problems are about to produce smaller rectangles (items or pieces), from larger rectangles (objects), by using cutting operations that split materials in two rectangles and respect the amount of times that the pieces may appear in the cutting patterns, without restriction on the number of stages. Although the C2DCP is present in some industrial environments, there are no records in the literature of mathematical formulations for this problem. This project proposes the development of mathematical programming models and solution methods for C2DCP. The C2DCP will be analyzed in the context of the following problems: Placement Problem, Cutting Stock Problem and Bin Packing Problem. Three solution strategies are proposed. The first strategy involves the development of a compact formulation for these problems to deal with small item and object sets. The second and third strategies involve larger sets of items and objects from the development of extensive formulations for these problems, in a Column Generation context. The second strategy deals with the development of a mathematical programming model to generate cutting patterns for C2DCP and the third strategy proposes the use of dynamic programming methods to generate these patterns. The development of mathematical models contributes to the research of solution methods to the problem, from the analysis of particular structures that allow the reformulation of the problem through decomposition or relaxation techniques. The robustness of the methods will be evaluated by computational experiments using instances of the literature, which also will be compared to other approaches.

Scientific publications

(8)

(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)

MARTIN, MATEUS; OLIVEIRA, JOSE FERNANDO; SILVA, ELSA; MORABITO, REINALDO; MUNARI, PEDRO. Three-dimensional guillotine cutting problems with constrained patterns: MILP formulations and a bottom-up algorithm. EXPERT SYSTEMS WITH APPLICATIONS, v. 168, APR 15 2021. (13/07375-0, 16/01860-1, 16/08039-1)

MARTIN, MATEUS; BIRGIN, ERNESTO G.; LOBATO, RAFAEL D.; MORABITO, REINALDO; MUNARI, PEDRO. Models for the two-dimensional rectangular single large placement problem with guillotine cuts and constrained pattern. International Transactions in Operational Research, v. 27, n. 2, JULY 2019. (13/07375-0, 16/01860-1, 12/23916-8, 16/08039-1)

MARTIN, MATEUS; MORABITO, REINALDO; MUNARI, PEDRO. Two-stage and one-group two-dimensional guillotine cutting problems with defects: a CP-based algorithm and ILP formulations. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, v. 60, n. 6, p. 20-pg., 2021-02-09. (16/08039-1, 20/00747-2, 13/07375-0, 16/01860-1)

MARTIN, MATEUS; HOKAMA, PEDRO H. D. B.; MORABITO, REINALDO; MUNARI, PEDRO. The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation, a Benders decomposition and a CP-based algorithm. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, v. 58, n. 9, p. 18-pg., 2019-06-20. (16/11082-6, 13/07375-0, 16/01860-1, 16/08039-1, 13/07375-0)

MARTIN, MATEUS; MORABITO, REINALDO; MUNARI, PEDRO. A top-down cutting approach for modeling the constrained two- and three-dimensional guillotine cutting problems. Journal of the Operational Research Society, v. 72, n. 12, p. 2755-2769, DEC 2 2021. (16/01860-1, 13/07375-0, 16/08039-1)

MARTIN, MATEUS; HOKAMA, PEDRO H. D. B.; MORABITO, REINALDO; MUNARI, PEDRO. The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation, a Benders decomposition and a CP-based algorithm. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, JUN 2019. (13/07375-0, 16/11082-6, 16/01860-1, 16/08039-1)

MARTIN, MATEUS; MORABITO, REINALDO; MUNARI, PEDRO. Two-stage and one-group two-dimensional guillotine cutting problems with defects: a CP-based algorithm and ILP formulations. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, FEB 2021. (20/00747-2, 16/08039-1, 16/01860-1, 13/07375-0)

MARTIN, MATEUS; MORABITO, REINALDO; MUNARI, PEDRO. A bottom-up packing approach for modeling the constrained two-dimensional guillotine placement problem. Computers & Operations Research, v. 115, MAR 2020. (13/07375-0, 16/08039-1, 16/01860-1)