Algoritmos avançados para alocação de recursos, gerência de estoque e outros problemas de cadeia de fornecimento

• Processo: 12/17634-0
• Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
• Vigência (Início): 01 de fevereiro de 2013
• Vigência (Término): 31 de janeiro de 2014
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Flávio Keidi Miyazawa
• Beneficiário: Lehilton Lelis Chaves Pedrosa
• Supervisor no Exterior: Maxim Sviridenko
• Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Local de pesquisa : University of Warwick, Inglaterra
• Vinculado à bolsa: 10/20710-4 - Algoritmos de aproximação para problemas de localização com diferentes funções de distância, BP.DR
• Assunto(s): Algoritmos de aproximação Alocação de recursos

Resumo

Algoritmos de aproximação têm recebido grande atenção dos pesquisadores de otimização e teoria da computação nos últimos anos. Esses algoritmos são utilizados principalmente em problemas NP-difíceis, para os quais um algoritmo exato seria inviável. Existem diferentes técnicas para o desenvolvimento de algoritmos de aproximação, que têm sido utilizadas para obter aproximações cada vez melhores para os problemas de alocação e vários outros. Essas técnicas geralmente podem ser utilizadas para lidar com diversas variantes e outros problemas de cadeia de suprimento. Neste projeto, estamos interessados em investigar o Problema de Alocação de Recursos (FLP) e outros problemas de cadeia de suprimento, como o Problema de Gerência de Estoque. Nosso interesse será focado em estratégias recentes desenvolvidas para estes problemas, principalmente aquelas que levam a bons fatores de aproximação. Entre elas, estão as técnicas de arredondamento de PL e a técnica primal-dual. Em particular, a técnica primal-dual combinada com a análise por meio de programas reveladores de fator (factor-revealing programs). Um primeiro objetivo desse projeto é estudar essas técnicas e aplicá-las a variantes e problemas relacionados. Também iremos investigar diferentes funções de distância para os problemas estudados. Diversos algoritmos de aproximação para problemas, como o FLP ou o TSP, utilizam fortemente o fato de que as funções de distância subjacentes sejam métricas para obter resultados de aproximação. Para algumas aplicações, no entanto, as funções de distância não obedecem à desigualdade triangular, como é o caso do k-means, que utiliza a distância euclidiana ao quadrado. Os problemas TSP e FLP já foram estudados considerando funções de distância não-métricas. Um outro objetivo desse trabalho é estender esse estudo a outras variantes e problemas relacionados. (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)

PEDROSA, LEHILTON L. C.; SVIRIDENKO, MAXIM. Integrated Supply Chain Management via Randomized Rounding. INFORMS JOURNAL ON COMPUTING, v. 30, n. 1, p. 124-136, WIN 2018. Citações Web of Science: 0.