DOI
https://doi.org/10.11606/D.3.2018.tde-25072018-082433
Documento
Autor
Nome completo
Leandro Maciel Turi
E-mail
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2018
Mendes, André Bergsten (Presidente)
Brinati, Marco Antonio
Leite, Laura Silvia Bahiense da Silva

Título em português
Métodos heurísticos para resolução de problemas de empacotamento unidimensional.
Palavras-chave em português
Empacotamento e corte
Heurística
Limitantes inferiores
Logística
Resumo em português

Título em inglês
Heuristic methods for solving one-dimensional bin packing problems.
Palavras-chave em inglês
Bin packing problem
Heuristic method
Lower bounds
Simulated annealing
Resumo em inglês
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.

AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2018-07-26

AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores.
CeTI-SC/STI
© 2001-2024. Biblioteca Digital de Teses e Dissertações da USP.