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.

Este trabalho propõe a aplicação de dois diferentes conceitos para a resolução do Problema de Estivagem de Unidades de Celulose - PEUC, que de acordo com Ribeiro e Lorena (2008) pode ser definido como um problema que busca alocar a máxima quantidade de unidades de celulose ao porão de cargas de um dado navio, respeitando as restrições físicas de dimensões, de posicionamento, de não-sobreposição das unidades e de capacidade máxima do porão do navio. Esse tipo de problema se encaixa, no contexto da Pesquisa Operacional, na classe de Corte e Empacotamento (Cutting and Packing - C&P) e pode ser classificado, de acordo com a tipologia de Wäscher, Haußner e Schumann (2007), como sendo um Single Large Object Placement Problem (SLOPP). Em última instância, o objetivo do PEUC é definir o melhor plano de estivagem para o carregamento de unidades de celulose em um dado porão de um navio, maximizando a área ocupada pelas unidades de celulose. Trata-se de um problema NP-Completo (DOWSLAND; DOWSLAND, 1992; BISCHOFF; WÄSCHER, 1995; MALAGUTI; DURáN; TOTH, 2013) e por isso foram propostas duas abordagens para buscar a melhoria das soluções encontradas e/ou redução do tempo computacional necessário. As abordagens propostas, o Modelo Matemático Modificado e o Método Iterativo de Solução, apresentaram bons resultados para instâncias experimentais, confirmando a efetividade de suas aplicações. Os resultados foram melhores tanto na qualidade das soluções (ocupação total do objeto), como no tempo computacional necessário. Também foram avaliadas quatro instâncias reais, com a comparação dos planos de estivagem resultantes da aplicação dos modelos matemáticos com os planos reais, elaborados manualmente por especialistas. Em três dos quatro casos os resultados das abordagens aqui propostas se mostraram melhores que os planos reais. / This work proposes the application of two different concepts to tackle the Woodpulp Stowage Problem - WSP, that according to Ribeiro e Lorena (2008) can be defined as a problem that seeks the allocation of the maximum quantity of woodpulp units inside the hold of a cargo vessel, always respecting the physical constraints, positioning constraints, non-overlapping of units and also the hold capacity. This kind of problem fits, in the context of Operational Research, into the class of Cutting & Packing and can be classified, according to Wäscher, Haußner e Schumann (2007) typology, as a Single Larga Object Placement Problem (SLOPP). Ultimately the objective of the WSP is to define the best stowage plan for the loading of woodpulp units inside a given hold of a given cargo vessel, maximizing the total area occupied by the woodpulp units. As it\'s a NP-Complete problem (DOWSLAND; DOWSLAND, 1992; BISCHOFF; WÄSCHER, 1995; MALAGUTI; DURáN; TOTH, 2013) two approaches were proposed to improve the quality of the resulting solutions and/or the reduction of the computational time needed. The proposed approaches, the Modified Mathematical Model and the Iterative Solution Method, showed good results for experimental instances, confirming the effectiveness of these approaches. The results were better regarding the quality of the solutions (total occupied area of the object) and also regarding the computational time needed. Also, four real instances were evaluated, comparing the results of the mathematical models with the real stowage plans, manually created by specialists. In three of the four instances, the proposed approaches showed better results than the real stowage plans.

Os problemas de corte e empacotamento são frequentes em diferentes processos produtivos, por exemplo, na produção de roupas, de calçados, de peças metálicas e de móveis. Seu objetivo mais frequente e a minimização do desperdício de matéria-prima. No entanto, em algumas situações, o problema de determinação do caminho de corte e fundamental para eciência do planejamento da produção. Este problema consiste em determinar a trajetória de corte que minimize, por exemplo, o tempo total de corte de um plano de corte previamente estabelecido. Devido a existência de poucas abordagens para este problema, nosso objetivo e propor modelos matemáticos para resolver o problema de determinação do caminho de corte. Além disso, uma variação do problema que considera a utilização de grafos dinâmicos também é abordada. Os resultados obtidos são comparados com resultados da literatura. / Cutting and packing problems are frequent in dierent productive process, for example, in the garment, shoe, metallic pieces and furniture production. Its most common objective is the minimization of the raw material waste. However, in some situations, the cutting path determination problem is fundamental to the eciency of the production planning. This problem consists in determining the cutting trajectory that minimizes, for example, the total cutting time of a previously established cutting plane. Due to the few existing approaches to this problem, our objective is to propose mathematical models to solve the cutting path determination problem. Furthermore, a variation of the problem that considers the use of dynamic graphs is also adressed. The obtained results are compared with those from the literature.

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.

Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-08T10:15:19Z (GMT). No. of bitstreams: 1 Araujo_OlintoCesarBasside_D.pdf: 1592360 bytes, checksum: 71dd5f2565cd93013aa027127157c442 (MD5) Previous issue date: 2006 / Resumo: A adoção de contêineres em grande escala tornou possível o desenvolvimento do transporte multimodal. Atualmente, carregamento de caixas em contêineres é uma importante atividade em empresas que têm no transporte de carga um fator logístico de alto custo. Este trabalho apresenta o desenvolvimento e aplicação de metaheurísticas com memória adaptativa para a resolução de problemas de corte e empacotamento tridimensional, bem como a integração destes com o problema de roteamento de veículos. Mais especificamente, são tratados os problemas de carregamento de contêiner, bin packing tridimensional e roteamento de veículos capacitados com restrições de empacotamento tridimensional. Uma nova abordagem, baseada em cubóides de tamanho variável, é utilizada para calcular os padrões de carregamento tridimensional em todos os métodos propostos. Restrições de orientação, estabilidade, centro de gravidade, projeção da base de apoio e múltiplos destinos são consideradas. Extensivos testes computacionais são realizados para demonstrar o desempenho das abordagenspropostas / Abstract: The wide-scale adoption of the containers made the development of the multimodal transport possible. Nowadays, shipment of boxes in containers is an important activity for companies that have in the load transport a logistic factor of high cost. This work presents the development and the application of metaheuristics with adaptive memory in order to solve three-dimensional cutting and packing problems, as well as their integration with the vehicle routing problem. In particular, problems of container loading, three-dimensional bin packing and vehicle routing with three-dimensional packing constraints are considered. Furthermore, a new approach based on maximal cuboids that fit in given empty spaces is used to calculate the packing patterns in the proposed methods. Constrains on orientation, stability, center of gravity, overhang and multiple destination are considered. Extensive computational experiments are carried out to demonstrate the performance of the proposed approaches / Doutorado / Automação / Doutor em Engenharia Elétrica

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.

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.

Based on an application in the field of server consolidation, we consider the one-dimensional cutting stock problem with nondeterministic item lengths. After a short introduction to the general topic we investigate the case of normally distributed item lengths in more detail. Within this framework, we present two lower bounds as well as two heuristics to obtain upper bounds, where the latter are either based on a related (ordinary) cutting stock problem or an adaptation of the first fit decreasing heuristic to the given stochastical context. For these approximation techniques, dominance relations are discussed, and theoretical performance results are stated. As a main contribution, we develop a characterization of feasible patterns by means of one linear and one quadratic inequality. Based on this, we derive two exact modeling approaches for the nondeterministic cutting stock problem, and provide results of numerical simulations.