Solving Distributed Flexible Job Shop Scheduling Problems in the Wool Textile Industry with Quantum Annealing

Resumo Técnico: Resolvendo Problemas de Escalonamento de Oficinas Flexíveis Distribuídas na Indústria Têxtil de Lã com Recozimento Quântico

Definição do Problema
O artigo aborda o Problema de Escalonamento de Oficinas Flexíveis Distribuídas (DFJSP) no contexto da indústria têxtil de lã. Diferente dos Problemas de Escalonamento de Oficinas (JSSP) tradicionais ou mesmo dos Problemas de Oficinas Flexíveis (FJSP) padrão, o DFJSP envolve locais de produção geograficamente dispersos, onde uma única ordem de produção (job) pode exigir que operações sejam realizadas em diferentes fábricas. Este caso de uso específico, derivado de um fabricante real de têxteis de lã, introduz uma complexidade única: não apenas as ordens de produção estão distribuídas entre os locais, mas os passos individuais de produção (operações) de um único trabalho também podem estar distribuídos. Consequentemente, o modelo deve considerar os tempos de envio entre máquinas localizadas em diferentes fábricas, além dos tempos de processamento padrão e das restrições de máquina. O objetivo é minimizar o makespan (tempo total de conclusão) enquanto satisfaz as restrições de precedência, garantindo que as operações comecem apenas uma vez e evitando sobreposições de máquinas. Este problema é identificado como NP-difícil, e a inclusão dos tempos de envio entre fábricas aumenta significativamente a complexidade combinatória.

Metodologia
Os autores formulam o DFJSP estendido como um problema de Otimização Binária Quadrática Não Restrita (QUBO) para ser resolvido usando um recozedor quântico (QPU) D-Wave Advantage System 4.1.

1. Formulação QUBO: O problema é mapeado para variáveis binárias $x_{i,o,m,t}$, representando se a operação $o$ do trabalho $i$ começa na máquina $m$ no tempo $t$. A função de custo $H(x)$ é construída como uma soma ponderada de funções de penalidade para restrições (precedência, execução única de operação, não sobreposição) e uma função objetivo para minimizar o makesksan.
2. Poda de Variáveis: Para gerenciar o tamanho do problema dentro dos limites físicos da QPU, os autores empregam a poda de variáveis. Isso envolve o cálculo de limites inferiores e superiores para os tempos de início das operações com base nos tempos mínimos de predecessores e nos limites máximos de makespan, eliminando assim as variáveis binárias que correspondem a cronogramas inválidos.
3. Determinação de Parâmetros: Uma etapa metodológica crítica envolve o cálculo sistemático dos parâmetros de Lagrange ($\alpha, \beta, \gamma$) para os termos de penalidade. Em vez de depender de tentativa e erro, os autores derivam esses pesos matematicamente com base no makespan máximo ($t_{max}$) da instância específica do problema. Isso garante que a energia de qualquer solução válida seja menor que a energia de qualquer solução inválida.
4. Incorporação e Configuração: As variáveis lógicas do QUBO são incorporadas à topologia física da QPU usando cadeias de qubits. Os autores investigam o impacto da "força da cadeia" (chain strength — a força de acoplamento entre os qubits em uma cadeia) na qualidade da solução, determinando valores ideais através da análise do compromisso (trade-off) entre a energia do sistema e a porcentagem de cadeias quebradas.
5. Comparação: Os resultados do recozimento quântico (QA) são comparados com o Recozimento Simulado (SA) usando o D-Wave Ocean SDK. Ambos os métodos são testados em instâncias de problemas variando de 50 a 250 variáveis (o tamanho máximo incorporável na QPU testada), com o SA também sendo testado em instâncias maiores (até 400 variáveis) para estabelecer uma linha de base para o escalonamento computacional.

Principais Contribuições
O artigo descreve três contribuições primárias:

1. Modelo DFJSP Estendido com QA: Os autores apresentam a primeira aplicação conhecida de Recozimento Quântico a um DFJSP estendido, onde tanto as ordens de produção quanto os passos individuais de produção estão distribuídos entre fábricas, modelando explicitamente os tempos de envio entre sites.
2. Cálculo Sistemático de Parâmetros: O artigo detalha um método para determinar os parâmetros de Lagrange e as configurações da QPU (especificamente a força da cadeia) com base na formulação matemática do problema, afastando-se de abordagens heurísticas de tentativa e erro.
3. Avaliação Econômica e de Desempenho: O estudo avalia o potencial de vantagem de velocidade no uso de QA para o escalonamento distribuído específico da indústria, comparando a qualidade da solução e o tempo de cálculo contra o SA clássico.

Resultos

• Qualidade da Solução: Para instâncias de problemas até 150 variáveis, o QA produziu soluções consistentes e válidas (sem violação de restrições), embora o Recozimento Simulado (SA) geralmente tenha retornado soluções com energia ligeiramente menor (melhor otimalidade). À medida que o tamanho do problema aumentou para 200 e 250 variáveis, as soluções do QA começaram a exibir restrições quebradas (1 e 2 violações, respectivamente), levando a valores de energia mais altos. Essa degradação é atribuída à dificuldade crescente de incorporar problemas lógicos maiores no grafo físico da QPU, resultando em cadeias mais longas e uma taxa maior de quebra de cadeias.
• Makespan: As soluções de QA para a maioria dos tamanhos de problemas situaram-se na metade inferior do intervalo de makespan possível, indicando cronogramas de produção viáveis. No entanto, para a instância de 250 variáveis, o makespan estava na metade superior do intervalo.
• Tempo Computacional: O SA demonstrou tempos de cálculo mais rápidos para pequenos problemas. No entanto, o tempo de CPU do SA cresceu exponencialmente com o tamanho do problema. Em contraste, o tempo de acesso à QPU para o QA aumentou a uma taxa decrescente (logarítmica). Embora as limitações atuais de hardware limitem o QA à incorporação de problemas de até 250 variáveis, a tendência sugere que, para instâncias maiores (extrapoladas além de 300 variáveis), o QA poderia potencialmente oferecer uma vantagem significativa de velocidade sobre o SA.

Significância e Alegações
O artigo alega que, embora o hardware atual de recozimento quântico enfrente limitações para incorporar problemas de grande escala e atingir mínimos globais em comparação com heurísticas clássicas para instâncias pequenas, ele detém um potencial significativo para os desafios específicos de DFJSP da indústria têxtil de lã. Os autores afirmam que o QA oferece uma alternativa promissora para o escalonamento distribuído de grande escala devido ao seu escalonamento favorável de tempo de computação em relação ao tamanho do problema. Eles concluem que, com melhorias futuras de hardware (mais qubits, melhor conectividade e estabilidade), o QA poderá fornecer uma vantagem definitiva de velocidade para instâncias de problemas acima de aproximadamente 300 variáveis, tornando-se uma ferramenta viável para o planejamento de produção multifábrica complexo e do mundo real. O trabalho enfatiza que o sucesso da aplicação do QA depende fortemente de uma formulação cuidadosa do problema, especificamente da derivação matemática dos pesos de penalidade e da otimização dos parâmetros de incorporação.