One-dimensional cutting stock decisions for rolls with multiple quality grades

This paper presents a procedure for solving one-dimensional cutting stock problems when both the master rolls and customer orders have multiple quality gradations. The procedure described here is a two-stage sequential heuristic. An innovative shadow price-based procedure is first used to select slitting patterns for master rolls with variable quality characteristics. Then a residual problem for the available first-quality (‘perfect’) master rolls is solved with a linear programming model. An important characteristic of this approach is its robustness. The procedure can deal effectively with problems of varying size and complexity and can also easily be adapted to changing circumstances with respect to production quality and demand.