Otimizando um otimizador: escalas justas com MIP

Montar escala de turnos é o tipo de problema que parece “coisa de planilha” até você tentar respeitar restrições de verdade: disponibilidade, cobertura mínima, diferentes frequências de participação e, de vez em quando, um “essas duas pessoas precisam trabalhar juntas”.

Este post é sobre uma mudança pequena, mas com impacto real. Peguei um escalonador de Programação Inteira Mista (MIP) que encontrava uma solução viável e empurrei o resultado na direção de uma solução justa mudando a função objetivo. Mesmas restrições; outro alvo.

O contexto

Esse trabalho foi feito para a Gomo, uma cooperativa de alimentos em São Paulo, tocada pelos próprios membros. Não há funcionários pagos; a operação roda porque as pessoas assumem turnos (abrir a loja, repor, caixa, ajudar outros cooperados).

Eles já tinham um escalonador MIP funcionando (desenvolvido originalmente por Fernando Pimentel Silva usando Gurobi). Ele respeitava as restrições duras, mas a distribuição ficava torta: alguns turnos acabavam cheios demais, enquanto outros ficavam colados no mínimo. O objetivo não era só viabilidade. Era justiça.

O problema

Precisávamos alocar 261 membros ao longo de 4 semanas, 7 dias por semana, 4 turnos por dia (06:15, 08:45, 11:15, 13:45).

As restrições:

Cada pessoa tem janelas específicas de disponibilidade
Cada turno exige um mínimo de pessoas (2-4 por turno)
As pessoas participam com frequências diferentes: semanal (4 turnos/ciclo), quinzenal (2 turnos/ciclo) ou mensal (1 turno/ciclo)
Algumas pessoas precisam trabalhar juntas em dupla (por exemplo, pai/mãe e filho(a))

O jeito “planilha” é lento, frágil e difícil de auditar. Dá para terminar com algo que “parece ok” e ainda assim viola restrições.

Isso é resolvível mesmo?

Antes de mexer no objetivo, eu fiz a checagem mais básica (oferta vs demanda). Na conta: 368 alocações no total (188 mensais + 112 quinzenais + 68 semanais) para uma demanda mínima de 220 vagas somando todos os turnos ativos. Isso deixa uma sobra de 148 alocações no agregado.

Esse saldo é necessário, mas não suficiente. O que importa é se as pessoas certas estão disponíveis para os turnos certos.

Por que Programação Inteira Mista?

MIP funciona bem aqui porque as decisões são discretas: ou alguém é alocado a um turno, ou não. E eu queria garantias duras: se o modelo devolve uma solução, ela respeita as restrições.

Dá para atacar isso com heurísticas ou programação por restrições. Eu fui de MIP porque queria duas coisas ao mesmo tempo: viabilidade estrita sob restrições duras e um objetivo de justiça bem definido.

O modelo matemático

Variáveis de decisão

Para cada pessoa i, semana j, dia k e turno t:

x[i,j,k,t] ∈ {0,1}

Onde x[i,j,k,t] = 1 significa que a pessoa i foi escalada para trabalhar na semana j, dia k, turno t.

Funções objetivo

Testei dois objetivos, mantendo o mesmo conjunto de restrições.

Objetivo base: “qualquer escala viável”

Quando você impõe “cada pessoa trabalha exatamente o número de turnos exigido”, o total de alocações fica praticamente fixo. Ainda assim, o objetivo precisa minimizar alguma coisa; só que isso não molda a distribuição do excedente de maneira útil.

Objetivo minimax: minimizar o pior excedente

Eu introduzi uma variável u para representar o excedente máximo entre os turnos ativos e minimizei u:

minimize u
where u ≥ (Σ x[i,j,k,t]) - demand[j,k,t]  ∀j,k,t

Intuição: se existe folga no sistema, espalhe essa folga em vez de despejá-la em meia dúzia de turnos.

Restrições

Disponibilidade: só alocar pessoas nos turnos que elas marcaram como disponíveis

x[i,j,k,t] ≤ availability[i,k,t]  ∀i,j,k,t

Cobertura mínima: cada turno precisa ter pessoas suficientes

Σ x[i,j,k,t] ≥ demand[j,k,t]  ∀j,k,t

Frequência: cada membro tem um número de turnos obrigatório no ciclo de 4 semanas (1, 2 ou 4). Membros quinzenais também seguem uma regra de periodicidade (semanas 0↔2 e 1↔3).
Duplas: pessoas em dupla precisam trabalhar nos mesmos turnos

x[i,j,k,t] = x[partner[i],j,k,t]  ∀i∈pairs, j,k,t

Implementação: de Gurobi para código aberto, de viável para justa

O algoritmo original usava Gurobi (licença comercial) e focava em viabilidade: encontrar qualquer escala válida. Eu queria abrir isso (PuLP + HiGHS) e, principalmente, trocar o objetivo para que a folga não ficasse concentrada em poucos turnos.

O pedaço novo é este:

import pulp

# Create model
model = pulp.LpProblem("shift_scheduler", pulp.LpMinimize)

# Decision variables
x = pulp.LpVariable.dicts(
    "x",
    ((i, j, k, t) for i in people
                  for j in weeks
                  for k in days
                  for t in shifts),
    cat="Binary"
)

# For MINIMAX: add variable for peak surplus
u = pulp.LpVariable("u", lowBound=0, cat="Integer")

# For each active shift: u >= surplus
for j in weeks:
    for k in days:
        for t in shifts:
            if demand[j][k][t] > 0:
                model += u >= (
                    pulp.lpSum(x[i, j, k, t] for i in people)
                    - demand[j][k][t]
                )

# Objective: minimize peak surplus
model += u

# Add constraints...
model.solve(pulp.HiGHS(msg=1, time_limit=300))

A parte minimax adiciona uma restrição por turno ativo (88 nesta configuração). Isso é pequeno perto do tamanho do modelo completo.

Resultados

Nesse tamanho, o otimizador resolve em segundos (261 pessoas em uma grade 4×7×4 de turnos). Nas execuções que estou reportando aqui, ele alocou os 368 turnos dos membros e não precisou de cobertura externa.

A otimização: base vs minimax

O algoritmo original (BASE) cumpre as restrições rápido, mas a distribuição do excedente pode ficar meio aleatória. Nos meus dados, alguns turnos ficaram acima do necessário enquanto outros ficaram colados no mínimo.

O objetivo minimax muda isso. Mesmas restrições; outro objetivo: derrubar o pior caso.

Aqui está a diferença visual para a Semana 0:

Comparação Base vs Minimax mostrando a distribuição de excedente

Na prática (base → minimax), o excedente máximo caiu de 11 para 2; deixou de existir turno com excedente ≥3 (21 → 0); e o P95 foi de 6.65 para 2.00.

A escala continua com folga, mas a folga para de se concentrar em poucos turnos “azarados”.

Distribuição da escala completa

A escala completa de 4 semanas mantém essa justiça ao longo de todas as semanas:

Mapa de calor de excedente em 4 semanas mostrando distribuição consistente

Azul indica excedente acima da demanda mínima, cinza escuro significa exatamente no mínimo, e vermelho indicaria déficit (não existe nessa solução). O padrão consistente de azul mostra que o otimizador conseguiu balancear a folga entre os turnos ativos.

O que isso te dá

Restrições duras garantidas por construção; uma métrica de justiça fácil de explicar (“minimizamos o pior excedente”); e iteração rápida quando as restrições mudam.

Quando usar MIP para escalas

MIP costuma funcionar bem quando as decisões são discretas (aloca/não aloca), as restrições são realmente duras, você tem um objetivo que importa e o problema está na faixa de “milhares de variáveis”, e não “milhões”.

MIP é exagero quando as restrições são flexíveis, você precisa de escala em tempo real ou a estrutura do problema é simples o bastante para um algoritmo guloso.

Lições aprendidas

As restrições importaram mais do que o código. A maior parte do meu tempo foi para arrumar a formulação e o pré-processamento, não para escrever PuLP.

Comece com dados de brinquedo. Se você não consegue fazer um caso de 3 pessoas e 2 turnos se comportar, um caso com 261 pessoas não vai se consertar sozinho.

Valide a saída. Não confie cegamente no que o solver devolve. Confira:

As alocações respeitam a disponibilidade declarada?
Cada turno bate a cobertura mínima?
As duplas realmente trabalham juntas?
Cada pessoa cumpre o número exigido de turnos (e a regra de periodicidade dos quinzenais)?

Encontrei problemas aqui que não eram óbvios olhando só para as restrições.

A função objetivo é o produto. O modelo base resolvia rápido, mas a qualidade da escala dependia de escolhas do solver que você não controla. O minimax demorou um pouco mais na minha máquina (cerca de 0.24s vs 0.1s) e removeu o pior excesso de lotação.

Um benefício subestimado de MIP: dá para responder “por que essa escala?” com algo melhor do que achismo.

O código

A implementação usa PuLP para modelagem MIP com HiGHS como solver (ambos gratuitos e de código aberto), Polars para manipulação de dados rápida e notebooks Jupyter para desenvolvimento interativo.

Código-fonte e notebooks: github.com/olavocarvalho/otimizador-escalas-mip

Além de turnos

A mesma abordagem serve para muitos problemas de alocação: grade de aulas com restrições de sala, roteirização de entregas, alocação de recursos em infraestrutura de nuvem, chaves de torneio, distribuição de tarefas em gestão de projetos.

Se você consegue escrever como variáveis binárias com restrições lineares, é bem provável que MIP resolva.

Está resolvendo um problema de escalas? Me encontre no LinkedIn ou no Twitter.