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.

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.

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.

Nesta tese é abordado o problema da mochila compartimentada e o problema de corte de estoque unidimensional acoplado ao problema dimensionamento de lotes. Para o problema da mochila compartimentada é apresentada a versão unidimensional e proposta a versão bidimensional, denominados como problema da mochila compartimentada unidimensional e problema da mochila compartimentada bidimensional, respectivamente. Para o problema de corte de estoque acoplado ao dimensionamento de lotes são apresentadas três variações: uma máquina para produzir um tipo de objeto; uma máquina para produzir vários tipos de objetos; múltiplas máquinas para produzir vários tipos de objetos. Algumas formulações matemáticas de programação inteira e inteira-mista, decomposições dos problemas em problema mestre e subproblemas e heurísticas baseadas no método geração de colunas são propostas para os problemas da mochila compartimenta e o problema acoplado. Em específico, para o problema acoplado são aplicadas decomposições Dantzig-Wolfe, que podem ser por período, por máquina ou por período e máquina. Além disso, uma heurística baseada em grafo E/OU é proposta para o problema da mochila compartimentada bidimensional / In this thesis we present the constrained compartmentalized knapsack problem and the one dimensional cutting stock problem integrated with the capacitated lot sizing problem. For the constrained compartmentalized knapsack problem, the one dimensional version is presented and the two dimensional version is proposed, called one-dimensional compartmentalized knapsack problem and two-dimensional compartmentalized knapsack problem, respectively. For the cutting stock problem integrated with the capacitated lot sizing problem three variations are considered: one machine to produce one type of object; one machine to produce multiple types of objects; multiple machines to produce multiple types of objects. Some integer and mixed programming formulations, decompositions of the problems in master problem and subproblems and heuristics based on column generation method are proposed for the compartmentalized knapsack problem and the cutting stock problem integrated with the capacitated lot sizing problem. In particular, the period, the machine, and the period and machine Dantzig- Wolfe decompositions are applied for the integrated problem. Moreover, a heuristic based on the graph AND/OR is proposed for the two-dimensional compartmentalized knapsack problem. Computational results show that these mathematical formulations and methods provide good solutions

Nesta tese é abordado o problema da mochila compartimentada e o problema de corte de estoque unidimensional acoplado ao problema dimensionamento de lotes. Para o problema da mochila compartimentada é apresentada a versão unidimensional e proposta a versão bidimensional, denominados como problema da mochila compartimentada unidimensional e problema da mochila compartimentada bidimensional, respectivamente. Para o problema de corte de estoque acoplado ao dimensionamento de lotes são apresentadas três variações: uma máquina para produzir um tipo de objeto; uma máquina para produzir vários tipos de objetos; múltiplas máquinas para produzir vários tipos de objetos. Algumas formulações matemáticas de programação inteira e inteira-mista, decomposições dos problemas em problema mestre e subproblemas e heurísticas baseadas no método geração de colunas são propostas para os problemas da mochila compartimenta e o problema acoplado. Em específico, para o problema acoplado são aplicadas decomposições Dantzig-Wolfe, que podem ser por período, por máquina ou por período e máquina. Além disso, uma heurística baseada em grafo E/OU é proposta para o problema da mochila compartimentada bidimensional / In this thesis we present the constrained compartmentalized knapsack problem and the one dimensional cutting stock problem integrated with the capacitated lot sizing problem. For the constrained compartmentalized knapsack problem, the one dimensional version is presented and the two dimensional version is proposed, called one-dimensional compartmentalized knapsack problem and two-dimensional compartmentalized knapsack problem, respectively. For the cutting stock problem integrated with the capacitated lot sizing problem three variations are considered: one machine to produce one type of object; one machine to produce multiple types of objects; multiple machines to produce multiple types of objects. Some integer and mixed programming formulations, decompositions of the problems in master problem and subproblems and heuristics based on column generation method are proposed for the compartmentalized knapsack problem and the cutting stock problem integrated with the capacitated lot sizing problem. In particular, the period, the machine, and the period and machine Dantzig- Wolfe decompositions are applied for the integrated problem. Moreover, a heuristic based on the graph AND/OR is proposed for the two-dimensional compartmentalized knapsack problem. Computational results show that these mathematical formulations and methods provide good solutions

O Problema da Mochila Compartimentada é uma extensão do Problema da Mochila, em que os itens solicitados são divididos em classes, de modo que a mochila deve ser subdividida em compartimentos, os quais têm capacidades limitadas e são carregados com itens da mesma classe. Além disso, a construção de um compartimento tem um custo fixo e ocasiona uma perda no espaço da mochila. O objetivo consiste em maximizar a soma dos valores dos itens, descontado o custo fixo de inclusão de compartimentos. Neste trabalho, são abordados dois métodos de solução. A primeira abordagem é uma heurística, que consiste na combinação de duas heurísticas da literatura. A segunda abordagem é o método Geração de Colunas, que além de fornecer um novo limitante superior para o Problema da Mochila Compartimentada, ao final do método o problema mestre foi resolvido com as variáveis definidas como inteiras, obtendo uma solução factível. Em ambos os métodos, o modelo não-linear é decomposto em dois modelos lineares, no qual, um gera compartimentos e o outro os seleciona. Os resultados obtidos com as duas abordagens foram comparados com um limitante superior e se mostraram bastante satisfatórios / The Compartmentalized Knapsack Problem is an extension of the classical Knapsack Problem, where the ordered items are partitioned into classes, in such way that the knapsack must be divided into compartments, each one having limited capacity. In addition, the building of a compartment has a fixed cost and involves a loss of the overall capacity. The objective is to maximize the sum of the items utility value, minus the fixed costs of the compartments. This dissertation presents two solving methods. The first approach is a heuristic method, which is a combination of two heuristics from the literature. The second approach is a Column Generation method, that apart from it gives a new upper bound to the Compartmentalized Knapsack Problem, in the end of the method the master problem was solved with the variables defined as integer, that supplies a feasible solution. In both methods, the mathematical non linear model is decomposed into two linear models, one generates the compartments, and the other selects them to compose the knapsack. The results obtained with these two approaches were compared with an upper bound and they showed very efficient

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.

Nos problemas de corte de itens irregulares, temos um conjunto de itens menores que devem ser alocados em objetos maiores (recipientes) de forma que estes estejam inteiramente contidos no recipiente e não se sobreponham. Neste trabalho, resolvemos um problema de corte e empacotamento de uma indústria que confecciona aventais e forros de luva, no qual deseja-se alocar uma lista de itens dentro de recipientes retangulares utilizando a menor quantidade de recipientes possível e minimizando o comprimento utilizado em cada recipiente. Para isto, utilizamos métodos exatos e heurísticos adaptados para o corte de aventais e forros de luva, com o objetivo de obter soluções de alta qualidade. Foram realizados experimentos computacionais que comprovaram a eficiência dos métodos de solução presentes neste trabalho. / In nesting problems, we have a set of small items that must be allocated into larger objects (containers) so that they are fully contained within the container and do not overlap. In this work, an apron and gloves lining industry cutting problem is solved, in which we want to allocate a list of items into rectangular containers using the smallest quantity of containers and minimizing the length used in each container. For this, we used exact and heuristic methods adapted for cutting aprons and glove liners, in order to obtain high quality solutions. Computational tests were performed and they show the efficiency of the solving methods presented in this work.

O Problema da Mochila Compartimentada é uma extensão do Problema da Mochila, em que os itens solicitados são divididos em classes, de modo que a mochila deve ser subdividida em compartimentos, os quais têm capacidades limitadas e são carregados com itens da mesma classe. Além disso, a construção de um compartimento tem um custo fixo e ocasiona uma perda no espaço da mochila. O objetivo consiste em maximizar a soma dos valores dos itens, descontado o custo fixo de inclusão de compartimentos. Neste trabalho, são abordados dois métodos de solução. A primeira abordagem é uma heurística, que consiste na combinação de duas heurísticas da literatura. A segunda abordagem é o método Geração de Colunas, que além de fornecer um novo limitante superior para o Problema da Mochila Compartimentada, ao final do método o problema mestre foi resolvido com as variáveis definidas como inteiras, obtendo uma solução factível. Em ambos os métodos, o modelo não-linear é decomposto em dois modelos lineares, no qual, um gera compartimentos e o outro os seleciona. Os resultados obtidos com as duas abordagens foram comparados com um limitante superior e se mostraram bastante satisfatórios / The Compartmentalized Knapsack Problem is an extension of the classical Knapsack Problem, where the ordered items are partitioned into classes, in such way that the knapsack must be divided into compartments, each one having limited capacity. In addition, the building of a compartment has a fixed cost and involves a loss of the overall capacity. The objective is to maximize the sum of the items utility value, minus the fixed costs of the compartments. This dissertation presents two solving methods. The first approach is a heuristic method, which is a combination of two heuristics from the literature. The second approach is a Column Generation method, that apart from it gives a new upper bound to the Compartmentalized Knapsack Problem, in the end of the method the master problem was solved with the variables defined as integer, that supplies a feasible solution. In both methods, the mathematical non linear model is decomposed into two linear models, one generates the compartments, and the other selects them to compose the knapsack. The results obtained with these two approaches were compared with an upper bound and they showed very efficient

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.