Algoritmo genético resolve lote com demanda aleatória e gap de 3,44%

O que aconteceu

Um estudo submetido ao arXiv em 5 de julho de 2026 (arXiv:2609.00004) apresenta uma modelagem matemática para um problema clássico de gestão de produção: o dimensionamento de lote com múltiplos itens, capacidade de produção limitada e demanda cujo período de chegada é estocástico, ou seja, não se sabe exatamente quando o pedido vai aparecer, apenas uma janela de tempo conhecida.

O artigo, intitulado "Discrete-Time MDP Modeling for Multi-Item Capacitated Lot Sizing with Stochastic Demand Timing", formaliza o problema como um processo de decisão de Markov em tempo discreto (DTMDP, na sigla em inglês). A proposta define espaço de estados, ações viáveis, núcleo de transição e função de custo de um período. Segundo o resumo, o modelo trabalha com decisões de produção e alocação no nível da demanda, o que permite representar competição por capacidade, atraso específico de cada demanda e dinâmica de inventário dependente da alocação.

O DTMDP, que é a base do estudo, compara cada instância estocástica com uma versão determinística, onde cada distribuição de chegada é substituída pelo período mais provável. A comparação mostrou que a incerteza no tempo de chegada aumenta substancialmente o número de estados, o número de transições, o tempo de solução e a pressão de memória.

Contexto

O problema de dimensionamento de lote é um dos pilares do planejamento da produção. Em versões tradicionais, a demanda é conhecida com antecedência, e a empresa decide quanto produzir em cada período para minimizar custos de produção, estoque e atraso. Quando o tempo de chegada do pedido é incerto, a complexidade cresce exponencialmente, pois cada cenário possível de chegada exige uma decisão diferente.

A formulação como processo de decisão de Markov (MDP) é uma abordagem consolidada para problemas sequenciais sob incerteza. O que o artigo faz é adaptar essa estrutura ao problema de lote com capacidade compartilhada entre múltiplos itens. A novidade está na representação no nível da demanda, que captura a interação entre pedidos concorrentes e permite atrasos específicos por item.

A equipe executou experimentos computacionais em 330 instâncias de benchmark. Em todas, a solução exata do DTMDP foi calculada quando possível. Nas instâncias mais difíceis, um conjunto de 90 casos, o algoritmo genético (GA) proposto manteve um gap de otimalidade abaixo do limite de 5%.

Por que importa

Em ambientes reais de manufatura, a incerteza sobre quando o cliente vai efetivamente fazer o pedido é comum, especialmente em contratos com janelas de entrega. Empresas que hoje usam modelos determinísticos, que assumem uma chegada fixa, podem estar subestimando a necessidade de estoque de segurança ou superestimando a capacidade utilizada.

O estudo oferece um método que, mesmo com a aleatoriedade, produz soluções próximas da ótima. O algoritmo genético, que é uma meta-heurística inspirada na evolução natural, busca sobre políticas de feedback de estado viáveis e avalia cada política exatamente sob o modelo de transição do DTMDP. Esse mecanismo de avaliação exata é o que garante a qualidade da resposta.

No cenário brasileiro, onde cadeias de suprimentos lidam com atrasos frequentes e variações de demanda, a aplicação prática pode reduzir custos de estoque e melhorar o nível de serviço, sem exigir a resolução exata que em muitos casos é computacionalmente inviável.

Impacto

Os números mostram o impacto prático. O gap médio de otimalidade do GA em relação à solução exata foi de cerca de 3,44%, considerando as instâncias onde a solução exata estava disponível. Nas 90 instâncias mais difíceis, o GA ficou abaixo do limiar de 5% e alcançou um speedup médio de otimização de 6,89 ± 1,41, com nível de confiança de 95%. Em outras palavras, o GA encontrou soluções quase ótimas em um tempo quase 7 vezes menor.

Para casos em que a solução exata não pôde ser calculada no hardware disponível, o estudo usou uma regressão empírica do tempo de Bellman para estimar o tempo de resolução exata e extrapolar o speedup esperado do GA. Isso dá uma ideia do ganho mesmo quando não há comparação direta.

A pressão de memória também é um fator relevante. Com o aumento de estados e transições no cenário estocástico, a alocação de memória pode inviabilizar a solução exata em servidores comuns. O GA contorna essa limitação ao não exigir a enumeração completa de todos os estados.

O que muda

Para pesquisadores e engenheiros de otimização, o artigo fornece uma base formal para tratar o problema de lote com tempo de chegada estocástico. A modelagem em DTMDP pode ser estendida para outras variações, como demanda com quantidade também incerta ou horizontes contínuos. Para profissionais de planejamento, o algoritmo genético se apresenta como uma alternativa prática viável para sistemas de apoio à decisão.

A técnica de regressão empírica para estimar o tempo de resolução exata também é um avanço metodológico, pois permite comparar desempenho mesmo quando o benchmark não pode ser resolvido de forma exata.

O que vem agora

O estudo não publica código-fonte nem detalhes de implementação, mas o modelo matemático completo está descrito no artigo. Os próximos passos naturais incluem aplicar o GA em casos reais da indústria, testar com demanda não estacionária e comparar com outras meta-heurísticas. O arXiv é um repositório de pré-prints, portanto o trabalho ainda não passou por revisão por pares, o que significa que os resultados devem ser interpretados com cautela.

O artigo está disponível na íntegra no arXiv, na seção de Inteligência Artificial (cs.AI), e pode ser acessado pelo identificador 2609.00004. A comunidade de otimização e gestão de operações deve acompanhar os próximos desdobramentos, especialmente se os autores disponibilizarem os benchmarks e o código para reprodução.

Fontes

• arXiv: Discrete-Time MDP Modeling for Multi-Item Capacitated Lot Sizing with Stochastic Demand Timing — https://arxiv.org/abs/2609.00004