Geração das K-melhores soluções para o problema da mochila unidimensional em ambiente distribuído
AUTOR(ES)
Rodrigo de Castro Penna Franca
FONTE
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia
DATA DE PUBLICAÇÃO
01/11/1996
RESUMO
Este trabalho sugere um algoritmo para ambiente distribuído que determina as K-melhores soluções para o problema da mochila unidimensional. O algoritmo baseia-se no trabalho de Yanasse, Soma e Maculan (1995), que trata da mesma questão para ambiente serial. Entretanto, convém ressaltar que a versão distribuída do algoritmo possui profundas modificações em relação à versão serial. Primeiramente, o algoritmo serial foi estudado e totalmente implementado. A segunda etapa do trabalho foi o desenvolvimento do algoritmo distribuído. Parte desta tarefa tratou da escolha de uma abordagem de implementação no ambiente distribuído. Duas abordagens foram levadas em consideração e os respectivos algoritmos foram implementados e testados. O paradigma divide and conquer para algoritmos paralelos foi o que prevaleceu. Quanto ao ambiente operacional, o algoritmo serial foi desenvolvido, na sua fase inicial, sobre a plataforma 486/Windows e linguagem de programação C++. Posteriormente, portou-se a aplicação para o ambiente RISC/UNIX. O algoritmo distribuído foi desenvolvido em linguagem de programação C++ aliada às funções da biblioteca PVM, Parallel Virtual Machine (Máquina Paralela Virtual), em uma rede de estações UNIX. Resutaldos computacionais são apresentados.
ASSUNTO(S)
algoritmos programação matemática problema da mochila programação paralela ambiente de programação matemática computacional processamento distribuído computação
ACESSO AO ARTIGO
http://www.bd.bibl.ita.br/tde_busca/arquivo.php?codArquivo=1691Documentos Relacionados
- Algoritmos paralelos para o problema da mochila.
- Um algoritmo exato para o problema da mochila
- O Problema da mochila compartimentada e aplicações
- The Compartmentalized Knapsack Problem
- Uma heurística baseada em geração sequencial de padrões para o problema de corte de estoque unidimensional com um número reduzido de padrões