THE DH KD ALGORITHM - A HYBRID APPROACH FOR UNCONSTRAINED 2-DIMENSIONAL CUTTING PROBLEMS/

We study both weighted and unweighted unconstrained two-dimensional gu illotine cutting problems. We develop a hybrid approach which combines two heuristics from the literature. The first one (DH) uses a tree-se arch procedure introducing two strategies: Depth-first search and Hill -climbing. The second one (KD) is based on a series of one-dimensional Knapsack problems using Dynamic programming techniques. The DH/KD alg orithm starts with a good initial lower bound obtained by using the KD algorithm. At each level of the tree-search, the proposed algorithm u ses also the KD algorithm for constructing new lower bounds and uses a nother one-dimensional knapsack for constructing refinement upper boun ds. The resulting algorithm can be seen as a generalization of the two heuristics and solves large problem instances very well within small computational time. Our algorithm is compared to Morabito et al.'s alg orithm (the unweighted case), and to Beasley's [2] approach (the weigh ted case) on some examples taken from the literature as well as random ly generated instances.