Programação Linear Online com Agrupamento

Estudamos a Programação Linear Online (OLP) com agrupamento. O horizonte de planejamento é dividido em K grupos, e as decisões sobre os clientes que chegam dentro de um grupo podem ser adiadas até o final do seu grupo associado. Em comparação com OLP sem agrupamento, a capacidade de adiar decisões traz melhor desempenho operacional, conforme medido pelo arrependimento. Duas questões de pesquisa de interesse são: (1) Qual é um limite inferior do arrependimento como função de K? (2) Quais algoritmos podem atingir o limite inferior do arrependimento? Essas questões foram analisadas na literatura quando a distribuição da recompensa e o consumo de recursos dos clientes têm suporte finito. Em contraste, este artigo analisa essas questões quando a distribuição condicional da recompensa dada o consumo de recursos é contínua, e mostramos que as respostas são diferentes nesse ambiente. Quando há apenas um único tipo de recurso e o tomador de decisão conhece o número total de clientes, propomos um algoritmo com um limite superior de arrependimento O(K) e fornecemos um limite inferior de arrependimento (K). Também propomos algoritmos com limite superior de arrependimento O(K) para o cenário em que há múltiplos tipos de recurso e o cenário em que os clientes chegam seguindo um processo de Poisson. Todos esses limites superiores e inferiores de arrependimento são independentes da duração do horizonte de planejamento, e todos os algoritmos propostos adiam decisões sobre os clientes que chegam apenas no primeiro e no último grupo. Também levamos em consideração a impaciência dos clientes e estabelecemos uma maneira de selecionar um tamanho de grupo apropriado.