Estudo de estruturas de vizinhança e estratégias de busca local em gpu para o problema job shop clássico.

• Processo: 18/08326-6
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Data de Início da vigência: 01 de outubro de 2018
• Data de Término da vigência: 31 de dezembro de 2020
• Área do conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Fabio Henrique Pereira
• Beneficiário: Fabio Henrique Pereira
• Instituição Sede: Universidade Nove de Julho (UNINOVE). Campus Vergueiro. São Paulo , SP, Brasil
• Assunto(s): Otimização combinatória
• Palavra(s)-Chave do Pesquisador: Algoritmo Genético Paralelo | Busca local | Cuda | Gpu | Job Shop Scheduling | Otimização combinatória

Resumo

O problema de sequenciamento da produção job shop (job shop scheduling) tem sidoexaustivamente estudado nos últimos anos devido a sua importância prática e complexidadecomputacional. Além disso, as aplicações práticas desses problemas na indústria e na ciência estão setornando cada vez maiores e complexas, exigindo mais poder computacional e métodos especializadospara uma solução escalável. Técnicas de busca local tem sido o método de escolha para problemasdessa complexidade. A aplicação de técnicas de busca local nesses casos provou ser necessária, masextremamente custosa em termos computacionais. Uma alternativa para responder à essa questão docusto computacional é a programação paralela, com destaque para o paralelismo baseado emUnidades de Processamento Gráfico (GPU) para computação de propósito geral. A paralelização emGPU permite um ganho de eficiência extremamente alto quando comparado a uma unidade deprocessamento usual (CPU), desde que a aplicação possua demandas favoráveis à arquiteturadaqueles dispositivos, a qual é mais focada na unidade lógica aritmética. Por outro lado, as estratégiastradicionais de vizinhança sofrem com uma dificuldade relacionada às características do espaço debusca nesses problemas, as chamadas bacias de atração que dificultam a convergência de métodosde otimização. Assim, diante da complexidade dos problemas de scheduling, o objetivo deste projeto édesenvolver uma estratégia de busca local para o JSSP, com características de vizinhança eestratégias de busca menos sensível às bacias de atração e adequada aos aspectos de paralelizaçãoem processadores gráfico das placas de vídeos e da plataforma CUDA" da NVIDIA. Os resultadosobtidos serão analisados e comparados com os mesmos métodos desenvolvidos em modeloconvencional de forma a minimizar o instante de término de processamento de todas as tarefas nosistema de produção. (AU)

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)

PEREZ, YURI; PEREIRA, FABIO HENRIQUE. Simulation of traffic light disruptions in street networks. PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, v. 582, NOV 15 2021. (18/08326-6)

PEREZ, YURI; PEREIRA, FABIO HENRIQUE. Estimating pandemic effects in urban mass transportation systems: An approach based on visibility graphs and network similarity. PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, v. 620, p. 13-pg., 2023-06-15. (18/08326-6)