A Genetic Algorithm with Critical‑Path‑Driven Dual‑Neighborhood Search for Flexible Job Shop Scheduling

Resumo Técnico: Um Algoritmo Genético com Busca de Vizinhança Dupla Baseada no Caminho Crítico para Programação Flexível de Oficinas

Definição do Problema
O artigo aborda o Problema de Programação de Oficinas Flexíveis (FJSP - Flexible Job Shop Scheduling Problem), um desafio de otimização fortemente NP-difícil, prevalente na manufatura moderna. Diferente do Problema de Programação de Oficinas Clássico (JSP), onde as operações possuem atribuições de máquinas fixas, o FJSP permite que cada operação seja processada em qualquer máquina de um conjunto de candidatos alternativos, frequentemente com tempos de processamento variados. O objetivo principal é minimizar o makespan ($C_{max}$), definido como o tempo de conclusão máximo de todos os trabalhos. O problema envolve determinar tanto a seleção de máquinas para cada operação quanto a sequência de processamento em cada máquina, satisfazendo as restrições de precedência e a disponibilidade das máquinas.

Metodologia: HGVNSA
Os autores propõem um Algoritmo de Busca de Vizinhança Variável Híbrido Genético (HGVNSA) que integra um Algoritmo Genético (GA) para exploração global com uma Busca de Vizinhança Variável (VNS) baseada no Caminho Crítico para explotação local.

1. Codificação e Decodificação: A solução é representada por uma codificação de duas camadas: um vetor de Sequência de Operações (OS) e um vetor de Seleção de Máquinas (MS). Uma estratégia de decodificação ativa é empregada para gerar cronogramas viáveis.
2. Inicialização da População: Para equilibrar qualidade e diversidade, a população inicial é gerada usando uma estratégia híbrida: Seleção Global (60%, minimizando o incremento de carga global), Seleção Local (30%, equilibrando a carga dentro dos trabalhos) e Seleção Aleatória (10%).
3. Operações Genéticas:
   • Crossover: Um operador de crossover baseado em Path-Relinking (PR) é introduzido. Em vez de uma troca aleatória de genes, ele transforma sistematicamente uma solução pai em outra, registrando e avaliando soluções intermediárias para explorar o espaço de busca entre os pais.
   • Mutação: Um mecanismo de mutação adaptativa ajusta as probabilidades com base na aptidão (fitness) do indivíduo e na contagem de gerações. Dois tipos de mutação são usados: mutação de OS (embaralhando a ordem das operações) e mutação de MS (alterando as atribuições de máquinas).
   • Preservação da Diversidade: Uma estratégia baseada em distância de Hamming é empregada para manter a diversidade da população e evitar a convergência prematura.
4. VNS de Vizinhança Dupla Baseada no Caminho Crítico: Incorporada à estrutura do GA, esta busca local foca nas operações localizadas no caminho crítico (o caminho mais longo no grafo disjuntivo). Ela utiliza duas estruturas de vizinhança complementares:
   • Vizinhança N8: Otimiza a sequência de operações na mesma máquina. Ela estende os movimentos tradicionais N5-N7 ao permitir que operações críticas fora de blocos críticos sejam movidas para as extremidades dos blocos ou para posições pré/pós-bloco.
   • Vizinhança k-Inserção: Realoque operações críticas para diferentes máquinas. Isso envolve percorrer máquinas alternativas e inserir a operação em posições viáveis, verificando dependências cíclicas.
   • Estratégia de Busca: O processo VNS prioriza a vizinhança N8 (menor custo computacional) e muda para a k-inserção (maior custo, busca mais ampla) apenas se nenhuma melhoria for encontrada, garantindo um equilíbrio entre eficiência e profundidade de exploração.

Principais Contribuições
O artigo delineia cinco contribuições principais:

1. Estrutura Híbrida: Estabelece um framework sinérgico de "exploração global primeiro, explotação local posteriormente", equilibrando efetivamente a precisão da solução e a eficiência computacional.
2. Integração de Vizinhança Dupla: É o primeiro a integrar as vizinhanças N8 e k-inserção dentro de um framework VNS unificado para FJSP. Esta combinação aborda tanto o sequenciamento intra-máquina quanto o realocamento inter-máquina, aumentando significativamente a capacidade de busca local.
3. Operadores Genéticos Aperfeiçoados: A introdução do crossover de Path-Relinking e das probabilidades de mutação adaptativas fortalece a capacidade do algoritmo de explorar o espaço de soluções e manter a estabilidade da convergência.
4. Desempenho em Benchmarks: No conjunto de benchmarks Brandimarte MK, o HGVNSA alcança consistentemente soluções ótimas conhecidas em 6 de 10 instâncias (MK01-MK04, MK08-MK09) e apresenta o menor Desvio Percentual Relativo (RPD) médio de 0,06% entre os algoritmos comparados (HGWO, HLO-PSO, HA, SLGA, ISLGA).
5. Aplicação no Mundo Real: O algoritmo foi aplicado a um cenário de processamento de eixo de engrenagem na Empresa A. Comparado a um Algoritmo Genético tradicional, o HGVNSA melhorou a eficiência da produção em 8,81%, demonstrando sua praticidade de engenharia.

Resultos e Validação

• Testes de Benchmark: Experimentos extensivos nas instâncias MK01-MK10 mostraram que o HGVNSA superou os algoritmos de comparação em termos de qualidade de solução e estabilidade. Estudos de ablação confirmaram que a remoção do componente VNS, da estrutura de vizinhança dupla ou dos mecanismos adaptativos levou a uma degradação significativa do desempenho (por exemplo, remover o VNS aumentou o makespan médio de MK02 de 26 para 30,4).
• Estudo de Caso: No estudo de caso da Empresa A, envolvendo 10 trabalhos e 59 operações em 15 máquinas, o algoritmo reduziu o makespan de 522 (GA tradicional) para 476.
• Convergência: A análise de convergência indicou que, enquanto outros algoritmos estagnavam após uma convergência inicial rápida, o HGVNSA continuava a refinar as soluções através de seus mecanismos de busca local, rompendo ótimos locais em iterações posteriores.

Significância
O artigo afirma que o HGVNSA fornece um framework de solução eficiente e robusto para o FJSP, abordando efetivamente os desafios de equilibrar a busca global e local e projetar estruturas de vizinhança eficazes. O estudo valida que a combinação de busca local baseada no caminho crítico com evolução genética produz resultados superiores tanto em benchmarks teóricos quanto em ambientes industriais práticos. Os autores sugerem que este trabalho estabelece uma base para pesquisas futuras em programação distribuída e no uso de aprendizado por reforço profundo para seleção inteligente de vizinhança, embora não aleguem que essas extensões tenham sido implementadas no presente estudo.