Return to search

Métodos de resolução para o problema de empacotamento de cilindros em níveis / Solution methods for the cylinder packing problem in levels

O problema de empacotamento de cilindros em níveis é comumente encontrado nas indústrias de cerâmica. Solucionar este problema significa encontrar o posicionamento ideal dos itens cerâmicos cilíndricos dentro do forno de modo que o menor número de fornos seja utilizado e os itens não se sobreponham e obedeçam aos limites do recipiente. Também é considerado o uso de prateleiras para que haja uma melhor ocupação do espaço do forno. Propomos uma formulação matemática não-linear inteira mista e métodos de resolução heurísticos e exato para o problema. Os métodos heurísticos consistem em escolher uma estratégia de ordenação, posicionar os itens em cada nível por meio da heurística Bottom-Left e posicionar os níveis no recipiente utilizando as estratégias Best-Fit, First-Fit ou Worst-Fit. Ao total, propomos seis variações heurísticas para resolução do problema. O método exato consiste em estimar o número de níveis e recipientes necessários e resolver o problema por meio de um solver de otimização global. Os experimentos computacionais foram realizados para um conjunto de instâncias que criamos. Os resultados mostraram que o método exato é capaz de encontrar a solução ótima em um curto período de tempo para instâncias de pequeno porte e que as heurísticas são capazes de resolver o problema em um tempo computacional baixo, para instâncias de pequeno, médio e grande porte, sendo que algumas heurísticas apresentam melhor desempenho que outras. / The cylinder packing problem in levels is commonly found in ceramic industries. Solving this problem consists in finding the ideal position of items inside furnaces so that the minimum number of furnaces is used and the items do not overlap and obeying furnaces size. In this case, it is possible to add levels to the furnace. We proposed a non-linear integer mixed mathematical model for the problem and heuristic and exact resolution methods. Heuristic methods consist of choosing a sorting strategy, packing the items at each level by a Bottom-Left heuristic, and positioning the levels in the furnace using Best-Fit, First- Fit or Worst-Fit strategy. In total, it is proposed six heuristic variations to solve the problem. The exact method consists in solving the problem by a global optimization solver. The computational experiments were run over a set of new proposed instances. The results have shown that the exact method is able to find an optimal solution in a short period of time for small instances and that the proposed heuristics are capable of solving the problem in a low computational time for small, medium and large instances. Furthermore, some of them have performed better than others.

Identiferoai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-29102018-113809
Date21 March 2018
CreatorsRaínne Florisbelo Gonçalves
ContributorsMarina Andretta, Silvio Alexandre de Araujo, Kelly Cristina Poldi, Maristela Oliveira dos Santos
PublisherUniversidade de São Paulo, Ciências da Computação e Matemática Computacional, USP, BR
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Sourcereponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0024 seconds