O problema de empacotamento consiste em empacotar, ortogonalmente e sem sobreposição, um conjunto de itens na menor quantidade de caixas possível. As versões bi e tridimensional do problema generalizam o caso bem conhecido unidimensional, um dos primeiros problemas da classe NP-Difícil. Esta dissertação estuda a versão clássica dos problemas de empacotamento bidimensional e tridimensional, considerando os casos com itens de orientação fixa e com rotação. O problema tem várias aplicações industriais, e o caso de orientação fixa se relaciona a outros problemas complexos como os de corte, repartição e agendamento. Várias heurísticas são propostas e combinadas com metaheurísticas para resolver instâncias de grande porte do problema com soluções de boa qualidade. Extensivos testes computacionais são realizados com 820 instâncias padrões utilizadas em vários trabalhos na literatura. Os resultados computacionais obtidos pela melhor abordagem deste trabalho, denominada BRKGA-VCD, demonstram que o método proposto obtém soluções de qualidade superior ou equivalente aos algoritmos estado da arte encontrados na literatura, melhorando o melhor resultado conhecido para este conjunto de instâncias
The bin packing problem consists of orthogonally packing a set of boxes into the minimum number of bins without overlap. The two and three-dimensional bin packing problem generalizes the well known unidimensional bin packing problem, which was characterized as NP-Hard in the beginning of NP-C Theory. This dissertation studies the classic versions of two and three-dimensional case of bin packing with fixed and non-fixed orientated boxes. The bin packing problem has many industrial applications and relates to other complex problems like cutting, repartitioning and scheduling. This work proposes heuristics combined with metaheuristics to devise good quality solutions for large-scale instances. This work presents extensive computational tests with 820 standard literature instances. The computational results devised by the best algorithm proposed, called BRKGA-VCD, demonstrate that this method produces equivalent or better solution compared to state-of-art algorithms found in the literature, improving the overall best known solution quality for this set of instances
