Master's Dissertation
DOI
https://doi.org/10.11606/D.55.2018.tde-29102018-113809
Document
Author
Full name
Raínne Florisbelo Gonçalves
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Carlos, 2018
Supervisor
Committee
Andretta, Marina (President)
Araujo, Silvio Alexandre de
Poldi, Kelly Cristina
Santos, Maristela Oliveira dos
Title in Portuguese
Métodos de resolução para o problema de empacotamento de cilindros em níveis
Keywords in Portuguese
Empacotamento de cilindros
Empacotamento em níveis
Métodos heurísticos
Modelagem matemática
Problemas de empacotamento
Abstract in Portuguese
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.
Title in English
Solution methods for the cylinder packing problem in levels
Keywords in English
Cylinder packing problem
Heuristic methods
Level packing
Mathematical modelling
Packing problems
Abstract in English
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.
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2018-10-29