Algorithmic Advances for 1.5-Dimensional Two-Stage Cutting Stock Problem
Open Access
- 27 December 2024
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 18 (1) , 3
Abstract
The Cutting Stock Problem (CSP) is an optimization challenge that involves dividing large objects into smaller components while considering various managerial objectives. The problem’s complexity can differ based on factors such as object dimensionality, the number of cutting stages required, and any technological constraints. The demand for coils of varying sizes and quantities necessitates intermediate splitting and slitting stages to produce the finished rolls. Additionally, relationships between orders are affected by dimensional variations at each stage of processing. This specific variant of the problem is known as the One-and-a-Half Dimensional Two-Stage Cutting Stock Problem (1.5-D TSCSP). To address the 1.5-D TSCSP, two algorithmic approaches were developed: the Generate-and-Solve (G&S) method and a hybrid Row-and-Column Generation (R&CG) approach. Both aim to minimize total trim loss while navigating the complexities of the problem. Inspired by existing problems in the literature for simpler versions of the problem, a set of randomly generated test cases was prepared, as detailed in this paper. An implementation of the two approaches was used to obtain solutions for the generated test campaign. The simpler G&S approach demonstrated superior performance in solving smaller instances of the problem, while the R&CG approach exhibited greater efficiency and provided superior solutions for larger instances.Keywords
All Related Versions
Funding Information
- Regione Puglia (B25H24000520009, B89J23001430005)
- Ministero delle imprese e del made in Italy (B25H24000520009, B89J23001430005)
- Ministero delle imprese e del made in Italy (B25H24000520009, B89J23001430005)
This publication has 25 references indexed in Scilit:
- Two-dimensional skiving and cutting stock problem with setup cost based on column-and-row generationEuropean Journal of Operational Research, 2020
- Algorithms for the one-dimensional two-stage cutting stock problemEuropean Journal of Operational Research, 2018
- Benders decomposition and column-and-row generation for solving large-scale linear programs with column-dependent-rowsEuropean Journal of Operational Research, 2018
- Solving real-world cutting stock-problems in the paper industry: Mathematical approaches, experience and challengesEuropean Journal of Operational Research, 2014
- Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rowsMathematical Programming, 2012
- Accelerating column generation for variable sized bin-packing problemsEuropean Journal of Operational Research, 2007
- An improved typology of cutting and packing problemsEuropean Journal of Operational Research, 2007
- Solving binary cutting stock problems by column generation and branch-and-boundComputational Optimization and Applications, 1994
- A typology of cutting and packing problemsEuropean Journal of Operational Research, 1990
- Trim loss and related problemsOmega, 1985