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.

O concreto é o material de construção mais utilizado e nos últimos anos, estudos têm sido desenvolvidos em busca de materiais com desempenho mecânico e durabilidade superiores, com redução do consumo de cimento. Nesse contexto, tem-se o estudo do empacotamento de partículas associado à dosagem de concretos, produzindo estruturas mais densas e compactas, com melhor consumo energético. Basicamente, o empacotamento de partículas consiste em otimizar composições empregando partículas de diferentes tamanhos, promovendo o refinamento dos poros e, eventualmente, reduzindo o volume de pasta necessário para envolver as partículas da mistura. O empacotamento de partículas permite uma evolução nas propriedades do concreto, além de promover um benefício ambiental por meio da utilização de resíduos e subprodutos industriais, redução de emissões poluentes e economia de energia, mediante a redução do consumo de cimento na mistura. Diante disto, o presente trabalho tem por objetivo aplicar o conceito de empacotamento de partículas na otimização de traços de concretos convencionais e de alta resistência. Para isso, realizou-se inicialmente um estudo de dosagem, sendo determinados traços de referência pela metodologia tradicional. Aplicando o modelo de empacotamento de Alfred, foi determinado o coeficiente de distribuição de cada mistura e, então, os traços foram otimizados mantendo-se o mesmo coeficiente, sendo comparadas as propriedades dos concretos otimizados com propriedades das misturas de referência. Verificou-se que nas misturas otimizadas não foi possível obter a trabalhabilidade desejada, sendo necessário ajustar o teor de aditivo a fim de manter a mesma consistência. No estado endurecido, os concretos otimizados apresentaram desempenho físico e mecânico superior aos concretos dosados pela metodologia tradicional. Os ensaios não destrutivos apenas permitiram verificar a evolução com o tempo do módulo de elasticidade dinâmico e da porosidade, visto que a mudança da composição das misturas influencia diretamente no módulo e na velocidade de propagação da onda no material. Por fim, foi possível verificar a sustentabilidade dos concretos otimizados, que apresentaram índice de intensidade de ligante mais eficiente que os concretos de referência, reforçando a importância desse trabalho. / Concrete is the most widely used construction material and in recent years, studies have been developed in search of materials with higher mechanical performance and durability, with reduced cement consumption. In this sense, the study of particle packing associated to the mix design of concrete, producing denser and more compact structures, with better energy consumption, is being studied. Basically, particle packing consists of optimizing compositions employing particles of different sizes, promoting pore refinement and possibly reducing the volume of cement paste required to involve the particles in the mix. The particle packing allows an evolution in concrete\'s properties, besides promoting an environmental benefit using industrial wates and by-products, reduction of polluting emissions and energy saving, by reducing the consumption of cement in the mix. In this view, the present research aims to apply the concept of particle packing in the optimization of conventional and high strength concretes mix design. For this, a mix design study was carried out initially, being determined reference concretes mix design by the traditional methodology. Applying the Alfred\'s packing model, the distribution coefficient of each mix was determined and concretes mix design were optimized by keeping the same coefficient, and the properties of the optimized concretes were compared with the properties of the reference mixtures. It was verified that, in optimized mixtures, it was not possible to get the desired workability and it was required to fit the chemical admixture content in order to keep the same consistency. In the hardened state, the optimized concrete showed physical and mechanical performance higher than concretes designed by the traditional methodology. The non-destructive tests only allowed to verify the evolution of the dynamic elasticity modulus and the porosity with time, since the change of the composition of the mixtures directly influences the modulus and the wave propagation speed in the material. Finally, it was possible to verify the sustainability of the optimized concretes, which presented a binder intensity index more efficient than the reference concrete, reinforcing the importance of this research.

[pt] O Método dos Elementos Discretos (DEM) com base em esferas pode fornecer aproximações para diversos fenômenos físicos complexos, tanto em escala micro quanto macro. Normalmente uma simulação DEM começa com um arranjo de partículas esféricas no interior de um determinado recipiente. Para domínios gerais a criação deste pacote de esferas pode ser complexo e demorado, especialmente se ele deve respeitar requisitos de precisão e de estabilidade da simulação. O objetivo deste trabalho é estender uma solução de empacotamento de discos 2D para gerar conjuntos aleatórios compostos por partículas esféricas não sobrepostas. O algoritmo construtivo proposto utiliza a técnica de frente de avanço, onde as esferas são inseridas uma a uma no pacote, de acordo com uma estratégia gulosa baseada nas partículas previamente inseridas. A técnica de frente de avanço requer a existência de um conjunto inicial de esferas que definem a fronteira do recipiente. Outra extensão importante proposta aqui é uma generalização do algoritmo para lidar com objetos arbitrários definidos por uma malha triangular qualquer. Este trabalho apresenta também alguns resultados que permitem algumas conclusões e sugestões de trabalhos futuros. / [en] The Discrete Element Method (DEM) based on spheres can provide acceptable approximations to many complex physical phenomena both in micro and macro scale. Normally a DEM simulation starts with an arrangement of spherical particles pack inside a given container. For general domains the creation of the sphere pack may be complex and time consuming, especially if the pack must comply with accuracy and stability requirements of the simulation. The objective of this work is to extend a 2D disk packing solution to generate random assemblies composed by non-overlapping spherical particles. The constructive algorithm, presented here, uses the advancing front strategy where spheres are inserted one-by-one in the pack, according to a greed strategy based on the previously inserted particles. Advance front strategy requires the existence of an initial set of spheres that defines the boundary of the pack region. Another important extension presented here is the generalization of algorithm to deal with arbitrary objects defined by a triangular boundary mesh. This work presents also some results that allow for some conclusions and suggestions of further work.

Presente em diversos processos industriais, que variam desde pequenas confecções até grandes indústrias da área de metal-mecânica, os problemas de empacotamento visam definir o posicionamento de itens menores sobre objetos maiores minimizando, frequentemente, a perda de material utilizado. O problema de empacotamento de peças irregulares em faixas, estudado nesta pesquisa, tem como principal característica, e obstáculo, possuir itens irregulares. Em algumas indústrias surge, após a determinação do empacotamento, um segundo problema: a determinação do caminho mínimo de corte. Embora a solução do primeiro influencie fortemente a resolução do segundo, não é de nosso conhecimento que existam, até o momento, estratégias que integrem esses problemas. Neste trabalho, são propostos dois modelos integrados de empacotamento de peças irregulares e caminho de corte. O primeiro modelo busca minimizar o caminho de corte entre as peças considerando um ponto fixo de início de corte (vértice fixo) para cada peça, enquanto que o segundo considera o corte por peça a partir de um vértice qualquer das peças. Testes computacionais mostram que é vantajosa a integração dos problemas contudo, como ambos são problemas de difícil solução, o problema integrado é pelo menos tão difícil quanto os problemas isolados, logo apenas instâncias de pequeno porte foram resolvidas de forma exata. Uma matheurística, baseada no algoritmo genético de chaves aleatórias viciadas, é proposta para o problema de empacotamento de peças irregulares em faixa em domínio contínuo e, em seguida, estendida para o problema integrado. Os resultados são promissores, pois a matheurística consegue encontrar solução para instâncias que não haviam sido resolvidas através dos modelos integrados previamente propostos. / Having great applicability in industries, ranging from small clothing industries to large metal mechanic ones, packing problems aim to determine the positioning of small pieces over a large object minimizing, for instance, raw material waste. The main characteristic and obstacle of the irregular strip packing problem, studied in this research, is the irregular shape of its pieces. In some industries, after a layout of pieces has been defined, a second problem arises: the cutting path determination problem. Although the solution of the first strongly influences the resolution of the second, to the best of our knowledge, there are no strategy to integrate these problems. Here, we propose two irregular strip packing and cutting path integrated models. The first one minimizes the cutting path between the pieces considering that the cutting starts at a fixed vertex for each piece, while the second considers the cutting start point in any vertex of the pieces. Computational tests show that it is advantageous to integrate the problems, however, as both are difficult to solve, the integrated one is at least as difficult as each of them, so only small instances were solved to optimality. A matheuristic, based on the biased random-key genetic algorithm, is proposed for the continuos irregular strip packing problem and then extended to the integrated problem. The results are promising, the matheuristics is able to find solution for instances that had not been solved through the previously proposed integrated models.

O número de contato do Rn (em inglês, kissing number) é o maior número de esferas de raio unitário e interiores dois-a-dois disjuntos que podem tocar simultaneamente uma esfera de raio unitário central. Nesta dissertação estudamos métodos que limitam o tamanho de tais configurações através de técnicas de otimização, como dualidade e programação semidefinida. O principal resultado obtido foi o cálculo de melhores limitantes para o número de contato nas dimensões 9 a 23; o que foi possível graças à exploração de simetrias dos polinômios presentes no limitante proposto por Bachoc e Vallentin (2008), levando à consideração de programas semidefinidos menores. Por fim, o limitante estudado é estendido para uma classe mais geral de problemas. / The kissing number of Rn is the maximum number of pairwise-nonoverlapping unit spheres that can simultaneously touch a central unit sphere. In this thesis we study methods to bound from above the size of such configurations using optimization techniques, like duality and semidefinite programming. The main result achieved is the computation of better bounds for the kissing number in dimensions 9 to 23; a result possible due to the exploitation of symmetries in the polynomials present in the bound proposed by Bachoc and Vallentin (2008), leading to the consideration of smaller semidefinite programs. Finally, the studied bound is extended to a bigger class of problems.

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.

Nesta tese, estudamos o problema de Empacotamento de Bicliques. Um biclique é um grafo bipartido completo. No problema de Empacotamento de Bicliques são dados um inteiro k e um grafo bipartido G e deseja-se encontrar um conjunto de k bicliques, subgrafos de G, dois a dois disjuntos nos vértices, tal que a quantidade total de arestas dos bicliques escolhidos seja máxima. No caso em que k=1, temos o problema de Biclique máximo. Esses dois problemas possuem aplicações na área de Bioinformática. Mantemos neste trabalho um enfoque prático, no sentido de que nosso interesse é resolver instâncias desses dois problemas com tamanho razoavelmente grande. Para isso, utilizamos técnicas de Programação Linear Inteira. Para avaliar os métodos propostos aqui, mostramos resultados de experimentos computacionais feitos com instâncias vindas de aplicações e também com instâncias geradas aleatoriamente. / In this thesis, we study the Biclique Packing problem. A biclique is a complete bipartite graph. In the Biclique Packing problem we are given an integer k and a bipartite graph G and we want to find a set of k vertex disjoint bicliques of G, such that the total number of biclique\'s edges is maximum. When k=1, we have the Maximum Biclique problem. These two problems have applications in Bioinformatics. In this work we keep a practical focus, in the sense that we are interested in solving large size instances of these problems. To tackle these problems, we use Integer Linear Programming techniques. In order to evaluate the methods proposed here, we show results of computational experiments carried out with practical application\'s instances and also with randomly generated ones.

Os problemas de corte e empacotamento são muito comuns nas indústrias e na logística. Dado um conjunto de N itens com diferentes pesos e um conjunto de M contentores com capacidade C, o problema de empacotamento unidimensional consiste em determinar o menor número de contentores a serem utilizados para alocar todos os itens respeitando a restrição de capacidade dos contentores. Nesse estudo pretende-se resolver o problema com instâncias benchmark da literatura, por meio de sessenta heurísticas diferentes, que são comparadas a quatro limitantes inferiores propostos na literatura com o intuito de avaliar a qualidade da solução heurística. Quatro limitantes inferiores e dez heurísticas construtivas diferentes foram programados em C++ num mesmo ambiente computacional, permitindo sua comparação tanto em termos de qualidade das soluções, quanto em termos dos tempos de processamento. Uma heurística simples de troca de itens entre contentores chamada Diferença-de-Quadrados foi proposta para melhorar as soluções iniciais do problema. A metaheurística simulated annealing foi acionada para melhorar a solução inicial quando o limitante inferior não foi atingido. Os parâmetros dos simulated annealing foram determinados com os dados das instâncias de forma diferente da utilizada na literatura. As combinações entre as dez soluções iniciais, a heurística Diferença-de-Quadrados e o simulated annealing geraram um conjunto de sessenta heurísticas diferentes. Os resultados mostraram que o algoritmo proposto é eficiente para resolver o problema com tempos de processamento adequados a tomada de decisão. / Cutting and packing problems are very common in industries and logistics. Given a set of N items with different weights and a set of M bins with full capacity C, the one-dimensional bin packing problem consists of determining the smallest number of bins capable to allocate all items respecting the capacity constraint of the bins. that impose that the sum of the weights of the items allocated to the bin is less than or equal to their capacity. In this study we intend to solve the problem with benchmark instances of the literature, by means of sixty different heuristics, which are compared to four lower bounds proposed in the literature in order to evaluate the quality of the heuristic solution. Four lower bounds and ten different constructive heuristics were programmed in C++ in the same computational environment, allowing their comparison both in terms of the quality of the solutions and in terms of processing times. A simple heuristic of item exchange between bins called Difference-of-Squares was proposed to improve the initial solutions of the problem. The simulated annealing metaheuristic was triggered to improve the initial solution when the lower bounds was not reached. The parameters of the simulated annealing were determined with the data of the instances differently from that used in the literature. The combinations of the ten initial solutions, the Difference-of-Squares heuristic and the simulated annealing generated a set of sixty different heuristics. The results showed that the proposed algorithm is efficient to solve the problem with adequate processing times for decision making.

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.

Este trabalho apresenta o uso de planejamento granulométrico na preparação e caracterização de suspensões concentradas de alumina em meio aquoso, que posteriormente deverão ser utilizadas para a conformação por colagem em fitas - processo de tape casting. A suspensão foi preparada utilizando-se duas ou mais distribuições granulométricas diferentes na sua formulação, a fim de promover a otimização do empacotamento de partículas. As condições para estabilização das suspensões preparadas foram obtidas por meio de estudos de comportamento reológico e através de curvas isotermas de adsorção, por meio de medidas de viscosidade em função da concentração de aditivo dispersante e de medidas de mobilidade eletroforética dinâmica, respectivamente. Os valores mostram a qualidade dos dados obtidos nas simulações quanto aos valores de IPS calculados, em função de uma quantidade de água pré estabelecida de 35% em volume, ficando em média próximo do valor de 0,150µm, para as formulações simuladas. Desta forma foi possível preparar uma suspensão concentrada com empacotamento de partículas otimizado podendo chegar a um valor máximo de 60% em volume de sólidos, com possibilidades de minimizar os possíveis efeitos adversos da retração durante a secagem e queima dos filmes. / This paper presents the use of grain size in the pack planning for preparation and characterization of a concentrated suspension of alumina in aqueous medium, which subsequently will be used for the conformation by tape casting process. The suspension was prepared using two or more different particle size distributions in the formulation to promote the optimization of particle packing. The definitions of stability and rheological behavior of dispersion curves were made by adsorption isotherms, by measuring electrokinetic mobility and viscosity curves as a function of concentration of additives, respectively. The results show the quality of data obtained in the simulations as the maximum values of IPS for each formulation. Then, it is possible to prepare a concentrated suspension with optimized particle packing and may reach a maximum value of 60% by volume of solids, with opportunities to minimize the possible adverse effects of shrinkage during drying of the films.