An LP-based approach to a two-stage cutting stock problem

This paper describes a linear programming model for a two-stage cutting stock problem that arises in make-to-order steel company. For technological reasons, there are two different cutting operations. Between the cutting operations, the intermediate rolls are processed to obtain the required characteristics. The minimization of the trim loss and the reduction of the number of set-ups are primary concerns in cutting stock problems. In this case it is also important to minimize the number of intermediate rolls, in order to reduce the processing work. These objectives may be conflicting and a balance may be necessary. We present a simplified LP model, which is solved by a column generation technique. The subproblems are relatively large knapsack problems. Computational results for a microcomputer are presented.