Modeling multistage cutting stock problems

Modeling multistage cutting stock problems

0.00 Avg rating0 Votes
Article ID: iaor20031909
Country: Netherlands
Volume: 141
Issue: 2
Start Page Number: 313
End Page Number: 327
Publication Date: Sep 2002
Journal: European Journal of Operational Research
Authors:
Keywords: programming: linear
Abstract:

In multistage cutting stock problems (CSP) the cutting process is distributed over several successive stages. Every stage except the last one produces intermediate products. The list of intermediate products may be given or arbitrary. The goal is to minimize the total amount of material taken out of stock to cut finished products sufficient to meet customer demands. If the intermediate sizes are given, the column generation technique can be applied to multistage cutting problems. If the intermediate sizes are not given then another dimension is added to the problem complexity. We propose a special procedure for this case that dynamically generates both rows (intermediate sizes) and columns (patterns). We refer to this method as row-and-column generation. The method uses an auxiliary problem embedded into the frame of the revised simplex algorithm. It is a non-linear knapsack problem that can be solved efficiently. In contrast to the column generation method the developed technique cannot guarantee the optimal solution. However, the results of computational experiments are very promising and prove that the method is a valuable addition to the set of tools for modeling and solving multistage CSPs.

Reviews

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