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 ge neral two-dimensional guillotine cutting (with many stock entities) an d a particular case called the two-dimensional guillotine cutting (whi ch considers only one stock unit). For the particular problem, we use the graph representation of the problem which is commonly used in arti ficial 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 heu ristic search is based upon a series of one-dimensional knapsack probl ems and the exact algorithm is based on two-dimensional knapsack probl ems. Further, some heuristics are considered, and computational result s are presented on some instances taken from the literature as well as randomly generated instances. Copyright (C) 1997 Published by Elsevie r Science Ltd