The one‐dimensional cutting stock problem with sequence‐dependent setups

Abstract

The cutting stock problem (CSP) is a classic operations research problem with several applications in real‐world scenarios. It involves cutting large objects into smaller items to satisfy customer demands, minimizing the number of cut objects. Auxiliary objectives often arise when solving the CSP, with a common one being the minimization of setups. This objective becomes particularly challenging in the presence of sequence‐dependent operations, where the setup required for a cutting pattern depends on the previously selected one. This paper proposes a novel assignment‐based formulation for the CSP that incorporates sequence‐dependent setups and minimizes the total number of different cutting patterns. To efficiently solve this problem, we introduce a metaheuristic procedure based on the random‐key optimizer (RKO) framework. Within this approach, a decoder is developed to simultaneously select cutting patterns, determine their frequencies, and sequence them. For the comparative analysis, we implemented two benchmark CSP heuristics, namely the sequential heuristic procedure and first‐fit heuristic, as well as the standard pattern‐based approach, including the mathematical model and the derived column‐generation heuristic. We conducted computational experiments to analyze the impact of minimizing both the sequence‐dependent setups and the number of different cutting patterns. The results were evaluated on benchmark instances and indicate that RKO yields higher‐quality solutions within reasonable computational times for larger instances, obtaining most of the best‐known solutions.