Made available in DSpace on 2014-06-12T15:59:06Z (GMT). No. of bitstreams: 2 arquivo4838_1.pdf: 7602633 bytes, checksum: 600ab77ebdd41162baaff3435aa76f53 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2003 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Um dos problemas abertos mais básicos da área de corte e empacotamento é encontrar o maior número de (,w)-retângulos que podem ser empacotados ortogonalmente num retângulo maior (L,W). O termo ortogonalmente quer dizer, apenas, que cada lado de um (,w)-retângulo empacotado é paralelo ou perpendicular aos lados do retângulo maior (L,W). Motivados por este problema e suas variantes mais difíceis (ex. caso tridimensional), desenvolvemos, baseado no trabalho [2], uma abordagem heurística geral de decomposições de gblocos. Os gblocos são uma generalização dos blocos. Os blocos são simplesmente retângulos em dimensão 2 e paralelepípedos em dimensão 3 (e seus análogos em dimensões maiores). Aplicando a abordagem de gblocos para o problema bidimensional aberto que mencionamos, mostramos se tratar, em termos de otimalidade, de um método superior á melhor heurística existente até o momento: a heurística de R. Morabito e S. Morales (1998). De fato ainda não é conhecido nenhum problema (,w, L,W) para o qual a nossa abordagem em gblocos não seja ótima. Esta observação empírica levanta a dúvida de estarmos diante de um método exato para o problema. Além do caso bidimensional, sugerimos também uma abordagem em gblocos para o caso tridimensional. Melhores métodos de empacotamento têm importante implicação econômica. Hoje, caminhões, trens, navios e aviões transportam contêineres e paletes com uma carga menor do que poderiam. Esta Tese é um passo na busca de melhores métodos. Ela apresenta alguns resultados originais, formaliza uma linguagem adequada para o problema abstrato e, por fim, sugere um caminho promissor para o problema concreto no setor de transporte de carga

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.

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.