Publicado no Encontro de Saberes 2016
Evento: XXIV Seminário de Iniciação Científica
Área: CIÊNCIAS EXATAS E DA TERRA
Subárea: Ciência da Computação
Órgão de Fomento: Conselho Nacional de Desenvolvimento Científico e Tecnológico
| Título |
| Paralelização do algoritmo de Estratégia de Aceitação Tardia em Subida da Encosta para o Problema de Escalonamento de Múltiplos Projetos com Múltiplos Modos e Restrição de Recursos |
| Autores |
|
DAVI DALFIOR BALTAR (Autor) HAROLDO GAMBINI SANTOS (DECOM) (Orientador) |
| Resumo |
| O projeto em questão abordou uma paralelização para a estratégia de aceitação tardia em subida da encosta para o Problema de Escalonamento de Múltiplos Projetos com Múltiplos Modos e Restrição de Recursos. O problema proposto pode ser estudado a partir de programação inteira, programação por restrições ou heurísticas. Em nossa pesquisa, estabelecemos o foco no campo das heurísticas. Nosso estudo se concentrou na pesquisa de métodos eficientes de paralelização para o problema. De posse de 14 heurísticas implementadas no projeto anterior, as quais são manipuladas pela meta-heurística LAHC - (Late Acceptance Hill-Climbing), nosso trabalho propôs uma melhoria para este algoritmo. Após vários testes, foram selecionados os melhores parâmetros para compor a entrada do algoritmo em questão. A paralelização permitiu executar mais de uma heurística ao mesmo tempo e executar, de forma paralela, partes do LAHC, fazendo com que os resultados finais chegassem a um nível satisfatório. Em relação a 1-gap, os resultados do algoritmo paralelizado tiveram uma média melhor do que o do algoritmo não paralelizado, sendo os valores da média e desvio padrão para o algoritmo paralelizado de 0.97 e 0.030 respectivamente, enquanto o algoritmo não paralelizado alcançou uma média de 0.96 e desvio padrão de 0.040 na execução das 30 instâncias propostas na literatura. Por fim, com os resultados de nossa pesquisa, melhoramos a média e o desvio padrão obtidos pelo projeto anterior, ao qual propomos algumas melhorias na técnica de busca local para o LAHC. |
