💻 computer science

A Benchmarking Suite for Flexible Job Shop Scheduling Problems with Worker Flexibility under Uncertainty

Este artigo apresenta uma suíte abrangente de benchmarking composta por 402 instâncias padronizadas do Problema de Programação de Oficinas Flexíveis estendidas com flexibilidade de trabalhadores e incerteza, projetada para permitir comparações rigorosas, reprodutíveis e entre domínios de diversos solucionadores de otimização por meio de métricas unificadas, ferramentas de visualização e resultados de referência.

Autores originais: David Hutter, Thomas Steinberger, Michael Hellwig

Publicado 2026-05-06

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: David Hutter, Thomas Steinberger, Michael Hellwig

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine um chão de fábrica movimentado. Você tem um conjunto de tarefas a serem concluídas, uma frota de máquinas para realizar o trabalho e uma equipe de trabalhadores para operar essas máquinas. O objetivo é simples: terminar tudo o mais rápido possível. Mas, no mundo real, as coisas se complicam. Uma máquina pode ser mais rápida em uma tarefa do que em outra, um trabalhador pode ser mais rápido em uma tarefa diferente e, às vezes, uma máquina quebra ou um trabalhador pede licença médica.

Este artigo apresenta um novo "Ginásio" para programas de computador (chamados solucionadores) que tentam resolver esse quebra-cabeça de agendamento. Assim como atletas precisam de uma pista padronizada para comparar suas velocidades, esses programas de agendamento precisam de um conjunto justo e consistente de problemas para provar qual é o melhor.

Aqui está uma explicação do que os autores construíram, usando analogias simples:

1. O Problema: Uma Cozinha Caótica

Pense no Problema de Agendamento de Loja de Trabalho Flexível (FJSSP) como uma cozinha de restaurante de alto padrão.

As Tarefas: Diferentes pedidos chegando (por exemplo, um bife, uma salada, uma sopa).
As Máquinas: Os fornos, grelhas e liquidificadores.
O Twist: Diferente de uma cozinha simples onde a grelha apenas cozinha bifes, aqui, a grelha também pode ser capaz de cozinhar a salada se o chef for rápido o suficiente. Isso é "flexibilidade da máquina".

Agora, adicione a Flexibilidade dos Trabalhadores (FJSSP-W).

Os Trabalhadores: Os chefs.
O Novo Twist: Não apenas a grelha pode cozinhar a salada, mas qual chef está segurando a espátula importa. O Chef A pode levar 5 minutos para grelhar um bife, enquanto o Chef B leva 7 minutos. O computador precisa descobrir não apenas qual máquina usar, mas qual trabalhador específico deve operá-la para realizar a tarefa o mais rápido possível.

2. O Jeito Antigo: Jogando com Regras Diferentes

Anteriormente, pesquisadores tentando construir computadores de agendamento melhores eram como pessoas tentando comparar corredores em pistas diferentes.

Um pesquisador testou seu programa em uma pista pequena e fácil.
Outro testou o seu em um campo enorme e lamacento.
Alguns usaram "tempo perfeito" (sem falhas), enquanto outros usaram "chuva e vento" (incerteza).

Como as pistas de teste eram tão diferentes, não era possível dizer se um corredor era realmente mais rápido ou apenas tinha um percurso mais fácil. Isso tornava difícil saber qual programa de computador era verdadeiramente o melhor.

3. A Nova Solução: Um "Estádio Olímpico" Padronizado

Os autores criaram um Conjunto de Benchmarking. Pense nisso como um enorme estádio olímpico padronizado com 402 pistas diferentes.

A Coleção: Eles pegaram 402 cenários de fábrica existentes e os atualizaram todos para incluir a regra de "Flexibilidade dos Trabalhadores". Isso cria uma enorme biblioteca pronta para uso de problemas.
A Estação Meteorológica de "Incerteza": Fábricas reais não são perfeitas. Máquinas quebram e trabalhadores ficam cansados. Este novo conjunto permite que os pesquisadores injetem "caos" no teste. Eles podem simular:
- Ruído no Tempo de Processamento: Um trabalhador pode ser ligeiramente mais rápido ou mais lento do que o habitual (como um corredor tendo um dia bom ou ruim).
- Falhas de Máquina: Uma máquina para de funcionar repentinamente (como um corredor tropeçando).
- Indisponibilidade do Trabalhador: Um trabalhador não consegue aparecer (como um corredor se machucando).

4. Como Funciona: O "Placar"

O conjunto não é apenas uma lista de problemas; é um kit de ferramentas completo:

O Filtro: Você pode escolher tipos específicos de pistas (por exemplo, "Mostre-me apenas as fábricas com 10 máquinas e alta flexibilidade dos trabalhadores"). Isso ajuda os pesquisadores a testar partes específicas de seus programas.
A Linha de Base: O conjunto vem com uma pontuação "Padrão Ouro". Ele informa o melhor tempo possível alcançado por programas de ponta até agora. Se seu novo programa não conseguir superar essa pontuação, não está pronto para as Olimpíadas.
Os Visuais: Ele transforma os resultados em gráficos e diagramas de fácil leitura, para que você possa ver de relance qual programa é o "Campeão Olímpico".

5. A Primeira Corrida: Quem Venceu?

Os autores testaram alguns programas de computador diferentes neste novo estádio para ver como funcionava:

O Solucionador "Ganancioso": É como um corredor que apenas escolhe a próxima pista disponível sem pensar à frente. Foi o mais lento.
O Solucionador "MILP" (Programação Linear Inteira Mista): É um corredor muito rigoroso e matemático que tenta calcular cada possibilidade individual. Foi preciso, mas ficou preso nas pistas grandes e complexas (esgotando a memória).
O Solucionador "CP" (Programação por Restrições): Este corredor foi o vencedor claro. Lidou com a complexidade de atribuir trabalhadores e máquinas muito melhor do que os outros.
O Solucionador "GA" (Algoritmo Genético): Este corredor ficou em segundo lugar forte, usando um método inspirado na evolução (tentativa e erro) para encontrar boas soluções.

Por Que Isso Importa

Antes deste artigo, os pesquisadores estavam gritando para o vazio, cada um afirmando que seu programa era o melhor com base em seus próprios testes minúsculos e únicos. Este artigo constrói uma linguagem comum e um campo de jogo justo.

Permite que os cientistas digam: "Meu programa é melhor que o seu porque ambos rodamos exatamente nas mesmas 402 pistas, sob exatamente as mesmas condições climáticas." Isso ajuda todo o campo a avançar mais rápido, levando a um software melhor que, eventualmente, pode ajudar fábricas reais a operar com mais eficiência, mesmo quando as coisas dão errado.

Em resumo: Eles construíram um "ginásio" padronizado, justo e caótico onde computadores de agendamento podem finalmente competir em pé de igualdade para ver quem é verdadeiramente o melhor em organizar uma fábrica movimentada.

Resumo Técnico: Uma Suite de Benchmarking para Problemas de Agendamento de Oficina Flexível com Flexibilidade de Trabalhadores sob Incerteza

Definição do Problema
O artigo aborda o Problema de Agendamento de Oficina Flexível (FJSSP) e sua extensão, o Problema de Agendamento de Oficina Flexível com Flexibilidade de Trabalhadores (FJSSP-W). Enquanto o FJSSP clássico envolve a atribuição de operações a máquinas elegíveis para minimizar uma função de custo (tipicamente o makespan), o FJSSP-W integra ainda a atribuição da força de trabalho. Neste problema estendido, uma operação deve ser atribuída não apenas a uma máquina específica, mas também a um trabalhador elegível, onde a combinação específica máquina-trabalhador determina o tempo de processamento.

Uma lacuna significativa identificada na literatura é a falta de um ambiente de benchmarking padronizado e sistemático para esses problemas, particularmente ao incorporar incerteza (por exemplo, tempos de processamento estocásticos, falhas de máquinas e indisponibilidade de trabalhadores). A pesquisa existente frequentemente depende de conjuntos de instâncias fragmentados e ad hoc ou casos reais específicos que dificultam a comparação entre domínios de solvers de diferentes paradigmas de otimização (Programação Matemática, Programação por Restrições e Otimização Baseada em Simulação).

Metodologia e Construção do Benchmark
Os autores propõem uma suite de benchmarking abrangente e de código aberto implementada em Python. A metodologia envolve três componentes principais:

Coleta e Extensão de Instâncias:
- A suite é construída sobre uma coleção curada de 402 instâncias distintas de FJSSP extraídas de dez fontes estabelecidas (por exemplo, Brandimarte, Hurink, Kacem).
- Essas instâncias são sistematicamente estendidas para criar instâncias de FJSSP-W. O processo de extensão atribui um conjunto de trabalhadores ( $W$ ) a cada combinação máquina-operação.
- Lógica de Atribuição de Trabalhadores: Para cada par operação-máquina, um número aleatório de trabalhadores elegíveis é amostrado. Os tempos de processamento para essas novas combinações são gerados amostrando de uma distribuição centrada no tempo de processamento original da máquina (intervalo padrão: 90% a 110% do tempo base).
- Caracterização: A suite documenta características específicas das instâncias, incluindo o número de trabalhos ( $n$ ), máquinas ( $m$ ), trabalhadores ( $w$ ), operações ( $N$ ), flexibilidade ( $\beta$ ) e variedade de duração ( $d_v$ ), permitindo filtragem baseada em características.
Modelagem de Incerteza via Simulação de Eventos Discretos (DES):
- O ambiente suporta a simulação de três tipos de incerteza: variabilidade do tempo de processamento, falhas de máquinas e indisponibilidade de trabalhadores.
- Tempos de Processamento: Modelados usando distribuições Beta para simular velocidades de trabalho inconsistentes.
- Falhas de Máquinas: Modeladas usando distribuições Exponenciais para ocorrência (média de uma falha por cronograma) e distribuições Weibull para duração (mínimo de 10% do makespan livre de ruído).
- Indisponibilidade de Trabalhadores: Também modelada com distribuições Exponenciais (frequência menor) e Weibull (duração mais longa, mínimo de 50% do makespan livre de ruído).
- As soluções são representadas como Grafos Acíclicos Direcionados (DAGs) para facilitar a travessia e simulação desses eventos estocásticos.
Framework de Avaliação:
- A suite fornece APIs para carregar instâncias, traduzir codificações (por exemplo, entre FJSSP e FJSSP-W) e avaliar desempenho.
- Métricas: O objetivo principal é minimizar o makespan. Para simulações de incerteza, o makespan robusto ( $C_r$ ) é calculado como o makespan real médio em múltiplas execuções de simulação.
- Análise Estatística: O framework inclui ferramentas para classificação estatística (testes de Friedman e Nemenyi) e visualização (por exemplo, diagramas de Nemenyi) para comparar rigorosamente o desempenho dos solvers.

Principais Contribuições

Coleção de Benchmark Padronizada: A criação de um portfólio fixo de 402 instâncias de FJSSP-W, garantindo reprodutibilidade e comparabilidade entre estudos.
Suite de Código Aberto: Um ambiente baseado em Python que suporta múltiplos paradigmas de otimização (MILP, CP, Algoritmos Evolutivos) fornecendo representações de modelo necessárias e funções de avaliação.
Integração de Incerteza: Um método sistemático para injetar estocasticidade em instâncias de problemas, permitindo o desenvolvimento e avaliação de estratégias de otimização robusta.
Resultados de Referência: Fornecimento de resultados "melhor conhecidos" derivados de solvers de última geração (Gurobi, IBM CPLEX/OR-Tools e Algoritmos Genéticos) sob um limite de tempo padronizado (20 minutos) e configuração de hardware.

Resultados Experimentais
Os autores demonstraram a suite comparando quatro solvers nas 402 instâncias de FJSSP-W:

Programação por Restrições (CP): Superou significativamente outras abordagens, alcançando um desvio relativo ( $\delta_{rel}$ ) inferior a 0,25 em mais de 80% das instâncias.
Algoritmo Genético (GA): Desempenhou-se bem, superando significativamente as abordagens MILP e Gananciosa, embora ficando atrás do CP.
Programação Linear Inteira Mista (MILP): Lutou com a escala do problema; muitas instâncias não puderam ser resolvidas dentro do limite de tempo devido a restrições de memória e contagem de variáveis.
Algoritmo Ganancioso: Serviu como referência, apresentando o pior desempenho.

Em simulações de robustez (usando a instância Fattahi20), o framework visualizou com sucesso a degradação de cronogramas sob incerteza, calculando o makespan robusto e o quociente de robustez ( $R$ ) para avaliar a estabilidade do cronograma.

Significado e Alegações
O artigo afirma que este trabalho estabelece uma fundação para o desenvolvimento direcionado de algoritmos e avaliação consistente de desempenho na pesquisa de agendamento de produção. Ao abordar a fragmentação nas práticas atuais de benchmarking, a suite permite:

Comparação Justa: Avaliação rigorosa e reprodutível entre diferentes solvers e subdomínios de problemas.
Desenvolvimento de Algoritmos: Suporte para o desenvolvimento de operadores para grupos específicos de problemas através de filtragem de instâncias.
Avaliação de Robustez: A capacidade de avaliar como os solvers lidam com incertezas do mundo real, indo além da otimização determinística.

Os autores enfatizam que, embora a suite seja projetada principalmente para Otimização Baseada em Simulação (SBO) e Algoritmos Evolutivos, sua provisão de representações de modelo para MILP e CP permite comparação entre paradigmas. Eles defendem o uso do conjunto fixo de instâncias para garantir reprodutibilidade científica e chamam por transparência na divulgação de parâmetros experimentais e especificações de hardware para facilitar pesquisas futuras.