Comparação de malhas para problemas de corte e empacotamento
Carregando...
Data
2018-02-22
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
This work brings the use of grid of points in the resolution of cutting and packing problems
that consider rectangular shaped items. The grids can be considered for mathematical programming
models and heuristics, and they are independent of the problem. The following
grids that are defined by the literature are considered for this work: canonical dissections
(also known as normal patterns), reduced raster points, useful numbers, corner points, regular
normal patterns, extreme points, and meet-in-the-middle patterns. The objective is to
assess the influence of each grid on the resolution of cutting and packing problems, before
and after applying reduction procedures, as the one related to update the items size. Theoretical
results are obtained from relations of set and size between the grids, showing that
the grid of normal patterns and useful numbers are equivalent and, thus, proving formally
that the grid of reduced raster points ensures an optimal solution (this result has been formally
opened in the literature). In addition, we propose a new procedure to reduce the size
of grids. In order to validate the proposed procedure and evaluate the grids, we perform experiments
over instances from the literature, where it is possible to observe that the grids of
reduced raster points and meet-in-the-middle patterns are the smallest. Experiments were
also conducted in a two-dimensional packing problem that uses an integer linear programming
model to pack the items in points of a grid. The results indicate that using the reduction
procedures it is possible to obtain optimal solutions quicker.
Descrição
Palavras-chave
Problemas de corte e empacotamento, Malha de pontos, Procedimentos de redução, Normal patterns, Reduced raster points, Cutting and packing problems, Grid of points, Reduction procedures, Normal patterns, Reduced raster points
Citação
CUNHA, J. G. A. Comparação de malhas para problemas de corte e empacotamento. 2018. 139 f. Dissertação (Mestrado em Modelagem e Otimização) - Universidade Federal de Goiás, Catalão, 2018.