The Price of Optimality Under Uncertainty: A Predictive–Reactive Robustness Analysis of Exact, Metaheuristic, and Dispatching-Rule Scheduling for the Dynamic Job-Shop Problem

Resumo Técnico: O Preço da Otimalidade sob Incerteza

Definição do Problema
Este estudo aborda o Problema de Escalonamento de Job-Shop Dinâmico (JSSP) sob incerteza. Embora o JSSP seja um problema canônico NP-difícil, tipicamente resolvido para minimizar o makespan ($C_{max}$) em benchmarks determinísticos, as oficinas reais estão sujeitas a três principais interrupções: quebras de máquinas, tempos de processamento estocásticos e a chegada dinâmica de novos trabalhos. A questão central de pesquisa investiga se um cronograma que é ótimo sob dados nominais (determinísticos) permanece preferível quando executado sob essas interrupções. O artigo compara o "preço da otimalidade" — o compromisso entre alcançar um cronograma teoricamente perfeito e manter a robustez quando a realidade diverge do plano.

Metodologia
O autor emprega uma comparação controlada de nível de paradigma usando um aparato de avaliação preditivo-reativo de eventos discretos. O estudo avalia três famílias distintas de soluções através de dezesseis instâncias de benchmark de Fisher–Thompson e Lawrence (variando de $6\times6$ a $20\times10$) sob nove regimes de interrupção (três severidades para cada uma de: quebras, tempos estocásticos e chegadas dinâmicas).

1. Paradigmas de Solução:

   • Solver Exato (CP-SAT): Um solver de programação de restrições que produz um cronograma preditivo certificado como ótimo (ou quase ótimo). Isso representa o "teto de qualidade" para dados nominais.
   • Metaheurística (Algoritmo Genético - GA): Um algoritmo genético baseado em permutação com um orçamento computacional fixo, produzindo cronogramas preditivos de alta qualidade, mas não certificados.
   • Regras de Despacho de Prioridade (PDRs): Nove regras online (SPT, LPT, MWKR, LWKR, MOR, LOR, FIFO, EDD, CR) que tomam decisões reativamente em cada evento, sem um cronograma pré-computado.

2. Políticas de Execução e Reparo:

   • Os métodos offline (CP-SAT e GA) utilizam uma política de reparo por deslocamento à direita (right-shift). A sequência de operações comprometida é fixa; as interrupções atrasam as operações, mas não as reordenam.
   • As PDRs operam online, redecidindo prioridades a cada evento.
   • As chegadas dinâmicas são tratadas pela absorção de novos trabalhos em intervalos de máquinas ociosas, uma restrição que cronogramas pré-computados não conseguem antecipar.

3. Desenho Experimental:

   • Modelos de Interrupção: Quebras de máquina seguem um processo de renovação calibrado para disponibilidades alvo ($A_k \in \{0.95, 0.80\}$); tempos de processamento utilizam um multiplicador log-normal de média unitária ($s \in \{0.10, 0.50\}$); chegadas dinâmicas seguem um processo de Poisson calibrado para utilizações alvo ($\rho \in \{0.70, 0.95\}$).
   • Métricas:
     • Índice de Robustez (RI): Degradação relativa do makespan sob interrupção em comparação com o próprio makespan nominal do método.
     • Desvio Percentual Relativo Realizado (RPD): O desvio do makespan perturbado contra o ótimo certificado, permitindo a comparação de qualidade real entre os métodos.
   • Protocolo Estatístico: A análise inclui 30 réplicas de cenários por célula (47.520 execuções no total). Comparações pareadas utilizam o teste de postos sinalizados de Wilcoxon exato; classificações conjuntas utilizam o teste de Friedman com análise post-hoc de Nemenyi.

Resultos Principais
O estudo relata uma inversão decisiva entre qualidade nominal e robustez:

1. Desempenho Nominal: Como esperado, o solver exato (CP-SAT) domina, alcançando um RPD médio de 3,08% acima do ótimo, seguido pelo GA (6,28%). As melhores regras de despacho (MWKR, MOR) ficam significativamente atrás (12,07% e 14,15% RPD).
2. Classificação de Robustez: A classificação inverte-se sob interrupção. O solver exato e o GA são os métodos menos robustos (ranks de Friedman 10,14 e 9,82, respectivamente), enquanto todas as regras de despacho são significativamente mais robustas (ranks 3,95–5,77). A compactação ótima do solver exato não deixa folga para absorver atrasos, fazendo com que cada interrupção se propague totalmente.
3. Cruzamento de Qualidade Realizada:
   • Quebras de Máquina: As regras MWKR e MOR superam o solver exato em qualidade realizada (42,97% e 43,20% RPD vs. 46,07% para o CP-SAT).
   • Tempos de Processamento Estocásticos: O solver exato mantém uma liderança estreita, mas a vantagem nominal encolhe de ~9% para <3%.
   • Chegadas Dinâmicas: As regras online dominam categoricamente. O solver exato e o GA tornam-se os dois piores métodos (175,30% e 177,02% RPD) porque um cronograma comprometido não pode planejar para trabalhos que chegam após a geração do cronograma.

Principais Contribuições

1. Comparação de Robustez em Nível de Paradigma: O estudo fornece a primeira comparação direta entre um solver exato, uma metaheurística e um conjunto completo de regras de despacho em um aparato preditivo-reativo comum e estatisticamente controlado.
2. Evidência da Inversão Otimalidade–Robustez: Quantifica que o cronograma exato-ótimo é simultaneamente o melhor método nominal e o menos robusto, com a classificação de robustez essencialmente revertendo a classificação de qualidade nominal.
3. Identificação de Limiares de Interrupção: O artigo identifica que, além de níveis de interrupção leves, a vantagem nominal do solver exato erode e se inverte, com regras de despacho simples (especificamente MWKR e MOR) entregando cronogramas realizados superiores.
4. Esclarecimento Metodológico: O estudo destaca a distinção entre degradação relativa (RI) e qualidade realizada (RPD). Demonstra que confiar apenas no RI pode ser enganoso, pois regras com cronogramas nominais ruins (como EDD) parecem "robustas" simplesmente porque têm menos espaço para degradar, enquanto regras como MWKR combinam um desempenho nominal competitivo com uma degradação suave.

Significância e Alegações
O artigo conclui que a otimalidade exata e a robustez à interrupção são objetivos conflitantes no job shop dinâmico. O "preço da otimalidade" é alto: um cronograma otimamente compacto é estruturalmente frágil porque carece da folga necessária para absorver a incerteza.

O autor argumenta que, para ambientes propensos a interrupções, uma regra de despacho simples e sem custo de computação (especificamente MWKR ou MOR) não é meramente um recurso de contingência, mas frequentemente a política implementada superior. Essas regras atuam como mecanismos de balanceamento de carga que naturalmente redirecionam o esforço em torno das interrupções sem a necessidade de replanejamento de maquinário. O estudo sugere uma política contingente à interrupção: a resolução exata vale a pena apenas em regimes quase determinísticos; conforme a interrupção se intensifica, o caso para solvers exatos enfraquece rapidamente, e as regras online tornam-se a escolha ideal para o desempenho realizado. Os achados desafiam a intuição derivada de benchmarks determinísticos, sugerindo que, em ambientes dinâmicos, o "bom o suficiente" da adaptabilidade online frequentemente supera o planejamento offline "perfeito".