Pattern-based ILP models for the one-dimensional c... - BV FAPESP
Advanced search
Start date
Betweenand


Pattern-based ILP models for the one-dimensional cutting stock problem with setup cost

Full text
Author(s):
Martin, Mateus ; Yanasse, Horacio Hideki ; Salles-Neto, Luiz Leduino
Total Authors: 3
Document type: Journal article
Source: JOURNAL OF COMBINATORIAL OPTIMIZATION; v. N/A, p. 26-pg., 2022-02-12.
Abstract

The one-dimensional cutting stock problem with setup cost (CSP-S) is a cutting problem that seeks a cutting plan with a minimum number of objects and a minimum number of different patterns. This problem gains relevance in manufacturing settings, where time consuming operations to set up the knives of the cutting machine for the new patterns increases production costs. In this paper, we aim at solving the bi-objective CSP-S that analyzes the trade-offs between the number of objects and the number of patterns. We first derive an upper bound on the maximum frequency of a pattern in the cutting plan. Then, we propose a pattern-based pseudo-polynomial integer linear programming (ILP) formulation for the CSP-S. To obtain the Pareto optimal frontier, this formulation is embedded into a straightforward framework which solves the problem of minimizing the number of objects subject to a limited number of patterns in an iterative manner. Since we are not aware of other approaches in the literature that have solved the bi-objective CSP-S exactly, we derive an ILP formulation based on Harjunkoski et al. (Comput Chem Eng 20:121-126, 1996. https://doi.org/10.1016/0098-1354(96)00031-2) into this framework to provide an alternative exact approach. The results of the computational experiments using a general-purpose ILP solver indicated that the approaches are proper for instances with solutions characterized by a moderate number of objects and a few patterns in the Pareto optimal frontier. (AU)

FAPESP's process: 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings
Grantee:Reinaldo Morabito Neto
Support Opportunities: Research Projects - Thematic Grants
FAPESP's process: 20/00747-2 - New formulations for the minimization open stacks problems and related
Grantee:Mateus Pereira Martin
Support Opportunities: Scholarships in Brazil - Post-Doctoral
FAPESP's process: 13/07375-0 - CeMEAI - Center for Mathematical Sciences Applied to Industry
Grantee:José Alberto Cuminato
Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC