Detalhes dos Anais Veja o resumo do trabalho

Publicado no Encontro de Saberes 2015

Evento: XXIII Seminário de Iniciação Científica

Área:

Subárea:

Título
UMA 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 (Orientador)
JANNIELE APARECIDA SOARES (Co-Autor)
Resumo
O projeto em questão abordou uma 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. Para o nosso trabalho, retivemos o foco da nossa pesquisa no campo das heurísticas. Nosso estudo se concentrou na pesquisa de métodos eficientes de busca local para o problema. Nesse sentido, foram estudadas 14 vizinhanças. Nas heurísticas, foram implementados métodos de busca local, métodos de múltiplos reinícios entre outras técnicas. No trabalho proposto, as heurísticas foram manipuladas pelo algoritmo LAHC - (Late Acceptance Hill-Climbing algorithm). Após vários testes, foram selecionados os melhores parâmetros para compor a entrada do algoritmo em questão. Para melhorar o desempenho do código, foi feita também uma paralelização com múltiplas threads. Essa paralelização permitiu executar mais de uma heurística ao mesmo tempo, fazendo com que os resultados finais chegassem a um nível satisfatório, que em relação a 1-gap ficaram entre 0.94 e 1.00 das melhores soluções encontradas na literatura. Das 30 instâncias propostas por uma conferência, 25 ficaram dentro dessa faixa. Por fim, com os resultados do nosso trabalho de pesquisa, obtivemos alguns resultados melhores com relação aos melhores encontrados na literatura. As 20 instâncias mais difíceis são mantidas em (http://allserv.kahosl.be/mista2013challenge/bestsolutions.html). Essa página já está atualizada. As instâncias nas quais ultrapassamos os melhores resultados foram: B-8 e B-10. Anteriormente, a instância B-8 possuía um TPD de 3176 e TMS de 533 e a instância B-10 um TPD de 3249 e TMS de 456. Com nosso método, a instância B-8 teve um TPD de 2974 e TMS de 541 e a instância B-10 um TPD de 3050 e TMS de 448. Com estes resultados, um artigo foi publicado na conferência internacional MISTA.
Voltar Visualizar PDF