Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/275757
Type: TESE
Title: Algoritmos de aproximação para problemas de empacotamento em faixa com restrições de descarregamento
Title Alternative: Approximation algorithms for the strip packing problem with unloading constraints
Author: Silveira, Jefferson Luiz Moisés da, 1986-
Advisor: Xavier, Eduardo Candido, 1979-
Abstract: Resumo: Neste trabalho estudamos problemas de empacotamento com restrições de descarregamento considerados NP-difíceis. Estes problemas possuem aplicações nas áreas de logística e roteamento. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes para resolver tais problemas. Uma das abordagens consideradas para tratar tais problemas é a de algoritmos de aproximação, que são algoritmos eficientes (complexidade de tempo polinomial) e que geram soluções com garantia de qualidade. Estudamos técnicas para o desenvolvimento de algoritmos aproximados e também alguns algoritmos para problemas de empacotamento online que podem ser utilizados na resolução do problema estudado. Propomos também algumas heurísticas para o problema e, além disto, provamos que duas destas heurísticas possuem garantias de aproximação com fatores constantes. Realizamos testes computacionais com estes algoritmos propostos. Dentre estes, a heurística GRASP foi a que obteve melhores resultados para as instâncias de teste consideradas

Abstract: In this work we study some NP-hard packing problems with unloading constraints. These problems have applications in logistics and routing problems. Assuming P ? NP, there are no efficient algorithms to solve these problems. On way to deal with these problems is using approximation algorithms, that are efficient algorithms (polynomial time complexity) that produce solutions with quality guarantee. We study techniques used in the development of approximation algorithms and some algorithms for online packing problems which can be used to solve the considered problem. We propose some heuristics for the problem and prove that two of them have constant approximation guarantees. We also perform computational tests with the proposed algorithms. Among them, the GRASP heuristic achieved the best results on the considered instances
Subject: Algoritmos
Problemas de empacotamento
Language: Português
Editor: [s.n.]
Date Issue: 2011
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Silveira_JeffersonLuizMoisesda_M.pdf1.48 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.