Google propõe algoritmos para agendamento com capacidade variável

O que aconteceu

O Google Research Blog publicou, em 11 de fevereiro de 2026, o artigo "Scheduling in a changing world: Maximizing throughput with time-varying capacity", do pesquisador Manish Purohit. O estudo, intitulado "Non-preemptive Throughput Maximization under Time-varying Capacity", foi apresentado no SPAA 2025 e introduz os primeiros algoritmos de aproximação de fator constante para o problema de maximização de throughput em ambientes com capacidade variável. Isso significa que a diferença entre a solução encontrada pelo algoritmo e a solução ótima é garantidamente um número fixo, independentemente do tamanho do problema.

Contexto

No agendamento algorítmico de jobs, os recursos computacionais costumam ser tratados como estáticos: um servidor tem um número fixo de CPUs, ou um cluster tem uma quantidade constante de máquinas disponíveis. Na prática, porém, a infraestrutura de nuvem em larga escala é dinâmica. Recursos flutuam por falhas de hardware, ciclos de manutenção e limitações de energia. Em sistemas hierárquicos de agendamento, tarefas de alta prioridade podem reivindicar recursos sob demanda, deixando uma capacidade "sobrante" variável para jobs em lote de baixa prioridade. Quando esses jobs não são preemptivos — ou seja, não podem ser pausados e retomados —, uma interrupção causada por queda de capacidade faz todo o progresso ser perdido.

Por que importa

A pesquisa fornece uma base teórica para construir agendadores mais robustos em ambientes de nuvem voláteis. Para empresas que operam cargas de trabalho em lote, isso pode significar menos jobs perdidos e melhor aproveitamento da capacidade ociosa. Os pesquisadores usam uma analogia: imagine um restaurante em que mesas são reservadas para VIPs em horários diferentes; acomodar clientes comuns nas mesas restantes é um quebra-cabeça complexo. O novo modelo captura essa dinâmica ao considerar um perfil de capacidade que varia no tempo e define o número máximo de jobs que podem ser executados em paralelo a cada momento.

Impacto

No curto prazo, os resultados são majoritariamente teóricos, mas abrem caminho para implementações práticas em agendadores de cluster. Os algoritmos de aproximação de fator constante oferecem previsibilidade de desempenho mesmo quando a capacidade oscila. Isso pode levar a sistemas de nuvem mais eficientes e confiáveis para processamento em lote, especialmente em plataformas que usam agendamento em camadas, onde jobs de alta prioridade consomem recursos dinamicamente.

O que muda

Em vez de tratar a capacidade como fixa, os novos algoritmos consideram explicitamente um perfil de capacidade variável. O modelo inclui uma máquina ou cluster com capacidade máxima variável ao longo do tempo, e cada job é definido por atributos como janela de execução válida e peso. O objetivo é selecionar um subconjunto de jobs e agendá-los de forma contínua, respeitando a restrição de que o número de jobs em execução não exceda a capacidade disponível em nenhum momento.

O que vem agora

O post não detalha próximos passos específicos. Como o trabalho foi apresentado no SPAA 2025, é esperado que os algoritmos sejam refinados e eventualmente incorporados a sistemas de agendamento reais, especialmente em infraestruturas de nuvem que dependem de agendamento hierárquico. As informações são do Google Research Blog.