Dissertação de Mestrado

O Problema de Empacotamento Unidimensional é um problema de otimização combinatorial para o qual a obtenção de soluções exatas é uma tarefa difícil. A maioria dos algoritmos conhecidos para encontrar soluções exatas para estes problemas consome um grande tempo de processamento, o que se torna inviável quando o número de variáveis é grande. Assim, o maior esforço tem se concentrado no desenvolvimento e análise de algoritmos mais rápidos (heurísticas) que resultam em boas soluções e aproximadas na maioria das vezes. Neste trabalho é apresentado um método de solução para a otimização do Problema de Empacotamento Unidimensional, utilizando algumas heurísticas e aplicando a técnica de Times Assíncronos (A-Teams), uma rede computacional caracterizada por ser fortemente cíclica, possuir fluxo de dados iterativos e agentes autônomos, os quais comunicam-se entre si através de memórias compartilhadas.

Bin Packing is a combinatorial optimization problem known to be NP-complete. The majority of the algorithms used to find exact solutions for this class of problems takes exponential time. A great amount of effort have been devoted to the development and analysis of faster algorithms (heuristics) that produces good solutions in polynomial time. This work presents an optimization solution method to Bin Packing problem, using some heuristics and applying the Asynchronous Teams method (A-Teams), a strongly cyclic computational network, with interactive data flow and autonomous agents, which one can communicate by shared memories.