Quando as matheurísticas superam a otimização clássica: lições de um problema real de programação da produção

Por que a programação da produção é mais complexa do que parece

A programação da produção é um dos problemas de otimização mais comuns no setor industrial. Quando bem executada, pode gerar melhorias concretas para o negócio, como o aumento dos níveis de serviço e da eficiência das máquinas por meio da redução dos tempos de preparação (setup). No entanto, resolver esses problemas não é tão simples quanto parece.

Na indústria de papel, especificamente, a programação das linhas de conversão, nas quais grandes bobinas de papel são cortadas em folhas utilizadas no dia a dia, é extremamente complexa, envolvendo múltiplas máquinas, diferentes SKUs e diversas decisões interdependentes. O desafio torna-se ainda maior porque, devido às limitações práticas do ambiente industrial, os algoritmos frequentemente precisam encontrar soluções dentro de um tempo máximo de execução.

O exemplo real apresentado aqui envolve a programação de mais de 100 ordens de produção, distribuídas por 6 máquinas ao longo de uma semana, em uma das maiores fabricantes de papel do mundo.

Essa programação também precisa respeitar diversas restrições comuns aos processos produtivos, como a disponibilidade de estoque proveniente de etapas anteriores, a disponibilidade das máquinas e os tempos de preparação (setup) que variam conforme a sequência das ordens de produção, entre outras.

Tudo isso enquanto se busca equilibrar os níveis de estoque, os níveis de serviço e a eficiência das máquinas!

Os limites da otimização clássica

Nesse contexto, a otimização clássica consiste em formular matematicamente o problema por meio de um modelo de Programação Linear Inteira Mista (Mixed-Integer Linear Programming — MILP) e utilizar um software de otimização (solver) que aprimora iterativamente a solução e, com tempo suficiente, pode encontrar a solução ótima global. A imagem abaixo apresenta uma explicação simplificada de como esses modelos funcionam.

Como é possível imaginar, para que um solver consiga melhorar progressivamente uma solução, ele precisa primeiro encontrar uma solução viável — o que pode ser particularmente difícil em problemas grandes e complexos.

Em um problema de otimização da programação da produção, por exemplo, o número de variáveis de decisão — que determinam o espaço de soluções possíveis — cresce rapidamente à medida que aumenta a quantidade de ordens de produção.

No nosso caso, o problema apresentava aproximadamente 30 mil variáveis de decisão para 100 ordens de produção. Se esse número dobrasse para 200 ordens, estaríamos diante de cerca de 110 mil variáveis de decisão.

Ainda assim, nossa primeira tentativa foi resolver o problema utilizando métodos clássicos de otimização exata, com o solver Gurobi. No entanto, encontramos uma dificuldade que já era previsível: encontrar uma solução inicial viável, a partir da qual o modelo pudesse trabalhar, era uma tarefa complexa.

Quase 30% do tempo total de execução foi dedicado apenas à busca dessa primeira solução.

nvertendo a estratégia: busca global antes da otimização local

Nesse momento, começamos a avaliar quais outras estratégias poderiam ser utilizadas para enfrentar esse desafio. Decidimos inverter a abordagem: primeiro, realizar uma busca global para encontrar rapidamente uma solução inicial — que sabíamos não ser ótima, mas que seria viável — e, em seguida, aplicar a otimização local com um solver MILP para aprimorar a solução e aproximá-la do resultado ótimo.

Encontrar rapidamente uma solução inicial seria possível por meio de metaheurísticas amplamente estudadas, que podem ser extremamente úteis para gerar soluções de boa qualidade em períodos curtos, embora não garantam a obtenção da solução ótima. Por isso, escolhemos uma das metaheurísticas mais utilizadas: o Algoritmo Genético (Genetic Algorithm — GA).

Desenvolvendo uma solução inicial evolutiva (Evolutionary Warm Start)

Um Algoritmo Genético é um algoritmo evolutivo que simula a dinâmica da seleção natural. Ele começa com uma população de soluções candidatas, chamadas de cromossomos, que evoluem ao longo de sucessivas gerações.

Neste caso, por exemplo, cada cromossomo representa uma sequência completa de ordens de produção distribuídas pelas 6 linhas ao longo de uma semana.

Em cada geração, selecionamos os melhores indivíduos, recombinamos suas características por meio de operações de cruzamento (crossover) e introduzimos variações por meio de mutações.

O principal objetivo é melhorar a função de aptidão (fitness function), que, no nosso caso, corresponde à função objetivo do modelo MILP.

Uma versão simplificada do Algoritmo Genético que desenvolvemos está ilustrada abaixo:

Além do Algoritmo Genético tradicional, incorporamos um pequeno componente de aprendizado por reforço baseado em Q-learning, para selecionar os operadores de cruzamento (crossover) e mutação de forma mais inteligente, em vez de escolhê-los aleatoriamente.

Também ajustamos os parâmetros do Algoritmo Genético utilizando o método Taguchi, o que reduziu drasticamente o número de combinações de parâmetros que precisávamos testar.

Refinando a solução: Fix-and-Optimize

O Algoritmo Genético conseguiu gerar rapidamente uma solução viável, embora ainda estivesse longe da solução ótima.

A etapa seguinte consistia em utilizar essa solução como ponto de partida (warm start) para um modelo MILP, buscando aprimorá-la e aproximá-la do resultado ótimo.

Para isso, optamos por duas estratégias:

1. Utilizar a solução inicial gerada pelo Algoritmo Genético como entrada para um solver de otimização clássica;
2. Utilizar a mesma solução inicial como entrada para uma heurística Fix-and-Optimize.

A heurística Fix-and-Optimize (F&O) funciona de forma iterativa: a cada iteração, uma porcentagem das variáveis de decisão é fixada, enquanto o solver reotimiza as variáveis restantes, que permanecem livres. Dessa forma, o algoritmo explora soluções próximas à melhor solução encontrada até aquele momento, buscando melhorias progressivas.

Como funciona o processo híbrido de otimização

Para entender como essas etapas se conectam do início ao fim, apresentamos abaixo uma versão simplificada do pseudocódigo do processo:

Outra decisão que investigamos foi quanto tempo deveríamos permitir que o Algoritmo Genético executasse para gerar a solução inicial, considerando um limite rigoroso de 30 minutos para todo o processo.

Assim, avaliamos seis configurações diferentes, nas quais o Algoritmo Genético era executado por 30 segundos, 1 minuto, 2 minutos, 5 minutos, 10 minutos ou 15 minutos. O tempo restante, até completar o limite total de 30 minutos, era destinado à aplicação da heurística Fix-and-Optimize ou da otimização exata.

Realizamos uma série de testes para avaliar o desempenho das duas abordagens — solução inicial gerada pelo Algoritmo Genético (GA), seguida de otimização exata ou da heurística Fix-and-Optimize — considerando diferentes tempos de execução para a geração da solução inicial.

Os resultados são apresentados no gráfico abaixo. Como o modelo analisado era um problema de minimização, quanto menor o valor da função objetivo, melhor a solução encontrada.

O que realmente funcionou (e por quê)

Os resultados médios mostram que a combinação da heurística Fix-and-Optimize com o Algoritmo Genético apresentou um desempenho superior ao da abordagem que combina o Algoritmo Genético com a otimização exata, em praticamente todas as configurações de geração da solução inicial (warm start) avaliadas.

A abordagem Fix-and-Optimize alcançou os melhores resultados quando combinada com uma solução inicial gerada pelo Algoritmo Genético durante 5 minutos.

De forma intuitiva, tempos mais curtos para gerar a solução inicial forneceram à heurística F&O informações estruturais insuficientes, resultando em soluções de menor qualidade. Por outro lado, tempos mais longos permitiram gerar soluções iniciais melhores, mas deixaram pouco tempo disponível para o refinamento por meio do modelo MILP. O ponto ideal está em encontrar um equilíbrio entre essas duas etapas.

Em conclusão, para problemas combinatórios complexos, como a programação da produção, podemos combinar os pontos fortes das metaheurísticas com os dos solvers MILP para encontrar soluções melhores, especialmente quando existem limites rigorosos de tempo de execução.

Essa abordagem híbrida merece ser considerada principalmente em problemas nos quais o espaço de soluções possíveis é tão grande que os solvers enfrentam dificuldades para encontrar uma solução inicial viável.

No nosso caso, as metaheurísticas não substituíram o solver MILP. Elas tornaram sua utilização viável na escala de que precisávamos.