Best-first search and dynamic programming methods for cutting problems: The cases of one or more stock plates

Best-first search and dynamic programming methods for cutting problems: The cases of one or more stock plates

0.00 Avg rating0 Votes
Article ID: iaor1999703
Country: United States
Volume: 32
Issue: 1
Start Page Number: 187
End Page Number: 205
Publication Date: Jan 1997
Journal: Computers & Industrial Engineering
Authors: ,
Keywords: programming: dynamic, engineering
Abstract:

The problem of generating guillotine cutting patterns for a number of stock entities with a rectangular form is discussed. We present exact algorithms and heuristics for solving exactly and approximately the general two-dimensional guillotine cutting (with many stock entities) and a particular case called the two-dimensional guillotine cutting (which considers only one stock unit). For the particular problem, we use the graph representation of the problem which is commonly used in artificial intelligence, and also some lower and upper bounds obtained by using the operations research techniques. For the general problem, we show how we can solve it by using dynamic programming methods: the heuristic search is based upon a series of one-dimensional knapsack problems and the exact algorithm is based on two-dimensional knapsack problems. Further, some heuristics are considered, and computational results are presented on some instances taken from the literature as well as randomly generated instances.

Reviews

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