A combinatorial algorithm for the constrained k-staged guillotine cutting problem

• Grant number: 24/20161-3
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: February 01, 2025
• End date: January 31, 2026
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Mateus Pereira Martin
• Grantee: Vitor Ferrari Henriques
• Host Institution: Centro de Ciências em Gestão e Tecnologia (CCGT). Universidade Federal de São Carlos (UFSCAR). Campus de Sorocaba. Sorocaba , SP, Brazil
• Associated research grant: 22/05803-3 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings, AP.TEM

Abstract

We address the constrained k-staged guillotine cutting problem (CGCP-k), which arises in various manufacturing systems, such as the cutting of wood panels, glass, and steel blocks. The objective of the CGCP-k is to maximize the total value of items cut from a single object, while meeting two fundamental requirements: the technological constraint of k-stage orthogonal guillotine cutting, where cuts run from edge to edge and are parallel to the object's borders, and the production constraint, which limits the quantity of each item type to avoid overproduction. A guillotine stage is defined as a sequence of cuts made in the same direction.This project focuses on bidimensional (sheet cutting) and tridimensional (block cutting) guillotine cutting problems, considering cutting patterns with up to k stages, where k is a positive integer. We propose to adapt the combinatorial algorithm by Wang (1983), originally developed for the unrestricted-stage version of CGCP, to accommodate the constraints of up to k stages. Additionally, we aim to assess the trade-off between cutting solution quality and the number of guillotine stages.The proposed approaches will be validated through computational experiments, using case studies based on instances from the literature and, potentially, data from companies in the state of São Paulo.