<p>The BMW Group uses load units for the transportation of assembly parts from the suppliers to the plants and for the internal material flow. This thesis analyses the advantageousness of introducing a load unit with a new size. There are three reasons why the current choice of containers is not sufficient. Firstly, there is a certain range of assembly parts that does not fit very well into the existing standard load units. Secondly, the average measurements of the parts have grown in the last years and thirdly, several of the existing containers leave unused space in the transportation vehicles.</p><p>For this the relevant costs and other, more qualitative aspects like the placing at the assembly line are considered. A container size is identified that offers a significant savings potential. For this potential the handling and transportation costs are identified as the relevant leverages. These costs are found to depend mainly on the utilisation degree of the load units.</p><p>To calculate the different utilisation degrees, a packing-algorithm in form of a four-block heuristic is applied and its results are extrapolated on the basis of existing BMW packing information. Thus, several assembly parts are identified that fit better into the suggested load unit than in the existing ones. These results are assessed using BMW’s expense ratios for handling and transportation. 80 parts are determined for which the migration to the new size would result in savings of more than 5,000 EUR for each per year in Dingolfing. Together, these parts offer a savings potential of about 0.9 million Euro.</p>

The BMW Group uses load units for the transportation of assembly parts from the suppliers to the plants and for the internal material flow. This thesis analyses the advantageousness of introducing a load unit with a new size. There are three reasons why the current choice of containers is not sufficient. Firstly, there is a certain range of assembly parts that does not fit very well into the existing standard load units. Secondly, the average measurements of the parts have grown in the last years and thirdly, several of the existing containers leave unused space in the transportation vehicles. For this the relevant costs and other, more qualitative aspects like the placing at the assembly line are considered. A container size is identified that offers a significant savings potential. For this potential the handling and transportation costs are identified as the relevant leverages. These costs are found to depend mainly on the utilisation degree of the load units. To calculate the different utilisation degrees, a packing-algorithm in form of a four-block heuristic is applied and its results are extrapolated on the basis of existing BMW packing information. Thus, several assembly parts are identified that fit better into the suggested load unit than in the existing ones. These results are assessed using BMW’s expense ratios for handling and transportation. 80 parts are determined for which the migration to the new size would result in savings of more than 5,000 EUR for each per year in Dingolfing. Together, these parts offer a savings potential of about 0.9 million Euro.

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.

Neste trabalho desenvolvemos o estudo da álgebra linear, secções cônicas e aplicações. Apresentamos os conceitos mais importantes da álgebra linear, estudando os espaços vetorias, subespaços vetoriais, matriz de mudança de base, transformações lineares e produto interno. O principal resultado do trabalho é o teorema espectral que fornece ferramentas para se estudar as secções cônicas não elementares, ou seja, aquelas nas quais uma parábola, elipse ou hipérbole são apresentadas com seus eixos não paralelos aos eixos coordenados do plano cartesiano. Uma vez de posse deste teorema é mostrado um processo prático no qual transformamos uma equação ax2 +bxy +cy2 +dx +ey + g = 0 na equação k1 (x\')2 + k2 (y\')2 + (dx1 + ey1) x\' + (dx2 + ey2) y\' + g = 0 sem o termo misto xy, onde após a eliminação deste, podemos deduzir a equação da cônica identificando assim esta curva. Apresentamos exemplos de cônicas com eixos paralelos e não paralelos aos coordenados do plano cartesiano e utilizamos o software geogebra para visualização. Também discutimos algumas aplicações das cônicas como trajetória de corpos celestes (planeta Terra e um cometa), princípio de reflexão da parábola mostrando o porquê das antenas e dos captadores de ondas sonoras serem parabólicos. Demonstramos um teorema que denominei de identificador de uma curva cônica pois com ele é possível classificar a cônica sem realizar o processo prático, apenas para isso identificamos através da equação ax2 +bxy + cy2 +dx + ey +g = 0, quais os valores de a;b e c e feito isto calculamos o discriminante b2 - 4ac, analisamos os sinais e a nulidade, ou seja, se é maior que zero, menor que zero ou igual a zero, assim é possível classificar a cônica. / The paper develops the study of linear algebra, conic sections and applications. I present the most important concepts of linear algebra, studying vector spaces, vector subspaces, base change matrix, linear transformations, internal product. The main result of the work is the spectral theorem, which provides tools to study the non-elementary conic sections, that is, those in which a parabola, ellipse or hyperbola are presented with their axes not parallel to the cartesian planes coordinate axes. Using this theorem we show a practical process in which we transform an equation ax2 +bxy + cy2 +dx +ey +g = 0 into the equation k1 (x\')2 +k2 (y\')2 + (dx1 +ey1) x\' (dx2 + ey2) y\' +g = 0 without the mixed term xy, where after its elimination we can deduce the conic equation thus identifying the curve we are looking for. I present examples of conic with parallel and non-parallel axes to the coordinates of the Cartesian plane and use the geogebra software for visualization. I discuss some applications of the conic as a trajectory of celestial bodies (planet Earth and a comet), principle of reflection of parabola showing why the antennas and sound wave pickups are parabolics. I demonstrate a theorem that I named the identifier of a conic curve, with it it is possible to classify the conic without realizing the practical process only for this. I identify through the equation ax2 +bxy + cy2 +dx + ey + g = 0, what are the values of a;b, and c and, with this done, I compute the discriminant b2 - 4ac and analyze the signs and the nullity, that is, if it is greater than zero, less than zero or equal to zero, therefore is possible to classify the conic.

O problema de empacotamento de itens irregulares com balanceamento da carga é encontrado no carregamento de aviões, caminhões e navios. O objetivo é empacotar itens irregulares utilizando o menor número de recipientes possível de forma que os recipientes estejam balanceados, que os itens não se sobreponham e estejam inteiramente contidos no recipiente. Neste trabalho, propomos três heurísticas bases com três variações cada para o problema com recipientes retangulares e irregulares. As heurísticas utilizam abordagens diferentes para representar os itens e para fazer o balanceamento. Uma das heurísticas utiliza malha para representação dos itens e faz o balanceamento dividindo o recipiente em quadrantes e revezando a alocação dos itens entre eles de forma que o balanceamento é feito de forma indireta. Tal heurística resolve o problema tanto para recipientes retangulares quanto irregulares. A segunda heurística utiliza a representação dos itens por polígonos e impossibilita a sobreposição de itens utilizando a técnica do nofit polygon. A heurística constrói a solução item por item, sem posições fixas e a cada item alocado, os itens são deslocados em direção ao centro de gravidade desejado do recipiente. Esta heurística resolve apenas problemas com recipientes retangulares. A última heurística é uma adaptação da heurística anterior para a resolução do problema com recipientes irregulares, de forma que o problema é resolvido em duas fases. Cada heurística base possui três variações cada, totalizando nove heurísticas. As heurísticas foram comparadas com outro trabalho da literatura e conseguiram melhorar os resultados para nove das dezenove instâncias testadas. / The irregular bin packing problem with load balancing is found in the loading of airplanes, trucks and ships. The aim is to use as few bins as possible to pack all the items so that all bins are balanced, items do not overlap and are fully contained in the bin. In this work, we propose three base heuristics with three variations each for the problem with rectangular and irregular bin. The three heuristics use different approaches to represent the items and to balance the bin. One of the heuristics uses a grid to represent the items and does the balancing by dividing the container into quadrants and alternating the allocation of items between them so that the balancing is done indirectly. Such heuristic solves the problem for both rectangular and irregular bins. The second heuristic uses the representation of items by polygons and uses the nofit polygon technique. The heuristic constructs the solution item by item, with no fixed positions and with each item allocated, the items are shifted towards the desired center of gravity of the bin. This heuristic only solves problems with rectangular bins. The last heuristic is an adaptation of the previous one to solve the problem with irregular bins, so that the problem is solved in two phases. Each base heuristic has three variations, totaling nine heuristics. The heuristics were compared with other work in the literature and managed to improve the results for nine of the nineteen instances tested.

This thesis deals with the placement of irregular shapes on a fixed width plane, which is a problem whose solution can be used, for example, when placing sewing patterns on fabric so that its length is as small as possible. A continuity of shapes depending on ma- terial patterns are also taken into account. The thesis uses evolutionary algorithms with heuristic functions that assign positions to individual shapes depending on the individual being developed by the relevant evolution. Patterned fabrics are treated differently using special heuristic functions types that are able to adjust the layout. 1

[pt] Essa dissertação aborda o problema da elaboração de Plano de Estivagem de Placas de Aço, em navios, para o mercado externo. O Plano de Estivagem é muito importante para agilizar o processo de carregamento de navios e reduzir o laytime utilizados por esses no porto. O estudo de caso é na Companhia Siderúrgica de Tubarão (CST). A partir do levantamento dos procedimentos atualmente utilizados, foi desenvolvida uma heurística para elaboração de Planos de Estivagem no Terminal de Produtos Siderúrgicos do Porto de Praia Mole. A heurística desenvolvida foi dividida em duas etapas. Na primeira etapa, as placas de aço são distribuídas pelos porões do navio respeitando a capacidade do mesmo e, na segunda etapa, é determinado o layout das placas em cada porão. A heurística proposta foi implementada em um ambiente de programação C. / [en] This thesis considers the problem of elaborating Slabs Stowage Plan elaboration in ships, for international markets. The stowage plan is very important for shipment agility and reduction of the laytime used by the ships in the port. A case study was developed at Companhia Siderúrgica de Tubarão (CST). Based on the procedure used today, a heuristic solution is proposed for Slab Stowage Plan on the Steel Products Terminal (TPS) located at the port of Praia Mole. The heuristic was divided in two parts. In the first part, respecting holds capacities, slabs are distributed along the holds and in the second part the slabs layout in each hold is determinate. The proposed heuristc was implemented in a C programming language.

Orientador: Rubén Augusto Romero Lázaro / Resumo: Neste trabalho apresenta-se uma nova meta-heurística, o Algoritmo Genético Evolucionário Especializado (AGE-E) para resolver uma das categorias dos Problemas de Carregamento de Contêiners, objeto de estudo que pertence à otimização, na Pesquisa Operacional. Considera-se a existência de múltiplos contêiners de iguais dimensões que permitem o carregamento completo da carga disponível em um contexto de transporte industrial. Esta carga é composta por caixas de sortimento fortemente hete-rogêneo e que permite a rotação em qualquer dasseis possibilidades, tornando o problema ainda mais complexo, e, porisso,menos estudado na literatura. Uma revisão bibliográfica é também apresentada, contendo uma visão geral das classificações do problema e, em particular, um estudo aprofundado sobre algoritmos genéticos. A implementação do AGE-E foi realizada, e os resultados computacionais foram comparados com as melhores soluções já apresentadas na literatura, demonstrando o potencial do AGE-E para estudosfuturos. / Doutor

Submitted by BRUNA DE LIMA ALCANTARA KITAMURA null (brunakitamura@yahoo.com.br) on 2017-10-30T20:10:34Z No. of bitstreams: 1 TESE-FINAL-BRUNA-G-LIMA.pdf: 4015697 bytes, checksum: cb6eb178262689807dbc777ab5d4d4dd (MD5) / Approved for entry into archive by LUIZA DE MENEZES ROMANETTO (luizamenezes@reitoria.unesp.br) on 2017-11-09T18:45:51Z (GMT) No. of bitstreams: 1 lima_bg_dr_ilha.pdf: 4015697 bytes, checksum: cb6eb178262689807dbc777ab5d4d4dd (MD5) / Made available in DSpace on 2017-11-09T18:45:51Z (GMT). No. of bitstreams: 1 lima_bg_dr_ilha.pdf: 4015697 bytes, checksum: cb6eb178262689807dbc777ab5d4d4dd (MD5) Previous issue date: 2017-09-06 / Neste trabalho apresenta-se uma nova meta-heurística, o Algoritmo Genético Evolucionário Especializado (AGE-E) para resolver uma das categorias dos Problemas de Carregamento de Contêiners, objeto de estudo que pertence à otimização, na Pesquisa Operacional. Considera-se a existência de múltiplos contêiners de iguais dimensões que permitem o carregamento completo da carga disponível em um contexto de transporte industrial. Esta carga é composta por caixas de sortimento fortemente hete-rogêneo e que permite a rotação em qualquer dasseis possibilidades, tornando o problema ainda mais complexo, e, porisso,menos estudado na literatura. Uma revisão bibliográfica é também apresentada, contendo uma visão geral das classificações do problema e, em particular, um estudo aprofundado sobre algoritmos genéticos. A implementação do AGE-E foi realizada, e os resultados computacionais foram comparados com as melhores soluções já apresentadas na literatura, demonstrando o potencial do AGE-E para estudosfuturos. / This work presents a new meta-heuristic, the Specialized Evolutionary Genetic Algorithm (AGE-E), which solves one of the categories of Container Loading Problems, object of study that belongs to Optimization, within the Operational Research. It’s considered the existence of multiple containers ofthe equal dimensionsthat promote the full loading of the availablecargoinindustrial transportation context. Thisload is composed ofstrongly heterogeneous assortment to the boxes, and allows rotation in any of the six possibilities, making the problem even more complex, and therefore less studied in the literature. A bibliographic review is also presented, containing an overview of the classifications of the problem and, in particular, an deepened study on genetic algorithms. The implementation of AGE-E was performed, and the computational results were compared with the best solutions already determined by the bibliography, demonstrating the potentialofAGE-E for future studies.

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