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

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)