Bolsa 10/08434-1 - Scheduling, Meta-heurística - BV FAPESP
Processo: 10/08434-1
Pesquisador responsável: Débora Pretti Ronconi
Beneficiário: Celso Satoshi Sakuraba
Assunto(s): Scheduling Meta-heurística Otimização combinatória Heurística
Existem problemas de otimização que representam um desafio até mesmo para os melhores softwares disponíveis no mercado atualmente. Um exemplo destes problemas considerados difíceis são aqueles pertencentes à classe NP-hard, muitas vezes abordados utilizando metodologias heurísticas e meta-heurísticas, principalmente quando lidamos com instâncias com um grande número de variáveis. Este projeto visa o desenvolvimento de meta-heurísticas para dois problemas de otimização combinatória: o problema de ordenação linear e um problema de programação da produção em um ambiente flowshop. Trabalhos anteriores do autor incluem algoritmos que podem alcançar ótimos locais de forma eficiente, realizando uma busca local para o problema de ordenação linear em um tempo computacional menor do que algoritmos propostos anteriormente na literatura, ou encontrando uma programação ótima para uma dada sequência de tarefas em tempo linear. Com base em tais algoritmos, busca-se encontrar maneiras adequadas de se aplicar as estruturas de meta-heurísticas de forma a obter melhores resultados em termos de tempo de processamento computacional e qualidade das soluções.