Qualificação de doutorado da discente Janniele Araújo, dia 26/05/17.

Qualificação de doutorado da discente Janniele Soares Araujo, dia 26/05/17, as 15:00 na Sala de Seminários do DECOM - ICEB III.

Banca: Prof. Dr. Marcone Jamilson Freiras Souza - UFOP; Prof. Dr. Puca Huachi Vaz Penna - UFOP; Prof. Dr. Eduardo Uchoa Barcbosa - UFF

Resumo:

Algoritmos de Busca Heurística e Exata para o Problema de Escalonamento de Projetos com Restrições de Recursos

Problemas de escalonamento de projetos com restrição de recursos, do inglês Resource Constrained Project Scheduling Problems - (RCPSPs) são problemas com significativa importância acadêmica e prática. Uma solução para o RCPSP consiste em alocar tarefas selecionando modos de execução e respeitando restrições de precedência e uso de recursos. Métodos baseados em busca local estocástica (SLS) foram classificados como boas heurísticas disponível para muitos problemas de otimização combinatória difíceis. As SLS que utilizam muitas vizinhanças colocam questões difíceis sobre a exploração destas.
Neste trabalho são exploradas diferentes estratégias de composição para quatorze vizinhanças que fornecem insights interessantes. Abordagens exatas mais bem sucedidas para esses problemas são baseadas em formulações compactas de programação binária. Estas formulações geralmente fornecem limites inferiores fracos, mas podem ser significativamente melhoradas usando Planos de Corte. Neste trabalho também são propostas estratégias de separação e reforço para duas desigualdades válidas bem conhecidas para este problema. Também é explorada a criação dinâmica de grafos de conflitos densos considerando variáveis binárias, estes são utilizados para gerar desigualdades válidas derivadas de cliques. Cortes de Chvátal-Gomory de uso geral também são propostos para fortalecer os limites baseados em LP. Experimentos computacionais considerando instâncias de diferentes conjuntos de referência mostram que a inclusão de todas essas desigualdades fornece limites inferiores mais fortes. Por fim, novas melhores soluções foram encontradas utilizando estratégias heurísticas, foi obtido a prova da otimalidade para 318 instâncias e foi possível provar a infactibilidade de 78.

Palavras-chave: escalonamento de projeto, restrição de recursos, planos de corte, busca local estocástica, composição de vizinhança.