|
|
|
de Interesse |
|
| null | null |
| Grupo de Estudos em Otimização Combinatorial | |
|
|
Vanessa
Gindri Vieira
Vinícius Jacques Garcia |
|
|
Problema
da Mochila
Resumo |
|
|
|
| Grupo de Estudos de Educação na Informática | |
|
|
Fábio Purificação de Bastos |
|
|
Curso
de Word97
Resumo |
|
|
|
| Trabalhos de Graduação | |
|
|
Título Resumo Título Resumo Título Resumo Modelagem e Implementação do Problema de Empacotamento Uma das áreas da tecnologia da informação bastante explorada e com grandes aplicações nas demais é a pesquisa operacional, que faz uso de técnicas matemáticas e científicas para analisar e melhorar a eficiência de outras áreas. Nessa área encontra-se a Otimização Combinatorial, que trata basicamente do estudo matemático para encontrar um arranjo, agrupamento ou seleção ótima de objetos discretos, tendo sido aplicada extensivamente aos mais diversos ramos do conhecimento. Em Otimização Combinatorial, é comum encontrar na literatura vários algoritmos, muitos com excelente desempenho, para resolução de determinado problema. Muitos dos algoritmos propostos para um problema particular são aplicáveis a solução de outro problema através de pequenas adaptações. Assim, se tornaria mais simples o estudo e proposição de novos algoritmos se houvesse uma biblioteca que reunisse os problemas mais clássicos com os algoritmos para sua resolução. Dentre os problemas clássicos da Otimização Combinatorial está o problema de Empacotamento (Bin-Packing Problem) que foi extensivamente estudado por ser um problema difícil, onde a possibilidade de existir algoritmos exatos que os resolvam em tempo de execução razoável é muito pequena. Com isso, faz-se necessário o uso de algoritmos aproximados que buscam encontrar soluções muito próximas da ótima em tempos de execução razoáveis (heurísticas). O problema de Empacotamento consiste em alocar uma coleção de objetos com tamanhos definidos no menor número de caixas possível, sendo que a capacidade da caixa é previamente definida, de forma que nenhuma caixa seja preenchida além de sua capacidade, assim como nenhum objeto seja fracionado em objetos menores. O presente trabalho trata da implementação e modelagem, usando a linguagem de modelagem UML, do problema de Empacotamento visando a aplicação da modelagem proposta em [MÜLLER, TONIOLO 1998] do Framework de Otimização desenvolvido nesta Instituição de Ensino em colaboração com a UNICAMP (Campinas, SP) e PUC-RS (Porto Alegre, RS) e comparação dos métodos de resolução encontrados para o problema. Dentre as aplicações da Otimização Combinatorial para o Problema de Empacotamento tem-se nas indústrias o seu maior destaque, além de transporte de mercadorias, entre outras. Aproximando-se do contexto acadêmico de cursos voltados à tecnologia da informação, tem-se a necessidade de otimizar o uso de discos flexíveis, partições de disco rígido, fitas magnéticas, entre outros, para armazenamento de dados, o que pode ser obtido se este problema for reduzido ao problema de empacotamento. Ao final desse trabalho ter-se-á reunido e disponibilizado no Framework exemplos de dados de entrada e algoritmos implementados em Java ou encapsulados para a solução do problema de Empacotamento. Título Resumo |