A Linear Programming Approach to the Cutting Stock Problem—Part II

TLDR

The study extends earlier stock‑cutting methods to address the full‑scale paper trim problem. The authors introduce a faster knapsack algorithm, modify the formulation to limit knife use, balance multiple machines, and handle variable order sizes, and evaluate these changes through experiments on speed, waste, and integer‑programming connections. The developed methods generalize to other cutting problems beyond the paper industry.

Abstract

In this paper, the methods for stock cutting outlined in an earlier paper in this Journal [Opns Res 9, 849–859 (1961)] are extended and adapted to the specific full-scale paper trim problem. The paper describes a new and faster knapsack method, experiments, and formulation changes. The experiments include ones used to evaluate speed-up devices and to explore a connection with integer programming. Other experiments give waste as a function of stock length, examine the effect of multiple stock lengths on waste, and the effect of a cutting knife limitation. The formulation changes discussed are (i) limitation on the number of cutting knives available, (n) balancing of multiple machine usage when orders are being filled from more than one machine, and (m) introduction of a rational objective function when customers' orders are not for fixed amounts, but rather for a range of amounts. The methods developed are also applicable to a variety of cutting problems outside of the paper industry.