Abstract: 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. One-dimensional cutting stock (trim loss) problems arise when production items must be physically divided into pieces with a diversity of sizes in one dimension (e.g., when slitting master rolls of paper into narrower width rolls). Such problems occur when there are economies of scale associated with the production of the large master rolls. In general, the objectives in solving such problems are to: (1) minimize trim loss, (2) avoid production over-runs, and/or (3) avoid unnecessary slitter setups. This paper presents a procedure for solving such problems when both the master rolls and customer orders have multiple quality gradations. Solution procedures for problems with these characteristics have not been previously published. The procedure described here is a two-stage heuristic. A sequential, 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 firstquality ('perfect') master rolls is solved with a Received June 1988; revised February 1989 Gilmore-Gomory [1,2] type linear programming algorithm. An important characteristic of the procedure is its robustness. It 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.
An additional difficulty is when both the master rolls and the customer order can have multiple quality gradations REF .
One-dimensional cutting stock decisions for rolls with multiple quality grades
European Journal of Operational Research
Mathematics