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.

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.

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.

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.

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.

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.

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.