Low-Cost Labels, Reliable Choices: Rollout-Calibrated Hyper-Heuristics for Job Shop Scheduling

Resumo Técnico: Rótulos de Baixo Custo, Escolhas Confiáveis

Declaração do Problema
O artigo aborda o Problema de Programação de Oficinas (JSSP) através da lente de hiper-heurísticas de seleção. Embora as hiper-heurísticas assistidas por aprendizado ofereçam um meio-termo entre regras de despacho fixas e construtores aprendidos de ponta a ponta, mantendo a viabilidade e a interpretabilidade, elas enfrentam dois gargalos principais:

1. Custo de Geração de Rótulos: O aprendizado supervisionado requer rótulos gerados por "simulação" (rolling out) de regras de despacho candidatas de um agendamento parcial até um estado terminal. Uma simulação completa para cada regra candidata em cada ponto de decisão incorre em um custo computacional de $O(|H|T)$, onde $|H|$ é o número de regras e $T$ é o número de decisões restantes.
2. Confiabilidade da Seleção: Um seletor aprendido pode acidentalmente prever uma leve melhoria sobre uma regra padrão forte devido a ruído ou sobreajuste. Seguir cegamente a pontuação prevista mais baixa pode levar à degradação do desempenho em comparação com uma regra fixa robusta.

Os autores visam estudar o trade-off entre o custo de gerar esses rótulos de supervisão e a confiabilidade do seletor resultante, focando especificamente em como impedir que um modelo aprendido abandone uma regra padrão forte a menos que o ganho previsto seja credível.

Metodologia
A abordagem proposta, denominada Hiper-heurísticas Calibradas por Simulação (Rollout-Calibrated Hyper-Heuristics), integra três componentes principais:

1. Rótulos de Simulação Normalizados por Arrependimento:
   Em vez de usar o makespan bruto ou o makespan normalizado pelo limite inferior como alvo, os autores definem um rótulo de arrependimento por estado:
   $$r(s, h) = \frac{m(s, h) - \min_{h' \in H_s} m(s, h')}{\min_{h' \in H_s} m(s, h')}$$
   onde $m(s, h)$ é o makespan resultante da aplicação da regra $h$ no estado $s$. Isso transforma o alvo em um sinal de classificação local, onde a melhor regra em um estado específico tem um arrependimento de 0, isolando o desempenho relativo das regras dentro desse contexto específico.

2. Seleção com Portão de Incerteza:
   O sistema emprega um regressor de K-Vizinhos Mais Próximos (KNN) contextual para prever o arrependimento para cada regra candidata. Para garantir confiabilidade, um mecanismo de portão é introduzido. O seletor só muda de uma regra padrão fixa ($h_0$, escolhida como a melhor regra fixa no conjunto de treinamento) para uma regra prevista como melhor ($h^*$) se a melhoria esperada exceder uma margem ajustada pela incerteza:
   $$\pi_{gated}(s) = \begin{cases} h^* & \text{se } \hat{r}(s, h_0) - \hat{r}(s, h^*) > \lambda \hat{\sigma}(s, h^*) \\ h_0 & \text{caso contrário} \end{cases}$$
   Aqui, $\hat{\sigma}$ é o desvio padrão dos $k$-vizinhos mais próximos (servindo como estimativa de incerteza) e $\lambda$ é um hiperparâmetro que controla a agressividade da mudança.

3. Trade-off de Orçamento de Simulação:
   Os autores variam explicitamente a largura da simulação ($b$, o número de regras candidatas avaliadas) e a profundidade da simulação ($\kappa$, o número de passos que uma regra candidata é seguida antes de retornar ao padrão) para mapear a fronteira de Pareto entre o custo de geração de rótulos (passos de simulação/tempo de relógio) e o desempenho final de teste (Desvio Percentual Relativo, RPD).

Principais Contribuições

• Um Framework de Seleção Conservador: O artigo propõe um mecanismo de portão que prioriza a confiabilidade sobre a otimização agressiva, garantindo que o seletor aprendido não abandone regras fixas fortes sem alta confiança.
• Supervisão Baseada em Arrependimento: Ao usar arrependimento por estado em vez de makespan absoluto, o método foca na classificação local de regras, o que é mais robusto para a tomada de decisão em agendamentos parciais.
• Análise Explícita de Custo-Qualidade: Diferentemente de muitos trabalhos que tratam a geração de rótulos como uma etapa de pré-processamento fixa, este estudo varia sistematicamente a profundidade e a largura da simulação para quantificar o trade-off custo-qualidade, fornecendo orientações práticas para orçamentos de implantação.
• Reprodutibilidade Apenas em CPU: Todo o pipeline, incluindo geração de rótulos, ajuste do KNN e inferência, é projetado para rodar em CPUs sem aceleração por GPU, contrastando com abordagens de aprendizado por reforço profundo.

Resultados Experimentais
Os experimentos foram conduzidos em instâncias sintéticas de JSSP dos tamanhos $6\times6$, $10\times10$ e $15\times10$.

• Desempenho: O seletor Com Portão de Arrependimento alcançou o menor RPD médio entre todos os métodos aprendidos em todas as escalas. Ele permaneceu muito próximo da melhor regra de despacho fixa (tipicamente FIFO ou MOPNR nestes cenários sintéticos), com lacunas de RPD médias de 0,70, 0,67 e 0,06, respectivamente.
• Robustez: A abordagem com portão reduziu o RPD médio de uma linha de base Random-HH em mais de uma ordem de grandeza (de ~36–54% para ~0,8–2,8%).
• Ablação: O estudo confirmou que o portão é mais estável do que sempre mudar (seleção argmin). Os melhores resultados foram obtidos com rótulos de arrependimento e um limiar de confiança $\lambda=1,0$. Variantes de Limite Inferior de Confiança (LCB) performaram pior, sugerindo que a incerteza é melhor usada como um teste de mudança do que como um bônus direto de pontuação.
• Análise de Custo: Simulações completas ($\kappa=\infty, b=|H|$) produziram a melhor qualidade, mas ao custo mais alto. Simulações rasas ($\kappa=1$) resultaram em RPD significativamente mais alto. Profundidades intermediárias ofereceram um trade-off viável, reduzindo substancialmente os passos de simulação enquanto mantinham qualidade aceitável.

Significado e Alegações
O artigo alega modestamente fornecer um seletor e protocolo de avaliação reproduzíveis, apenas em CPU para estudar custos de rótulos e mudança conservadora em hiper-heurísticas assistidas por aprendizado.

Os autores posicionam seu trabalho como complementar a solucionadores especializados, despachadores de RL profundo (por exemplo, L2D, ScheduleNet) e busca de programas impulsionada por LLM (por exemplo, FunSearch, ReEvo). Enquanto esses sistemas visam pontos diferentes no espaço de design (muitas vezes inventando novos operadores ou políticas de ponta a ponta), este trabalho isola o problema de selecionar entre regras existentes e interpretáveis.

O significado principal reside em abordar o desafio prático de implantação: quanto orçamento de simulação deve ser gasto para gerar rótulos e como garantir que um seletor aprendido não degrade o desempenho mudando com muita frequência. Os autores observam que suas descobertas são específicas aos regimes sintéticos, estáticos e determinísticos testados. Eles reconhecem que a escalabilidade para instâncias industriais ou ambientes dinâmicos (por exemplo, quebras de máquinas, chegadas online) exigiria diferentes trade-offs de custo-qualidade e possivelmente dinâmicas de geração de rótulos diferentes. O trabalho não alega resolver o JSSP em geral, mas oferece um estudo controlado sobre como tornar as hiper-heurísticas assistidas por aprendizado confiáveis e custo-efetivas.