A recursive exact algorithm for weighted two-dimensional cutting

A recursive exact algorithm for weighted two-dimensional cutting

0.00 Avg rating0 Votes
Article ID: iaor1999210
Country: Netherlands
Volume: 91
Issue: 3
Start Page Number: 553
End Page Number: 564
Publication Date: Jun 1996
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: dynamic
Abstract:

Gilmore and Gomory's algorithm is one of the better actually known exact algorithms for solving unconstrained guillotine two-dimensional cutting problems. Herz's algorithm is more effective, but only for the unweighted case. We propose a new exact algorithm adequate for both weighted and unweighted cases, which is more powerful than both algorithms. The algorithm uses dynamic programming procedures and one-dimensional knapsack problem to obtain efficient lower and upper bounds and important optimality criteria which permit a significant branching cut in a recursive tree-search procedure. Recursivity, computational power, adequateness to parallel implementations, and generalization for solving constrained two-dimensional cutting problems, are some important features of the new algorithm.

Reviews

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