Approximation algorithms for the strip packing problem with unloading constraints

Orientadores: Eduardo Candido Xavier, Flávio Keidi MiyazawaDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: 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 consideradasAbstract: 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 instancesMestradoTeoria da ComputaçãoMestre em Ciência da Computaçã