A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem

A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem

0.00 Avg rating0 Votes
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: ,
Keywords: programming: dynamic, heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.