The reel and sheet cutting problem in paper industry

An important problem in paper industry is the sheet production: so-called master reels have to be cut into sheets of paper ordered by customers. In this paper, the combined process of reel and sheet production is analyzed within an industrial context. In particular, the assignment of sheets to reels and of reels to the master reel are modelled. The goal is to minimize the total trim loss (on the master reel and when cutting sheets) as well as to maximize the production speed. The process can be modeled as a two stage cutting problem combining a generalized assignment problem with a one-dimensional cutting stock problem. A heuristic based on column generation techniques is presented.