• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 7
  • 2
  • Tagged with
  • 9
  • 9
  • 9
  • 8
  • 8
  • 8
  • 6
  • 4
  • 4
  • 4
  • 3
  • 3
  • 3
  • 3
  • 3
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Heurística construtiva para o empacotamento de elipses tangentes em um polígono de n lados

Beckel, Cássia Cris January 2013 (has links)
Submitted by Milenna Moraes Figueiredo (milennasjn@gmail.com) on 2016-03-21T18:27:37Z No. of bitstreams: 1 2013-03-CassiaBeckel.pdf: 3043262 bytes, checksum: b4d8ecc2f5cd3190b2764693ce30f76a (MD5) / Rejected by Angelica Conceição Dias Miranda (angelicacdm@gmail.com), reason: Alterar 160 p. para 160 f. (Utilizamos folhas páginas seriam para livros) Fazer correções na Citação: como está - BECKEL, Cássia Cris. Heurística construtiva para o empacotamento de elipses tangentes em um polígono de n lados. 2013. 160p. Dissertação (Mestrado em Modelagem Computacional) - Programa de Pós-Graduação em Modelagem Computacional. Universidade Federal do Rio Grande, Rio Grande, 2013. Como deve ser - BECKEL, Cássia Cris. Heurística construtiva para o empacotamento de elipses tangentes em um polígono de n lados. 2013. 160 f. Dissertação (Mestrado em Modelagem Computacional) - Centro de Ciências Computacionais, Universidade Federal do Rio Grande, Rio Grande, 2013. Atenciosamente Equipe Revisão RI. on 2016-04-26T19:46:13Z (GMT) / Submitted by Milenna Moraes Figueiredo (milennasjn@gmail.com) on 2016-04-26T21:09:45Z No. of bitstreams: 1 2013-03-CassiaBeckel.pdf: 3043262 bytes, checksum: b4d8ecc2f5cd3190b2764693ce30f76a (MD5) / Rejected by Gilmar Barros (gilmargomesdebarros@gmail.com), reason: - Não foi colocado o nome do co-orientador. - Não foi colocado “ponto final” na citação. on 2016-04-27T12:24:49Z (GMT) / Submitted by Milenna Moraes Figueiredo (milennasjn@gmail.com) on 2016-04-27T17:31:32Z No. of bitstreams: 1 2013-03-CassiaBeckel.pdf: 3043262 bytes, checksum: b4d8ecc2f5cd3190b2764693ce30f76a (MD5) / Approved for entry into archive by Gilmar Barros (gilmargomesdebarros@gmail.com) on 2016-04-27T17:55:18Z (GMT) No. of bitstreams: 1 2013-03-CassiaBeckel.pdf: 3043262 bytes, checksum: b4d8ecc2f5cd3190b2764693ce30f76a (MD5) / Made available in DSpace on 2016-04-27T17:55:18Z (GMT). No. of bitstreams: 1 2013-03-CassiaBeckel.pdf: 3043262 bytes, checksum: b4d8ecc2f5cd3190b2764693ce30f76a (MD5) Previous issue date: 2013 / Problemas de corte e empacotamento estão presentes em diversos setores da industria, e o estudo destes problemas propicia oportunidades de colaboração entre os setores acadêmicos e industrial, com vistas a que se obtenham benefícios para ambos, contribuindo para a sociedade como um todo. Entre os setores industriais nos quais surgem problemas de corte e empacotamento estão as industrias têxtil, automotiva, portuária, lapidaria, entre outras. O presente trabalho tem como objetivo elaborar uma metodologia analítica e computacional com a qual seja possível encontrar uma solução viável para o problema de empacotamento de elipses, sendo idênticas ou não, sem sobreposição e tangentes a cada vértice e quadrante de uma elipse inicial inscrita em um polígono irregular de n lados. A metodologia analítica e computacional desenvolvida visa obter a maximização da área total das elipses empacotadas e a minimização do tempo de processamento computacional. Destaca-se a aplicabilidade das transformações em R2 para obter as novas equações paramétricas das elipses com centro deslocado da origem e rotacionadas em relação ao sistema de eixos cartesianos original. A heurística que realiza a verificação da inscrição de cada elipse, baseia-se em uma modificação da função inpolygon do software Matlab [34], de maneira que garante o empacotamento total das elipses no polígono. Para validar a heurística construtiva utilizaram-se 7 polígonos e com os resultados obtidos em cada simulação foi possível encontrar a função exponencial, através de um ajuste de curva, que descreve o comportamento da simulação.
2

Estudo de métodos de solução para problemas de corte de itens irregulares em recipientes irregulares / Study of solution methods for the irregular bin packing problem

Felipe Augusto Aureliano 30 June 2017 (has links)
Dentro da classe de problemas de corte e empacotamento, existem os problemas de corte de itens irregulares (não-circulares e não-retangulares), os quais visam determinar um arranjo ótimo de objetos irregulares menores (itens), sem sobreposição, dentro de objetos maiores (recipientes) a fim de atender a uma demanda. Possuem grande importância prática, uma vez que surgem em vários tipos de indústrias, como a têxtil, a de móveis e a de calçados, por exemplo. Entre estes problemas, ainda temos o chamado problema de corte de itens irregulares em recipientes, no qual estes últimos são fechados, isto é, possuem dimensões fixas, podendo ser retangulares ou irregulares. Neste caso, o objetivo é arranjar todos os itens de modo a utilizar o menor número possível de recipientes. A estes problemas, uma outra restrição ainda pode ser adicionada: os recipientes podem ter defeitos, isto é, áreas onde não pode ser posicionado qualquer item, e regiões com diferentes níveis de qualidade, chamadas de zonas de qualidades, em que apenas determinados itens podem ser alocados. Neste trabalho, portanto, introduzimos um conjunto de heurísticas construtivas para a resolução do problema de corte de itens irregulares em recipientes irregulares com defeitos e zonas de qualidades. Os experimentos computacionais foram realizados utilizando um conjunto com 15 instâncias adaptadas de outro problema de corte de itens irregulares, uma vez que não encontramos instâncias disponíveis na literatura para o problema abordado neste trabalho. Os resultados mostraram que todos os métodos são capazes de resolver o problema em um tempo computacional considerado baixo, sendo que alguns deles apresentam melhor desempenho que outros. / Within the class of cutting and packing problems, there are some problems known as nesting problems, which aim to determine an optimal arrangement of smaller irregular objects (items), without overlap, inside larger objects (bins) in order to attend a demand. They have practical importance, since they arise in many types of industries, such as textiles, furniture and footwear, for example. Among these problems, we still have the so-called irregular bin packing problem in which the bins are closed, that is, they have fixed dimensions, and may be rectangular or irregular. In this case, the goal is to arrange all items in order to use the least amount of bins. To these problems, another constraint can still be added: the bins may have defects, that is, areas where no item can be placed, and different levels of quality, called quality zones, where only specific items can be allocated. In this work, therefore, we introduce a set of constructive heuristics to solve the irregular bin packing problem in which the bins have defects and quality zones. The computational experiments were carried out using a set of 15 instances adapted from another nesting problem, since we did not find instances available in the literature for the problem addressed in this work. The results showed that all methods can solve the problem in a low computational time, and also that some of them perform better than others.
3

Mathematical models and heuristic methods for nesting problems / Modelos matemáticos e métodos heurísticos para os problemas de corte de itens irregulares

Mundim, Leandro Resende 18 August 2017 (has links)
Irregular cutting and packing problems, with convex and non-convex polygons, are found in many industries such as metal mechanics, textiles, of shoe making, the furniture making and others. In this thesis we study the two-dimensional version of these problems, where we want to allocate a set of items, without overlap, inside one or more containers, limited or unlimited, so as to optimize an objective function. In this document we study the knapsack problem, placement problem, strip packing problem, cutting stock problem and bin packing problem. For these problems, the heuristic methods and mathematical programming models are proposed and presented very promising results, surpassing in many cases the best results in the specialized literature. This thesis is organized as follows. In Chapter 1, we present a review of the studied problems, the value proposition for this thesis with the main contributions and ideas. In Chapter 2, we propose a metaheursitic for the strip packing problem with irregular items and circles. Then, in Chapter 3, we present a generic heuristic for the allocation of irregular items that may be weakly or strongly heterogeneous and will be allocated in a container (output maximization problems) or multiple containers (input minimization problems). In Chapter 4, we propose a solution method for the cutting stock problem with deterministic demand and stochastic demand. In Chapters 5 and 6, we present mathematical programming models for the strip packing problem. Finally, in Chapter 7, we present a conclusion and a concise direction for future works. / Os problemas de corte e empacotamento de itens irregulares, polígonos convexos e não convexos, são encontrado em diversas indústrias, tais como a metal-mecânica, a têxtil, a de calçados, a moveleira e outras. Nesta tese estudamos a versão bidimensional destes problemas, na qual desejamos alocar um conjunto de itens, sem sobreposição, no interior de um ou mais recipientes, limitados ou ilimitados, de modo a otimizar uma função objetivo. Neste trabalho estudamos o problema da mochila, o problema do assentamento, o problema empacotamento em faixa, o problema de corte de estoque e o problema de empacotamento de contêineres. Para estes problemas, os métodos heurísticos e modelos de programação matemática propostos e apresentam resultados muito promissores, ultrapassando em muitos casos os melhores resultados da literatura especializada. Esta tese esta organizada da seguinte maneira. No Capítulo 1, apresentamos uma revisão dos problemas estudados, a proposta de valor deste doutorado com as principais contribuições e ideias. No Capítulo 2, propomos uma meta-heurística para o problema de empacotamento em faixa para itens irregulares e círculos. Em seguida, no Capítulo 3 apresentamos uma heurística genérica para a alocação de itens irregulares que podem ser fracamente ou fortemente heterogêneos e serão alocados em um recipiente (problema de maximização de saída) ou de múltiplos recipientes (problemas de minimização de entrada). O Capítulo 4 propõem um método de solução para o problema de corte de estoque com demanda conhecida e demanda estocástica. Nos Capítulos 5 e 6 apresentamos modelos de programação matemática para o problema de corte de itens irregulares em faixa. Finalmente, no Capítulo 7, apresentamos a conclusão e uma sucinta direção para os trabalhos futuros.
4

Estudo de métodos de solução para problemas de corte de itens irregulares em recipientes irregulares / Study of solution methods for the irregular bin packing problem

Aureliano, Felipe Augusto 30 June 2017 (has links)
Dentro da classe de problemas de corte e empacotamento, existem os problemas de corte de itens irregulares (não-circulares e não-retangulares), os quais visam determinar um arranjo ótimo de objetos irregulares menores (itens), sem sobreposição, dentro de objetos maiores (recipientes) a fim de atender a uma demanda. Possuem grande importância prática, uma vez que surgem em vários tipos de indústrias, como a têxtil, a de móveis e a de calçados, por exemplo. Entre estes problemas, ainda temos o chamado problema de corte de itens irregulares em recipientes, no qual estes últimos são fechados, isto é, possuem dimensões fixas, podendo ser retangulares ou irregulares. Neste caso, o objetivo é arranjar todos os itens de modo a utilizar o menor número possível de recipientes. A estes problemas, uma outra restrição ainda pode ser adicionada: os recipientes podem ter defeitos, isto é, áreas onde não pode ser posicionado qualquer item, e regiões com diferentes níveis de qualidade, chamadas de zonas de qualidades, em que apenas determinados itens podem ser alocados. Neste trabalho, portanto, introduzimos um conjunto de heurísticas construtivas para a resolução do problema de corte de itens irregulares em recipientes irregulares com defeitos e zonas de qualidades. Os experimentos computacionais foram realizados utilizando um conjunto com 15 instâncias adaptadas de outro problema de corte de itens irregulares, uma vez que não encontramos instâncias disponíveis na literatura para o problema abordado neste trabalho. Os resultados mostraram que todos os métodos são capazes de resolver o problema em um tempo computacional considerado baixo, sendo que alguns deles apresentam melhor desempenho que outros. / Within the class of cutting and packing problems, there are some problems known as nesting problems, which aim to determine an optimal arrangement of smaller irregular objects (items), without overlap, inside larger objects (bins) in order to attend a demand. They have practical importance, since they arise in many types of industries, such as textiles, furniture and footwear, for example. Among these problems, we still have the so-called irregular bin packing problem in which the bins are closed, that is, they have fixed dimensions, and may be rectangular or irregular. In this case, the goal is to arrange all items in order to use the least amount of bins. To these problems, another constraint can still be added: the bins may have defects, that is, areas where no item can be placed, and different levels of quality, called quality zones, where only specific items can be allocated. In this work, therefore, we introduce a set of constructive heuristics to solve the irregular bin packing problem in which the bins have defects and quality zones. The computational experiments were carried out using a set of 15 instances adapted from another nesting problem, since we did not find instances available in the literature for the problem addressed in this work. The results showed that all methods can solve the problem in a low computational time, and also that some of them perform better than others.
5

Mathematical models and heuristic methods for nesting problems / Modelos matemáticos e métodos heurísticos para os problemas de corte de itens irregulares

Leandro Resende Mundim 18 August 2017 (has links)
Irregular cutting and packing problems, with convex and non-convex polygons, are found in many industries such as metal mechanics, textiles, of shoe making, the furniture making and others. In this thesis we study the two-dimensional version of these problems, where we want to allocate a set of items, without overlap, inside one or more containers, limited or unlimited, so as to optimize an objective function. In this document we study the knapsack problem, placement problem, strip packing problem, cutting stock problem and bin packing problem. For these problems, the heuristic methods and mathematical programming models are proposed and presented very promising results, surpassing in many cases the best results in the specialized literature. This thesis is organized as follows. In Chapter 1, we present a review of the studied problems, the value proposition for this thesis with the main contributions and ideas. In Chapter 2, we propose a metaheursitic for the strip packing problem with irregular items and circles. Then, in Chapter 3, we present a generic heuristic for the allocation of irregular items that may be weakly or strongly heterogeneous and will be allocated in a container (output maximization problems) or multiple containers (input minimization problems). In Chapter 4, we propose a solution method for the cutting stock problem with deterministic demand and stochastic demand. In Chapters 5 and 6, we present mathematical programming models for the strip packing problem. Finally, in Chapter 7, we present a conclusion and a concise direction for future works. / Os problemas de corte e empacotamento de itens irregulares, polígonos convexos e não convexos, são encontrado em diversas indústrias, tais como a metal-mecânica, a têxtil, a de calçados, a moveleira e outras. Nesta tese estudamos a versão bidimensional destes problemas, na qual desejamos alocar um conjunto de itens, sem sobreposição, no interior de um ou mais recipientes, limitados ou ilimitados, de modo a otimizar uma função objetivo. Neste trabalho estudamos o problema da mochila, o problema do assentamento, o problema empacotamento em faixa, o problema de corte de estoque e o problema de empacotamento de contêineres. Para estes problemas, os métodos heurísticos e modelos de programação matemática propostos e apresentam resultados muito promissores, ultrapassando em muitos casos os melhores resultados da literatura especializada. Esta tese esta organizada da seguinte maneira. No Capítulo 1, apresentamos uma revisão dos problemas estudados, a proposta de valor deste doutorado com as principais contribuições e ideias. No Capítulo 2, propomos uma meta-heurística para o problema de empacotamento em faixa para itens irregulares e círculos. Em seguida, no Capítulo 3 apresentamos uma heurística genérica para a alocação de itens irregulares que podem ser fracamente ou fortemente heterogêneos e serão alocados em um recipiente (problema de maximização de saída) ou de múltiplos recipientes (problemas de minimização de entrada). O Capítulo 4 propõem um método de solução para o problema de corte de estoque com demanda conhecida e demanda estocástica. Nos Capítulos 5 e 6 apresentamos modelos de programação matemática para o problema de corte de itens irregulares em faixa. Finalmente, no Capítulo 7, apresentamos a conclusão e uma sucinta direção para os trabalhos futuros.
6

Problemas de Corte e Empacotamento: Uma abordagem em Grafo E/OU / Cutting and packing problems: an AND/OR-Graph approach

Vianna, Andréa Carla Gonçalves 19 December 2000 (has links)
O problema de corte consiste no corte de objetos maiores para produção de peças menores, de modo que uma certa função objetivo seja otimizada, por exemplo, a perda seja minimizada. O problema de empacotamento pode também ser visto como um problema de corte, onde as peças menores são arranjadas dentro dos objetos. Uma abordagem em grafo E/OU para a resolução de problemas de corte e empacotamento foi proposta inicialmente por Morabito (1989) para problemas de corte bidimensionais e, mais tarde, estendida para problemas tridimensionais (Morabito, 1992). Nesta abordagem foi utilizada uma técnica de busca híbrida, onde se combinou a busca em profundidade primeiro com limite de profundidade e a busca hill-climbing, utilizando-se heurísticas baseadas nos limitantes superiores e inferiores. Experiências computacionais mostraram a viabilidade de uso na prática desta abordagem. Mais tarde, Arenales (1993) generalizou esta a abordagem em grafo E/OU mostrando como diferentes problemas de corte poderiam ser resolvidos, independentemente da dimensão, formas dos objetos e itens, baseado em simples hipóteses, sem realizar, entretanto, estudos computacionais. O presente trabalho tem por objetivo estender a abordagem em grafo E/OU para tratar outros casos não analisados pelos trabalhos anteriores, tais como situações envolvendo diferentes processos de corte, bem como a implementação computacional de métodos baseados na abordagem em grafo E/OU, mostrando, assim, a versatilidade da abordagem para tratar diversas situações práticas de problemas de corte e sua viabilidade computacional. / The cutting problem consists of cutting larger objects in order to produce smaller pieces, in such a way as to optimizing a given objective function, for example, minimizing the waste. The packing problem can also be seen as a cutting problem, where the position that each smaller piece is arranged inside of the objects can be seen as the place it was cut from. An AND/OR-graph approach to solve cutting and packing problems was initially proposed by Morabito (1989) for two-dimensional cutting problem and, later, extended to threedimensional problems (Morabito, 1992). That approach uses a hybrid search, which combines depth-first search under depth bound and hill-climbing strategy. Heuristics were devised based on upper and lower bounds. Computational experiences demonstrated its practical feasibility. The AND/OR-graph approach was later generalized by Arenales (1993) based on simple hypothesis. He showed that different cutting problems Gould be solved using the AND/ORgraph approach, independently of the dimension and shapes. The main objective of this thesis is the practical extension of the AND/OR-graph approach to handle other cases not considered by previous works. It was considered different cutting processes, as well as the analysis of computational implementation, showing how can it be adapted to many classes of practical cutting and packing problems.
7

Problemas de Corte e Empacotamento: Uma abordagem em Grafo E/OU / Cutting and packing problems: an AND/OR-Graph approach

Andréa Carla Gonçalves Vianna 19 December 2000 (has links)
O problema de corte consiste no corte de objetos maiores para produção de peças menores, de modo que uma certa função objetivo seja otimizada, por exemplo, a perda seja minimizada. O problema de empacotamento pode também ser visto como um problema de corte, onde as peças menores são arranjadas dentro dos objetos. Uma abordagem em grafo E/OU para a resolução de problemas de corte e empacotamento foi proposta inicialmente por Morabito (1989) para problemas de corte bidimensionais e, mais tarde, estendida para problemas tridimensionais (Morabito, 1992). Nesta abordagem foi utilizada uma técnica de busca híbrida, onde se combinou a busca em profundidade primeiro com limite de profundidade e a busca hill-climbing, utilizando-se heurísticas baseadas nos limitantes superiores e inferiores. Experiências computacionais mostraram a viabilidade de uso na prática desta abordagem. Mais tarde, Arenales (1993) generalizou esta a abordagem em grafo E/OU mostrando como diferentes problemas de corte poderiam ser resolvidos, independentemente da dimensão, formas dos objetos e itens, baseado em simples hipóteses, sem realizar, entretanto, estudos computacionais. O presente trabalho tem por objetivo estender a abordagem em grafo E/OU para tratar outros casos não analisados pelos trabalhos anteriores, tais como situações envolvendo diferentes processos de corte, bem como a implementação computacional de métodos baseados na abordagem em grafo E/OU, mostrando, assim, a versatilidade da abordagem para tratar diversas situações práticas de problemas de corte e sua viabilidade computacional. / The cutting problem consists of cutting larger objects in order to produce smaller pieces, in such a way as to optimizing a given objective function, for example, minimizing the waste. The packing problem can also be seen as a cutting problem, where the position that each smaller piece is arranged inside of the objects can be seen as the place it was cut from. An AND/OR-graph approach to solve cutting and packing problems was initially proposed by Morabito (1989) for two-dimensional cutting problem and, later, extended to threedimensional problems (Morabito, 1992). That approach uses a hybrid search, which combines depth-first search under depth bound and hill-climbing strategy. Heuristics were devised based on upper and lower bounds. Computational experiences demonstrated its practical feasibility. The AND/OR-graph approach was later generalized by Arenales (1993) based on simple hypothesis. He showed that different cutting problems Gould be solved using the AND/ORgraph approach, independently of the dimension and shapes. The main objective of this thesis is the practical extension of the AND/OR-graph approach to handle other cases not considered by previous works. It was considered different cutting processes, as well as the analysis of computational implementation, showing how can it be adapted to many classes of practical cutting and packing problems.
8

Modelos de programação matemática para problemas de carregamento de caixas dentro de contêineres

Junqueira, Leonardo 26 February 2009 (has links)
Made available in DSpace on 2016-06-02T19:51:39Z (GMT). No. of bitstreams: 1 2523.pdf: 1711552 bytes, checksum: cf13454170c0e1db1eb5ae2aa8cff6a3 (MD5) Previous issue date: 2009-02-26 / Financiadora de Estudos e Projetos / The object of this study is a particular case of the cutting and packing problems, known as container loading problems. These problems consist in arranging rectangular boxes orthogonally into containers (or into trucks, railcars and pallets), in order to optimize an objective function, for example, maximize the utilization of the available space, or minimize the number of the required containers to load all the available items. The objective of this study is to develop mathematical programming models to deal with situations commonly found in container loading practice. Multiple orientations of the boxes, weight limit of the container, cargo stability, load bearing strength of the boxes and multiple destinations of the cargo are considered. The author is not aware of mathematical formulations available in the cutting and packing literature that deal with such considerations, and this paper intends to contribute with possible formulations that describe these situations, although not very realistic for being used in practice. Computational experiments with the proposed models are performed with the software AMS/CPLEX and randomly generated instances extracted from the cutting and packing literature. The results show that the models are consistent and properly represent the practical situations treated, although this approach (in its current version) is limited to solve to optimality only medium-sized problems. However, we believe that the proposed models can be useful to motivate future research exploring decomposition methods, relaxations, heuristics, among others, to solve the present problems. / O objeto de estudo deste trabalho é um caso particular dos problemas de corte e empacotamento, conhecido como problemas de carregamento de contêineres. Estes problemas consistem em arranjar caixas retangulares ortogonalmente dentro de contêineres (ou caminhões, vagões ferroviários e paletes), de maneira a otimizar uma função objetivo, por exemplo, maximizar o aproveitamento do espaço disponível, ou então minimizar o número de contêineres necessários para carregar todas as caixas disponíveis. O objetivo deste trabalho é desenvolver modelos de programação matemática que abordem situações comumente encontradas na prática do carregamento de contêineres. Considerações de múltiplas orientações das caixas, limite de peso do contêiner, estabilidade do carregamento, resistência das caixas ao empilhamento e carga fracionada em múltiplos destinos são tratadas. O autor não tem conhecimento de formulações matemáticas disponíveis na literatura de corte e empacotamento que tratem estas considerações, e este trabalho pretende contribuir com possíveis formulações que, embora pouco realistas para serem aplicadas na prática, descrevem estas situações. Experimentos computacionais com os modelos propostos são realizados utilizando o aplicativo GAMS/CPLEX e exemplos gerados aleatoriamente e da literatura. Os resultados mostram que os modelos são coerentes e representam adequadamente as situações tratadas, embora esta abordagem (na sua versão atual) esteja limitada a resolver otimamente apenas problemas de tamanho bem moderado. No entanto, os modelos podem ser úteis para motivar pesquisas futuras explorando métodos de decomposição, métodos de relaxação, métodos heurísticos, entre outros, para resolver os problemas em questão.
9

Comparação de malhas para problemas de corte e empacotamento / Comparison of grids to cutting and packing problems

Cunha, Jéssica Gabriela de Almeida 22 February 2018 (has links)
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.

Page generated in 0.2185 seconds