No description available.

Orientadores: Eduardo Candido Xavier, Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-18T03:33:12Z (GMT). No. of bitstreams: 1 Silveira_JeffersonLuizMoisesda_M.pdf: 1516196 bytes, checksum: b3f9127c1017ef29bf9c429bb93e1a0c (MD5) Previous issue date: 2011 / Resumo: Neste trabalho estudamos problemas de empacotamento com restrições de descarregamento considerados NP-difíceis. Estes problemas possuem aplicações nas áreas de logística e roteamento. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes para resolver tais problemas. Uma das abordagens consideradas para tratar tais problemas é a de algoritmos de aproximação, que são algoritmos eficientes (complexidade de tempo polinomial) e que geram soluções com garantia de qualidade. Estudamos técnicas para o desenvolvimento de algoritmos aproximados e também alguns algoritmos para problemas de empacotamento online que podem ser utilizados na resolução do problema estudado. Propomos também algumas heurísticas para o problema e, além disto, provamos que duas destas heurísticas possuem garantias de aproximação com fatores constantes. Realizamos testes computacionais com estes algoritmos propostos. Dentre estes, a heurística GRASP foi a que obteve melhores resultados para as instâncias de teste consideradas / Abstract: In this work we study some NP-hard packing problems with unloading constraints. These problems have applications in logistics and routing problems. Assuming P ? NP, there are no efficient algorithms to solve these problems. On way to deal with these problems is using approximation algorithms, that are efficient algorithms (polynomial time complexity) that produce solutions with quality guarantee. We study techniques used in the development of approximation algorithms and some algorithms for online packing problems which can be used to solve the considered problem. We propose some heuristics for the problem and prove that two of them have constant approximation guarantees. We also perform computational tests with the proposed algorithms. Among them, the GRASP heuristic achieved the best results on the considered instances / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

No description available.

O problema de empacotamento consiste em arranjar um conjunto de itens em um contêiner, a fim de maximizar sua utilização. Este campo de estudos tem impacto em diversas indústrias, incluindo as indústrias têxtil, moveleira e naval. Neste trabalho, dois problemas de empacotamento de itens irregulares são estudados. O primeiro, chamado primal, é o caso em que os itens possuem rotação livre e o contêiner de dimensões fixas pode ser representado por um polígono qualquer, podendo ser não convexo. O segundo problema, denominado dual, consiste em posicionar os itens, que possuem apenas algumas orientações possíveis, em um contêiner retangular em que uma das dimensões é considerada infinita. Assim, o objetivo é obter o menor contêiner, variando a dimensão não fixa, no qual todos os itens podem ser posicionados sem sobreposição. Em ambos problemas, a solução é representada por uma lista ordenada de itens e uma regra de posicionamento é aplicada para se obter o leiaute. Neste caso, sobreposições não são permitidas. Para se garantir leiautes factíveis (sem sobreposição), é adotado o conceito de região livre de colisão. A região livre de colisão representa todas as translações possíveis para inserir um novo item em um contêiner com itens já posicionados. A região livre de colisão é obtida através de operações Booleanas envolvendo polígonos de obstrução e de posicionamento interno. Devido às propriedades dos conceitos envolvidos, o cálculo da região livre de colisão deve ser feito utilizando operações Booleanas não regularizadas. Um novo algoritmo de operação Booleana não regularizada de união e subtração é desenvolvido a partir da implementação de um algoritmo de operações Booleanas regularizadas. Um algoritmo de recozimento simulado é utilizado para controlar a posição, o ângulo (ou orientação) e a seqüência dos itens. Cada item só pode ser posicionado no vértice da região livre de colisão. Com a finalidade de melhorar o desempenho computacional do algoritmo, um método de paralelização do cálculo da região livre de colisão é proposto. Para comparação, são adotados dois algoritmos seriais. Através dos resultados, é possível afirmar que o algoritmo primal foi capaz de resolver problemas do tipo quebra-cabeça, incluindo contêineres convexos e com furos. O algoritmo apresentou melhora significativa no desempenho quando comparado com trabalhos anteriores. Para o caso dual foi proposto um algoritmo de dois níveis, em que o externo controla o comprimento do contêiner e o interno é semelhante ao primal. Este algoritmo foi testado com problemas existentes na literatura e apresentou soluções competitivas, obtendo alguns leiautes mais compactos. A paralelização apresentou ganho de desempenho apenas nos problemas com grande número de itens. Foi constatado que o custo computacional de operações Booleanas não regularizadas é fortemente dependente do número de vértices e intersecções dos polígonos de entrada da operação. / The irregular shape packing problem is an optimization problem that consists of arranging items on a container in order to maximize the utility rate of the sheet stock. This work investigates two problems. In the first problem, the single bin packing, the items can rotate freely and the container with fixed dimension can be any polygon, convex or non-convex. The second problem, the open dimension problem, consists of arranging items that have few admissible orientations in a container with fixed width and variable length. The objective is to find a feasible layout of the set of items that minimizes the length of the container. The solution is always represented as an ordered list of items to be packed and a placement heuristic is applied in order to generate a layout. To ensure feasible layouts, the concept of collision free region is adopted. It represents all the positions that a new item can be placed inside the container, without colliding with already placed items. The collision free region is obtained through non manifold Boolean operations applied to no-fit polygon and the inner-fit polygon. The simulated annealing algorithm controls the position, rotation and placement order of the items. Each item is is exclusively placed on collision free region\'s vertex. To improve the computational cost performance of the algorithm, a parallelization method to determine the collision free region is proposed. The speed of this algorithm is compared with two different serial methods of determing the collision free region. From the results, it can be observed that the solutions for the single bin packing problem are very competitive with previous works and can achieve optimal solution for puzzles with irregular shaped containers and containers with holes. The algorithm for the open dimension has two hierarchical levels: a core level with a simulated annealing algorithm, and the external level controlling the container length. This algorithm was tested with literature problems and obtained very competitive results, some which are more compact. The results showed that the parallelized version is better than the sequential approach only for datasets with very large number of items. The computational cost of the non manifold Boolean operation algorithm is strongly dependent on the number of vertices and intersections of the original polygons.

O problema de empacotamento consiste em arranjar um conjunto de itens em um contêiner, a fim de maximizar sua utilização. Este campo de estudos tem impacto em diversas indústrias, incluindo as indústrias têxtil, moveleira e naval. Neste trabalho, dois problemas de empacotamento de itens irregulares são estudados. O primeiro, chamado primal, é o caso em que os itens possuem rotação livre e o contêiner de dimensões fixas pode ser representado por um polígono qualquer, podendo ser não convexo. O segundo problema, denominado dual, consiste em posicionar os itens, que possuem apenas algumas orientações possíveis, em um contêiner retangular em que uma das dimensões é considerada infinita. Assim, o objetivo é obter o menor contêiner, variando a dimensão não fixa, no qual todos os itens podem ser posicionados sem sobreposição. Em ambos problemas, a solução é representada por uma lista ordenada de itens e uma regra de posicionamento é aplicada para se obter o leiaute. Neste caso, sobreposições não são permitidas. Para se garantir leiautes factíveis (sem sobreposição), é adotado o conceito de região livre de colisão. A região livre de colisão representa todas as translações possíveis para inserir um novo item em um contêiner com itens já posicionados. A região livre de colisão é obtida através de operações Booleanas envolvendo polígonos de obstrução e de posicionamento interno. Devido às propriedades dos conceitos envolvidos, o cálculo da região livre de colisão deve ser feito utilizando operações Booleanas não regularizadas. Um novo algoritmo de operação Booleana não regularizada de união e subtração é desenvolvido a partir da implementação de um algoritmo de operações Booleanas regularizadas. Um algoritmo de recozimento simulado é utilizado para controlar a posição, o ângulo (ou orientação) e a seqüência dos itens. Cada item só pode ser posicionado no vértice da região livre de colisão. Com a finalidade de melhorar o desempenho computacional do algoritmo, um método de paralelização do cálculo da região livre de colisão é proposto. Para comparação, são adotados dois algoritmos seriais. Através dos resultados, é possível afirmar que o algoritmo primal foi capaz de resolver problemas do tipo quebra-cabeça, incluindo contêineres convexos e com furos. O algoritmo apresentou melhora significativa no desempenho quando comparado com trabalhos anteriores. Para o caso dual foi proposto um algoritmo de dois níveis, em que o externo controla o comprimento do contêiner e o interno é semelhante ao primal. Este algoritmo foi testado com problemas existentes na literatura e apresentou soluções competitivas, obtendo alguns leiautes mais compactos. A paralelização apresentou ganho de desempenho apenas nos problemas com grande número de itens. Foi constatado que o custo computacional de operações Booleanas não regularizadas é fortemente dependente do número de vértices e intersecções dos polígonos de entrada da operação. / The irregular shape packing problem is an optimization problem that consists of arranging items on a container in order to maximize the utility rate of the sheet stock. This work investigates two problems. In the first problem, the single bin packing, the items can rotate freely and the container with fixed dimension can be any polygon, convex or non-convex. The second problem, the open dimension problem, consists of arranging items that have few admissible orientations in a container with fixed width and variable length. The objective is to find a feasible layout of the set of items that minimizes the length of the container. The solution is always represented as an ordered list of items to be packed and a placement heuristic is applied in order to generate a layout. To ensure feasible layouts, the concept of collision free region is adopted. It represents all the positions that a new item can be placed inside the container, without colliding with already placed items. The collision free region is obtained through non manifold Boolean operations applied to no-fit polygon and the inner-fit polygon. The simulated annealing algorithm controls the position, rotation and placement order of the items. Each item is is exclusively placed on collision free region\'s vertex. To improve the computational cost performance of the algorithm, a parallelization method to determine the collision free region is proposed. The speed of this algorithm is compared with two different serial methods of determing the collision free region. From the results, it can be observed that the solutions for the single bin packing problem are very competitive with previous works and can achieve optimal solution for puzzles with irregular shaped containers and containers with holes. The algorithm for the open dimension has two hierarchical levels: a core level with a simulated annealing algorithm, and the external level controlling the container length. This algorithm was tested with literature problems and obtained very competitive results, some which are more compact. The results showed that the parallelized version is better than the sequential approach only for datasets with very large number of items. The computational cost of the non manifold Boolean operation algorithm is strongly dependent on the number of vertices and intersections of the original polygons.

Geometric packing problems are NP-complete problems that arise in VLSI design. In this thesis, we present two novel algorithms using dynamic programming to compute exactly the maximum number of k x k squares of unit size that can be packed without overlap into a given n x m grid. The first algorithm was implemented and ran successfully on problems of large input up to 1,000,000 nodes for different values. A heuristic based on the second algorithm is implemented. This heuristic is fast in practice, but may not always be giving optimal times in theory. However, over a wide range of random data this version of the algorithm is giving very good solutions very fast and runs on problems of up to 100,000,000 nodes in a grid and different ranges for the variables. It is also shown that this version of algorithm is clearly superior to the first algorithm and has shown to be very efficient in practice.

Nesse trabalho, estudamos um problema de otimização combinatorial conhecido por Problema da Mochila Compartimentada, que é uma extensão do clássico Problema da Mochila. O problema consiste em determinar as capacidades adequadas de vários compartimentos que podem vir a ser alocados em uma mochila e como esses compartimentos devem ser carregados, respeitando as restrições de capacidades dos compartimentos e da mochila. Busca-se maximizar o valor de utilidade total. O problema é muito pouco estudado na literatura, apesar de surgir naturalmente em aplicações práticas. Nesse estudo, propomos uma modelagem matemática não linear para o problema e verificamos algumas heurísticas para sua resolução. / In this work, we studied a combinatorial optimization problem called the Clustered Knapsack Problem, that is an extension of the standard Knapsack Problem. The problem is to determine the right capacities of several clusters which can be allocated in a knapsack and how these clusters should be placed so as to respect the constraints on the capacities of the clusters and the knapsack. The objective is to maximize a total utility value. The problem has seldom been studied in the literature, even though it appears naturally in practical applications. In this study, we propose a non-linear model for the problem and we insert some heuristics for its resolution.

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.

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.

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.