A local branching-based solution for the multi-period cutting stock problem with tardiness, earliness, and setup costs

Abstract

This paper addresses the Multi-Period Cutting Stock Problem with Due Dates and Setups (MPCSPDDS), an extension of the classical one-dimensional Cutting Stock Problem (CSP). The MPCSPDDS considers the due dates specified in cutting orders’ requests and setups required for transitioning between different cutting patterns. The challenge lies in minimizing tardiness and earliness during production, considering these as detrimental factors. Additionally, the proposed model assumes that a setup is necessary for the cutting machine when switching patterns. The contribution of this paper includes the proposition of an integer mathematical programming model and a matheuristic solution approach for two variants of the MPCSPDDS, employing column generation, a round-up heuristic, and the local branching matheuristic. Computational experiments show that our proposed solution method consistently yields, on average, high-quality feasible solutions compared to employing column generation and solving the problem with the generated columns using the CPLEX solver while maintaining a low computational cost.