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

Sintesi Tecnica: Un Algoritmo Genetico con Ricerca a Doppio Vicinato Guidata dal Percorso Critico per lo Scheduling Flessibile di Officine (Flexible Job Shop Scheduling)

Definizione del Problema
Il documento affronta il problema dello Scheduling Flessibile di Officine (FJSP), una sfida di ottimizzazione fortemente NP-hard prevalente nella manifattura moderna. A differenza del classico Problema di Scheduling di Officina (JSP), dove le operazioni hanno assegnazioni di macchina fisse, l'FJSP consente che ogni operazione sia elaborata su una qualsiasi macchina appartenente a un insieme di candidati alternativi, spesso con tempi di lavorazione variabili. L'obiettivo primario è minimizzare il makespan ($C_{max}$), definito come il tempo di completamento massimo di tutti i lavori. Il problema comporta la determinazione sia della selezione della macchina per ogni operazione, sia della sequenza di lavorazione su ogni macchina, soddisfacendo al contempo i vincoli di precedenza e di disponibilità delle macchine.

Metodologia: HGVNSA
Gli autori propongono un Algoritmo di Ricerca a Vicinato Variabile Genetico Ibrido (HGVNSA) che integra un Algoritmo Genetico (GA) per l'esplorazione globale con una Ricerca a Vicinato Variabile (VNS) guidata dal Percorso Critico per l'sfruttamento locale.

1. Codifica e Decodifica: La soluzione è rappresentata mediante una codifica a due livelli: un vettore di Sequenza delle Operazioni (OS) e un vettore di Selezione delle Macchine (MS). Viene impiegata una strategia di decodifica attiva per generare programmi ammissibili.
2. Inizializzazione della Popolazione: Per bilanciare qualità e diversità, la popolazione iniziale viene generata utilizzando una strategia ibrida: Selezione Globale (60%, minimizzando l'incremento del carico globale), Selezione Locale (30%, bilanciando il carico all'interno dei lavori) e Selezione Casuale (10%).
3. Operazioni Genetiche:
   • Crossover: Viene introdotto un operatore di crossover basato sul Path-Relinking (PR). Invece di uno scambio casuale di geni, esso trasforma sistematicamente una soluzione genitore in un'altra, registrando e valutando le soluzioni intermedie per sfruttare lo spazio di ricerca tra i genitori.
   • Mutazione: Un meccanismo di mutazione adattiva regola le probabilità in base alla fitness dell'individuo e al numero di generazioni. Vengono utilizzati due tipi di mutazione: mutazione OS (rimescolamento dell'ordine delle operazioni) e mutazione MS (cambio delle assegnazioni delle macchine).
   • Preservazione della Diversità: Una strategia basata sulla distanza di Hamming è impiegata per mantenere la diversità della popolazione e prevenire la convergenza prematura.
4. Ricerca a Doppio Vicinato VNS Guidata dal Percorso Critico: Integrata all'interno del framework GA, questa ricerca locale si concentra sulle operazioni situate sul percorso critico (il percorso più lungo nel grafo disgiuntivo). Utilizza due strutture di vicinato complementari:
   • Vicinato N8: Ottimizza la sequenza delle operazioni sulla stessa macchina. Estende le mosse tradizionali N5-N7 permettendo alle operazioni critiche al di fuori dei blocchi critici di essere spostate alle estremità del blocco o in posizioni pre/post-blocco.
   • Vicinato k-Insertion: Riassegna le operazioni critiche a diverse macchine. Ciò comporta il passaggio attraverso macchine alternative e l'inserimento dell'operazione in posizioni fattibili, controllando la presenza di dipendenze cicliche.
   • Strategia di Ricerca: Il processo VNS dà priorità al vicinato N8 (minor costo computazionale) e passa al k-insertion (maggior costo, ricerca più ampia) solo se non viene trovato alcun miglioramento, garantendo un equilibrio tra efficienza e profondità di esplorazione.

Contributi Principali
Il documento delinea cinque contributi principali:

1. Framework Ibrido: Stabilisce un framework sinergico di "esplorazione globale prima, sfruttamento locale successivamente", bilanciando efficacementamente accuratezza della soluzione ed efficienza computazionale.
2. Integrazione del Doppio Vicinato: È il primo a integrare i vicinati N8 e k-insertion all'interno di un framework VNS unificato per l'FJSP. Questa combinazione affronta sia la sequenza intra-macchina che la riassegnazione inter-macchina, migliorando significativamente la capacità di ricerca locale.
3. Operatori Genetici Potenziati: L'introduzione del crossover Path-Relinking e delle probabilità di mutazione adattiva rafforza la capacità dell'algoritmo di esplorare lo spazio delle soluzioni e mantenere la stabilità della convergenza.
4. Prestazioni Benchmark: Sul set di benchmark Brandimarte MK, l'HGVNSA raggiunge costantemente le soluzioni ottime note in 6 istanze su 10 (MK01-MK04, MK08-MK09) e ottiene la più bassa deviazione percentuale relativa (RPD) media dello 0,06% rispetto agli algoritmi confrontati (HGWO, HLO-PSO, HA, SLGA, ISLGA).
5. Applicazione nel Mondo Reale: L'algoritmo è stato applicato a uno scenario di lavorazione di alberi di ingranaggi presso l'Azienda A. Rispetto a un tradizionale Algoritmo Genetico, l'HGVNSA ha migliorato l'efficienza della produzione dell'8,81%, dimostrando la sua praticità ingegneristica.

Risultati e Validazione

• Test Benchmark: Esperimenti estesi sulle istanze MK01-MK10 hanno mostrato che l'HGVNSA ha superato gli algoritmi di confronto in termini di qualità della soluzione e stabilità. Gli studi di ablazione hanno confermato che la rimozione della componente VNS, della struttura a doppio vicinato o dei meccanismi adattivi ha portato a un significativo degrado delle prestazioni (ad esempio, rimuovere il VNS ha aumentato il makespan medio su MK02 da 26 a 30,4).
• Caso di Studio: Nel caso di studio dell'Azienda A, che coinvolge 10 lavori e 59 operazioni su 15 macchine, l'algoritmo ha ridotto il makespan da 522 (GA tradizionale) a 476.
• Convergenza: L'analisi della convergenza ha indicato che, mentre altri algoritmi ristagnavano dopo una rapida convergenza iniziale, l'HGVNSA ha continuato a raffinare le soluzioni attraverso i suoi meccanismi di ricerca locale, superando gli ottimi locali nelle iterazioni successive.

Significatività
Il documento sostiene che l'HGVNSA fornisce un framework di soluzione efficiente e robusto per l'FJSP, affrontando efficacemente le sfide del bilanciamento tra ricerca globale e locale e della progettazione di strutture di vicinato efficaci. Lo studio valida che la combinazione della ricerca locale guidata dal percorso critico con l'evoluzione genetica produce risultati superiori sia nei benchmark teorici che negli ambienti industriali pratici. Gli autori suggeriscono che questo lavoro pone le basi per la ricerca futura nello scheduling distribuito e nell'uso del deep reinforcement learning per la selezione intelligente del vicinato, sebbene non affermino che tali estensioni siano state implementate nello studio attuale.