Algoritmos de Otimização Não-Exatos para Problemas de Sequenciamento

• Processo: 10/08434-1
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Data de Início da vigência: 01 de agosto de 2010
• Data de Término da vigência: 31 de dezembro de 2011
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Débora Pretti Ronconi
• Beneficiário: Celso Satoshi Sakuraba
• Instituição Sede: Escola Politécnica (EP). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Scheduling Meta-heurística Otimização combinatória Heurística
• Palavra(s)-Chave do Pesquisador: Busca local | heuristicas | meta-heurísticas | Scheduling | Otimização Combinatória

Resumo

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.

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

SAKURABA, CELSO S.; RONCONI, DEBORA P.; BIRGIN, ERNESTO G.; YAGIURA, MUTSUNORI. Metaheuristics for large-scale instances of the linear ordering problem. EXPERT SYSTEMS WITH APPLICATIONS, v. 42, n. 9, p. 4432-4442, JUN 1 2015. (13/07375-0, 10/08434-1, 13/05475-7, 10/10133-0, 13/03447-6)