Article ID: | iaor20106143 |
Volume: | 179 |
Issue: | 1 |
Start Page Number: | 297 |
End Page Number: | 315 |
Publication Date: | Sep 2010 |
Journal: | Annals of Operations Research |
Authors: | Morabito Reinaldo, Pureza Vitria |
Keywords: | programming: dynamic, heuristics |
In this paper we present a heuristic method to generate constrained two-dimensional guillotine cutting patterns. This problem appears in different industrial processes of cutting rectangular plates to produce ordered items, such as in the glass, furniture and circuit board business. The method uses a state space relaxation of a dynamic programming formulation of the problem and a state space ascent procedure of subgradient optimization type. We propose the combination of this existing approach with an and/or-graph search and an inner heuristic that turns infeasible solutions provided in each step of the ascent procedure into feasible solutions. Results for benchmark and randomly generated instances indicate that the method's performance is competitive compared to other methods proposed in the literature. One of its advantages is that it often produces a relatively tight upper bound to the optimal value. Moreover, in most cases for which an optimal solution is obtained, it also provides a certificate of optimality.