Resumo Técnico: DynaSchedBench

Declaração do Problema

O campo da Otimização Combinatória Neural (NCO) para o Problema de Programação de Trabalho Dinâmico e Flexível (DFJSP) enfrenta uma tensão metodológica que impede o progresso. Os benchmarks estáticos existentes (por exemplo, Taillard, DMU) incentivam o sobreajuste, onde os agentes memorizam estruturas específicas de instâncias em vez de aprender políticas generalizáveis. Por outro lado, as tentativas de gerar instâncias dinâmicas frequentemente dependem de amostragem procedural não calibrada, onde a dificuldade surge como um subproduto descontrolado de sementes aleatórias. Isso introduz uma "névoa estocástica" de alta variância, tornando impossível distinguir inovação algorítmica genuína de sequências favoráveis de eventos dinâmicos. Além disso, o surgimento de Modelos de Linguagem de Grande Escala (LLMs) como agentes de programação carece de um quadro de avaliação rigoroso para testar suas capacidades de raciocínio contra solucionadores estabelecidos em um ambiente controlado e distribucionalmente sólido.

Metodologia: Estrutura DynaSchedBench

Os autores introduzem o DynaSchedBench, um quadro de diagnóstico projetado para gerar instâncias de benchmark calibradas e fundamentadas teoricamente para o DFJSP. O quadro consiste em quatro componentes principais:

1. Calibrador de Espaço de Eventos Sequencial (SESC)

Em vez de otimizar hiperparâmetros gerativos em um espaço de parâmetros (o que é computacionalmente caro e propenso a instabilidade), o DynaSchedBench emprega o SESC. Este módulo opera diretamente no fluxo de eventos discretos realizados $E$. Ele aplica uma sequência de transformações estruturais locais (operadores) para ajustar o fluxo de eventos a métricas-alvo.

• Estratégias de Ajuste: O quadro utiliza um catálogo de estratégias que inclui Ajuste de estrutura de chegada (correção de taxa, reamostragem de renovação), Escala adaptativa de folga (modificando a rigidez das datas de entrega), Reamostragem isomórfica de tempo de processamento (corrigindo variabilidade enquanto preserva a carga de trabalho total) e Engenharia de gargalo (controle granular sobre a perda de capacidade).
• Loop de Calibração: Uma busca gulosa seleciona operadores que minimizam o vetor de erro normalizado entre as métricas observadas e as métricas-alvo, preservando métricas que já estão dentro da tolerância.

2. Índice de Estresse de Programação (SSI)

Para quantificar a dificuldade da instância, os autores propõem o Índice de Estresse de Programação (SSI). Esta métrica mapeia métricas empíricas brutas em um vetor de dificuldade de quatro componentes:

• Congestionamento ($C$): Baseado em aproximações de tráfego intenso no estilo de Kingman, utilizando a utilização natural do gargalo e a variabilidade.
• Pressão Temporal ($P$): O inverso da folga empírica.
• Complexidade Estrutural ($K$): Uma medida normalizada do número de máquinas e da profundidade da operação.
• Intensidade de Disrupção ($S$): Uma medida normalizada das razões de perturbação realizadas (por exemplo, falhas).
  Estes componentes são comprimidos por logaritmo e médios para produzir uma pontuação de dificuldade escalar $d \in [0, 100]$.

3. Pilha de Simulação e Avaliação Modular

O quadro fornece um ambiente compatível com Gym com:

• Simulação Baseada em Instantâneos: Garante observações imutáveis para agentes, apoiando tanto políticas sem memória quanto planejadores de antecipação.
• Motor Baseado em Trajetória: Persiste rastros de execução para verificação reproduzível de restrições (precedência, não sobreposição de recursos) e computação de métricas de desempenho.
• Níveis de Observabilidade: Define três níveis de acesso à informação para agentes:
  • L1: Visão local (trabalhos prontos, disponibilidade de máquinas).
  • L2: L1 + estatísticas locais (comprimentos de fila, fatores de folga).
  • L3: L2 + priores estruturais (pontuações de gargalo, objetivos de projeto).

4. Avaliação de Agentes LLM

O quadro avalia agentes baseados em LLM usando vários modos de prompt (Direto, Cadeia de Pensamento, Aumentado por Ferramentas) e estratégias de refinamento (Reflexão, Melhor-de-N). Ele mede o desempenho por meio do makespan normalizado ($C_{max}$) em relação ao melhor cronograma observado e rastreia o consumo de tokens para avaliar compensações custo-desempenho.

Resultados Principais

Desempenho de Calibração

• Eficiência e Estabilidade: O SESC supera significativamente as bases evolutivas (Otimização Multi-Objetivo e abordagens Híbridas) em eficiência computacional e estabilidade. O SESC alcança um tempo de execução de calibração mediano de 0,2 segundos, comparado a 57,9 segundos para OMO e 185,8 segundos para Híbrido.
• Precisão: O SESC demonstra estabilidade algorítmica superior com menor perda média normalizada ($\tilde{\ell}_2 \approx 0,0539$) e dispersão mínima de semente para semente em comparação com as bases.
• Correlação de Dificuldade: A pontuação SSI está positivamente correlacionada com a lacuna de programação entre um programador aleatório e a melhor heurística fixa ($\rho = 0,563$), validando sua utilidade como proxy para dificuldade de programação.

Descobertas de Programação com LLM

• O Paradoxo da Observabilidade: Fornecer aos agentes priores estruturais completos (L3) degrada o desempenho em comparação com resumos estatísticos concisos (L2). Agentes CoT L2 alcançaram um makespan excedente médio normalizado de 0,7%, enquanto agentes CoT L3 degradaram para 1,66%. Isso sugere que os LLMs atuais lutam para destilar sinais úteis de ruído estrutural de alta dimensão.
• Ineficiência da Sondagem Ativa: Estratégias aumentadas por ferramentas (L1+Ferramenta) incorreram em um aumento triplicado no consumo de tokens sem melhorar o desempenho sobre o CoT L1 padrão, destacando um "gargalo de integração de informações".
• Paridade Heurística: Apesar de substancial sobrecarga de tokens e estratégias avançadas de raciocínio (Reflexão, Melhor-de-N), os LLMs não conseguem superar consistentemente regras fortes de despacho de prioridade (PDRs) criadas manualmente. Os principais LLMs (por exemplo, Qwen3-8B) performaram estatisticamente indistinguíveis das melhores heurísticas fixas (por exemplo, LIFO+LIT), caracterizando-os como aproximadores heurísticos robustos em vez de otimizadores superiores.

Significado e Alegações

O artigo alega resolver a crise de avaliação na programação dinâmica ao fornecer um quadro principiado para gerar benchmarks controlados distribucionalmente. Seu significado principal reside em:

1. Rigor Metodológico: Substituir a amostragem não calibrada por um processo de calibração determinístico e baseado em espaço de eventos que permite a estratificação sistemática da dificuldade da instância.
2. Insight Diagnóstico: Revelar o "Paradoxo da Observabilidade", que desafia a suposição de que mais informações (priores estruturais) levam a uma melhor tomada de decisão em agentes baseados em LLM para problemas combinatórios.
3. Expectativas Realistas: Estabelecer que os LLMs atuais, mesmo com prompts avançados e uso de ferramentas, atuam principalmente como aproximadores robustos de heurísticas clássicas em vez de otimizadores transformadores, sugerindo a necessidade de pivotar a pesquisa para planejamento de trajetória multi-etapa em vez de despacho reativo.

Os autores concluem que, sem tais ambientes calibrados, o campo não pode avaliar de forma confiável as capacidades de raciocínio de agentes emergentes, e que a geração atual de LLMs é limitada pelo teto de desempenho das heurísticas clássicas em contextos de programação dinâmica.