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

Mateus Martin (), Horacio Hideki Yanasse () and Luiz Leduíno Salles-Neto ()
Additional contact information
Mateus Martin: Universidade Federal Fluminense
Horacio Hideki Yanasse: Universidade Federal de São Paulo
Luiz Leduíno Salles-Neto: Universidade Federal de São Paulo

Journal of Combinatorial Optimization, 2022, vol. 44, issue 1, No 27, 557-582

Abstract: 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.

Keywords: Cutting and packing; Cutting stock problem; Setup cost; Integer linear programming; Multi-objective optimization (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00848-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:1:d:10.1007_s10878-022-00848-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00848-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().