Exact algorithms for unconstrained three-dimensional cutting problems: a comparative study

摘要

In this paper we propose two exact algorithms for solving the three-dimensional cutting (3DC) problem. We study the two cases of the unconstrained 3DC problem: (i) only one large pallet is considered, denoted U_3DC, and (ii) the general version, denoted U_G3DC, in which different large pallets are considered. For both cases of the problem, we consider that there is unlimited quantity of each type of pieces to cut, and that all cuts are of guillotine type. We propose a first exact algorithm for the U_3DC problem. The algorithm is an adaptation of Gilmore and Gomory's approach (Oper. Res. 14 (1966) 1045) initially proposed for solving the unconstrained two-dimensional guillotine cutting problem. We then present a second algorithm for the same problem. This algorithm is mainly based upon a graph search procedure using a depth-first search strategy. This algorithm is a straightforward extension of the two-dimensional guillotine cutting approach proposed in (Eur. J. Oper. Res. 91 (1996) 553). We later show how we can extend the dynamic programming based algorithm for exactly solving the U_G3DC problem. Finally, we undertake an extensive experimental study with a large number of problem instances extracted from the literature and compare the performances of both algorithms. Scope and purpose In many industrial sectors, minimizing wastage is a critical issue. Thus, maximizing material utilization for cutting industries including paper, wood, glass, and metal is a relevant performance measure. This paper studies the unconstrained three-dimensional guillotine cutting problem, and proposes two exact algorithms to solve it. The unconstrained three-dimensional guillotine cutting problem, considered herein, consists of cutting objects of various sizes from large pallets of fixed dimensions. The objects, called pieces, are small rectangular parallelepipeds while the pallets are stock rectangular parallelepipeds. The demand for each type of objects is unlimited. In this paper we first propose two exact algorithms for solving the particular case where only one available large pallet is considered. Next, we show how we can extend the dynamic programming based algorithm for exactly solving the problem with different large pallets.