|
|
|
| Introdução
Esta página contém a proposta para a monografia de conclusão de curso, que versa sobre um projeto sob supervisão do Prof. Ernesto G. Birgin. ObjetivosImplementar e comparar a eficiência de diversos algoritmos para o problema do "Empacotamento de Círculos de Tamanho Variado em um Retângulo". Trata-se de um problema demonstradamente NP-difícil, expresso na forma de um problema de programação não-linear, para o qual foram sugeridas algumas heurísticas e os correspondentes algoritmos. O trabalho visa implementar diversas destas heurísticas e fazer uma análise dos resultados obtidos, comparando as técnicas entre si. A motivação para este problema pode ser ilustrada com a seguinte situação: uma empresa de transportes despacha uma variedade de tubos de plástico em containers. O comprimento de cada tubo é o mesmo do container. Tubos de diferentes diâmetros podem ser encaixados uns dentro dos outros. Sob a perspectiva da seção transversal de um tal carregamento, temos o problema bidimensional do empacotamento de círculos dentro de um retângulo. A questão do encaixe de tubos uns dentro dos outros não é abordada aqui, e assume-se que já tenhamos a lista dos diâmetros exteriores dos tubos (círculos) em questão. Os algoritmos abordados visam resolver o problema de como encaixar da melhor maneira possível um dado número de círculos dentro de um dado retângulo - note-se que também não será abordado o problema de como alocar os círculos de modo a minimizar a quantidade de retângulos. Atividades RealizadasOs papers existentes, relacionados ao assunto e citados na Bibliografia, foram estudados, selecionando-se um mais adequado para servir de base para a implementação tal como discutida acima (vide [Hifi04]). No momento, estou preparando uma apresentação geral do problema e da abordagem que iremos adotar para tratá-lo. Cronograma de Atividades para o Segundo Semestre
Estrutura Esperada da MonografiaA monografia será composta pelas seguintes seções:
|
|
Personal site:
http://rubens.altimari.com.br
|
