Row and column generation technique for a multistage cutting stock problem

Row and column generation technique for a multistage cutting stock problem

0.00 Avg rating0 Votes
Article ID: iaor2003239
Country: United Kingdom
Volume: 29
Issue: 9
Start Page Number: 1143
End Page Number: 1156
Publication Date: Aug 2002
Journal: Computers and Operations Research
Authors:
Keywords: programming: integer
Abstract:

This multistage cutting stock problem (CSP) generalizes the one-dimensional CSP when a lengthwise cutting process is distributed over two or more successive stages. At every stage of the cutting process incoming rolls are slit into smaller rolls by width. The problem is to minimize total trim loss occurring at all stages of technological process meeting customer demands for finished rolls. We propose a row and column generation technique for solving the multistage one-dimensional CSP. The technique is a generalization of the column generation method suggested by Gilmore and Gomory for solving a classic CSP. The procedure generates only those intermediate rolls (rows) and cutting patterns (columns) that are needed. An auxiliary problem embedded into the frame of the revised simplex algorithm is a non-linear knapsack problem that can be solved efficiently. Computational results prove the overall method is a valuable addition to the tool set for modeling and solving the multistage CSP.

Reviews

Required fields are marked *. Your email address will not be published.