Data/hora: 09/06/2024 00:40:10

Biblioteca(s): | Embrapa Agricultura Digital.
Data corrente: | 27/05/1998
Data da última atualização: | 21/01/2020
Autoria: | LORENA, L. A. N.; NARCISO, M. G.
Afiliação: | LUIZ ANTÔNIO NOGUEIRA LORENA, INPE; MARCELO GONÇALVES NARCISO, INPE.
Título: | Heurísticas para o problema generalizado de atribuição.
Ano de publicação: | 1994
Fonte/Imprenta: | In: SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL, 26., 1994, Florianópolis. Anais... Rio de Janeiro: SBPO, 1994.
Páginas: | p. 473-479.
Idioma: | Português
Notas: | SBPO 1994.
Conteúdo: | Neste trabalho, heurísticas são propostas para resolver o problema generalizado de atribuição. Usando as relaxações Lagrangeana e surrogate, elas realizam uma busca usando subgradiente para obter soluções viáveis. As relaxações consideram um vetor de multiplicadores para as restrições de capacidade. A resolução usando a relaxação Lagrangeana é imediata. Para a relaxação surrogate, o problema resultante é uma mochila com múltipla escolha, que é novamente relaxado para valores contínuos das variáveis, e resolvido em tempo polinomial. Multiplicadores advindo das relaxações são usados com uma heurística de Martello & Toth melhorada ou una nova heurística construtiva para encontrar boas soluções viáveis. Seis heurísticas são testadas com problemas da literatura e problemas gerados aleatoriamente. Melhores resultados são menos do que 5% do valor ótimo, com tempos computacionais razoáveis para um microcomputador AT/386. Parece promissor para problemas com coeficientes correlacionados.
Palavras-Chave: | Generalized assigment problems; Heurísticas; Heuristics; Lagrangian and surrogate relaxation; Problema generalizado de atribuição; Relaxação lagrangeana; Relaxação surrogate; Relaxações lagrangeana e surrogate.
Categoria do assunto: | X Pesquisa, Tecnologia e Engenharia
Registro original: | Embrapa Agricultura Digital (CNPTIA)

Exemplares:

CNPTIA - (6979-1) - ADD - SP - PP -  -  - 1998.00004 - DES
CNPTIA - (6979-2) - ADD - PC - DD -  -  -  - DIS