Algoritmos heurísticos y exactos para problemas de corte no guillotina en dos dimensiones

Resum

The constrained two-dimensional cutting problem consists of satisfying the demands of small pieces from a set of large stock sheets with the objective of maximizing the total value of the pieces cut. In this work we have studied two particular two-dimensional cutting problems in which both pieces and stock sheets are rectangular and non-guillotine cuts are allowed. The Pallet Loading Problem (PLP) arises whenever identical rectangular boxes have to be packed on a rectangular pallet. Though the problem is initially three-dimensional, practical considerations usually mean that the boxes must be placed orthogonally with respect to the edges of the pallet, and in layers in which the vertical orientation of the boxes is fixed. With these restrictions the problem becomes the two-dimensional problem of packing a large rectangle, pallet, with the maximum number of small identical rectangles, boxes. The problem has many practical applications in distribution and logistics. We have developed a branch and cut algorithm for that problem. The 0-1 formulation proposed by Beasley for cutting problems is adapted to the problem, adding new constraints and new procedures for variable reduction. We then take advantage of the relationship between this problem and the maximum independent set problem to use the partial linear description of its associated polyhedron. Finally, we exploit the specific structure of our problem to define the solution graph and to develop efficient separation procedures. We present computational results for the complete sets Cover I (up to 50 boxes) and Cover II (up to 100 boxes) which .had not been previously solved. In a second phase, we have developed a heuristic algorithm, based on Tabu Search, that solves efficiently problems with up to 150 boxes. In the second problem studied several types of pieces can be cut from the large stock rectangle. For this problem we have developed a greedy randomized adaptive search procedure (GRASP). We investigate several strategies for the constructive and improvement phases and several choices for critical search parameters. We perform extensive computational experiments with well known instances previously reported, which show that our algorithm improves the best known results in terms of quality and computing time.