Proposta para trabalho de formatura supervisionado

Francisco Nogueira Calmon Sobral

N$^o$USP: $3781690$. ¹

Nome do aluno: Francisco Nogueira Calmon Sobral
Nome do supervisor: Ernesto G. Birgin
Tipo de trabalho: Iniciação científica

Modelos não lineares para problemas de empacotamento

Resumo da monografia:

Problemas de empacotamento são caracterizados por se tentar colocar itens (objetos a serem empacotados) dentro de objetos (áreas, ou volumes, que empacotarão os itens). Esses tipos de problemas aparecem em diversas áreas relacionadas com logística, como colocar o maior número de produtos em um container, ou em um caminhão para tranporte; com a indústria, objetivando minimizar os desperdício de certo material ao se fazer cortes (em chapas de alumínio ou tecidos); e até mesmo na área química (empacotamento de moléculas).

Existem basicamente duas abordagens para o problema: uma onde, dado um objeto com dimensões fixas, encontrar o maior número de itens que ele pode conter sem que se sobreponham, e uma outra onde são dados $N$ itens e deseja-se encontrar o objeto (pré definido) com a menor área que os contém, sem sobreposição.

Objetivos do trabalho:

Nesse trabalho, estudaremos e implementaremos modelos não lineares para problemas relacionados com a segunda abordagem discutida acima (com um número fixo de itens, encontrar a menor área). Para isso, modelos serão construídos e utilizaremos um algoritmo de resolução de problemas não lineares chamado ALGENCAN.

O trabalho também consiste em tentar resolver grandes instâncias, que, pelo fato das comparações de sobreposição entre ítens serem da ordem O($N^2$), $N$ o número de ítens, exige que se encontre técnicas para torná-la mais rápida.

Finalmente os resultados conseguidos serão comparados com aqueles que já existem na literatura, para verificarmos a qualidade dos modelos feitos.

Atividades já realizadas:

Já foram construidos modelos para empacotamento de $N$ círculos em um círculo, um quadrado, um triângulo eqüilátero, um retângulo e em um strip (retângulo com a algura fixada, ou seja, deseja-se encontrar a menor largura).

Implementamos esses modelos no algoritmo ALGENCAN e instâncias para até $N = 50$ círculos de raio unitário foram testadas. Comparamos os resultados obtidos com os publicados na literatura e as conclusões foram animadoras.

Ao tentarmos aumentar o tamanho das instâncias, nos deparamos com o problema do número quadrático de comparações entre itens, de forma que uma técnica de colocar os círculos em uma 'grade', para comparar apenas aqueles que têm alguma chance de se sobreporem, foi sugerida.

Para que se pudesse usar a grade, foi necessária uma mudança dos modelos que eram utilizados. Atualmente, a grade está sendo testada, mas resultados preliminares indicam uma melhoria significativa no tempo.

Cronograma de atividades para o segundo semestre:

• Julho 2005: Revisão de todos os trabalho já lidos. Testes e comparações com os modelos já implementados (círculo, retângulo, triângulo eqülitátero, quadrado e strip) utilizando a grade.

• 2$^o$ semestre 2005: Desenvolvimento e teste de novos modelos: círculos em um objeto anelar, empacotamento ortogonal de retângulos (modelo sugerido em [1]), considerar quadrados como itens a serem empacotados.

Estrutura esperada da monografia:

A monografia terá a seguinte estrutura:

• Introdução aos problemas de empacotamento. Pesquisas e trabalhos publicados na área
• Apresentação da nossa abordagem: utilização de modelos contínuos
• Apresentação dos modelos de empacotamento
• Implementação e detalhes (geração dos pontos iniciais do problema, resolução do mesmo problema com pontos iniciais diferentes, etc...)
• Testes e comparações com resultados já obtidos
• Conclusões e trabalhos futuros
• Análise subjetiva do curso
• Referências