Random-Key Optimizer with reinforcement learning for the Capacitated Multi-period Cutting Stock Problem with setup cost

Abstract

This paper introduces a Random-Key Optimizer (RKO) procedure incorporating reinforcement learning to solve the One-Dimensional Multi-Period Cutting Stock Problem (MPCSP) with setup costs and capacity constraints. The MPCSP involves determining cutting plans for each period to meet customer demands, where inventory variables link consecutive periods. The RKO represents solutions as random-key vectors, which are decoded into feasible solutions for the MPCSP through a decoder process. During the optimization process, the RKO dynamically adapts its parameters using reinforcement learning. This framework integrates Biased Random-Key Genetic Algorithm (BRKGA), Particle Swarm Optimization (PSO), and Simulated Annealing (SA), all utilizing a unified decoder function. A novel penalization mechanism is also introduced within the decoder to handle infeasibilities effectively. The proposed RKO is evaluated on benchmark instances from the literature and compared against state-of-the-art methods, including a hybrid column generation heuristic and a dynamic programming-based heuristic. In addition, a new set of large-scale instances is introduced for further evaluation. Computational experiments reveal that the RKO employed by BRKGA consistently outperforms other solution methods in benchmark instances, delivering superior average solution quality. A sensitivity analysis is also conducted, examining the impact of setup costs and production capacity. Moreover, the study includes a comparative analysis of the RKO framework with and without reinforcement learning.