HEURISTICS FOR THE ONE-DIMENSIONAL STOCK CUTTING PROBLEM WITH SEQUENCE-DEPENDENT SETUPS

This work investigates solution methods for the One-Dimensional Cutting Stock Problem with sequence-dependent setups (1D-CSP-S), in which the setup cost depends on the sequence of consecutive cutting pattern on the machine. The CSP arises in several industrial contexts, such as in the paper and metal industries. From a practical perspective, exact methods become intractable for large-scale instances, which motivates the use of heuristics. This study presents a classical pattern based model, along with a column generation heuristic. For comparison purposes, two classical CSP heuristics adapted to the problem are considered: one based on the sequential generation of cutting patterns and another based on the first-fit decreasing strategy. The methods are evaluated on benchmark instances, and the column generation approach achieves the best gaps on the instances commonly solved by all methods.