Nesta tese abordamos o problema de empacotamento em faixas bidimensional em níveis - 2LSP. O 2LSP é um problema de otimização combinatória que, no que diz respeito a modelagem, tem recebido pouca atenção por parte da comunidade científica. Atualmente, o modelo mais competitivo para este problema, até onde sabemos, é o proposto por Lodi et al. em 2004, onde é acrescentado ao problema a restrição de que os itens devem ser alocados formando níveis. Em 2015, um modelo de fluxo para tratar o problema foi apresentado por Mehdi Mrad. A literatura apresenta alguns modelos matemáticos que, embora não seja especificamente para este problema, são modelos eficientes e podem ser adaptados para o 2LSP. Neste trabalho, desenvolvemos novos modelos para o problema, adaptando três modelos de programação linear inteira mista da literatura. Mais ainda, comparamos o desempenho computacional destes novos modelos com os modelos de Lodi et al. e de Mehdi Mrad, usando instâncias clássicas da literatura. Os resultados computacionais mostram que uma das novas formulações matemáticas supera os demais modelos em relação ao número de soluções ótimas. Para finalizar, apresentamos uma aplicação prática com a finalidade de desenvolver uma ferramenta para a geração automática dos planogramas utilizados para a montagem de gôndulas de supermercados. Para a aplicação, apresentamos um modelo de programação inteira mista preliminar que pode ser aplicado para tratar aplicações reais. / In this thesis we approached the two-dimensional level strip packing problem - 2LSP. 2LSP is a combinatorial optimization problem that, with respect to modeling, has received little attention from the scientific community. To the best of our knowledge, the most competitive model is the one proposed by Lodi et al. in 2004, where the items are packed by levels. In 2015, an arc flow model addressing the problem was proposed by Mehdi Mrad. The literature presents some mathematical models, despite not addressing specifically this problem, they are efficient and can be adapted for the two-dimensional level strip packing problem. In this thesis, we develop new models for the problem by adapting three mixed integer linear programming models from the literature. We also compare the computational performance of these new models with the models of Lodi et al. and Mehdi Mrad, by solving classical instances from the literature. The computational results show that one of the new mathematical formulations outperforms the remaining models with respect to the number of optimal solutions. To conclude, we present a practical application with the purpose of developing a tool for the automatic generation of the planograms used for the assembly of supermarket gondolas. For the application, we present a preliminary mixed integer programming model that can be applied to solve real applications.

Submitted by JÚLIO HEBER SILVA (julioheber@yahoo.com.br) on 2018-03-15T20:24:53Z No. of bitstreams: 2 Dissertação - Jéssica Gabriela de Almeida Cunha - 2018.pdf: 3483915 bytes, checksum: 12c37e736c4d6f53761fc0255e6bff6d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-03-16T11:10:21Z (GMT) No. of bitstreams: 2 Dissertação - Jéssica Gabriela de Almeida Cunha - 2018.pdf: 3483915 bytes, checksum: 12c37e736c4d6f53761fc0255e6bff6d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-03-16T11:10:21Z (GMT). No. of bitstreams: 2 Dissertação - Jéssica Gabriela de Almeida Cunha - 2018.pdf: 3483915 bytes, checksum: 12c37e736c4d6f53761fc0255e6bff6d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-02-22 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / 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. / Este trabalho traz o uso de malhas de pontos na resolução de problemas de corte e empacotamento para itens com formato retangular. As malhas podem ser consideradas em modelos de programação matemática e heurísticas, sendo independentes do problema tratado. As seguintes malhas definidas pela literatura, canonical dissections (também conhecida por normal patterns), reduced raster points, useful numbers, corner points, regular normal patterns, extreme points e meet-in-the-middle patterns, são consideradas neste trabalho. O objetivo é apresentar relações que existem entre as malhas e analisar a influência delas sobre o tempo gasto na resolução de problemas de corte e empacotamento, antes e após aplicar procedimentos de redução, como atualizar o tamanho dos itens. Resultados teóricos são obtidos envolvendo relações de conjunto e tamanho entre as malhas, mostrando que a malha de normal patterns e useful numbers são equivalentes e, assim, permitindo provar formalmente que a malha de reduced raster points garante uma solução ótima (resultado que estava em aberto na literatura). Além disso, propõe-se um novo procedimento visando reduzir o tamanho das malhas. Como forma de validar o procedimento proposto e avaliar a redução que ele proporciona nas malhas, executam-se experimentos sobre instâncias da literatura, sendo possível observar que as malhas de reduced raster points e meet-in-the-middle patterns são as menores. Experimentos também foram realizados sobre um problema de empacotamento bidimensional que utiliza um modelo de programação linear inteira para empacotar os itens em pontos da malha. Os resultados indicam que utilizando os procedimentos de redução é possível obter soluções ótimas mais rapidamente.