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

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. Copyright (C) 1997 Published by Elsevier Science Ltd