Joint Planning of Assembly Sequence Planning and Assembly Line Balancing Based on Improved Artificial Fish Swarm Algorithm

Sintesi Tecnica: Pianificazione Congiunta della Sequenza di Assemblaggio e del Bilanciamento della Linea di Assemblaggio basata su un Algoritmo di Sciame di Pesci Artificiali Migliorato

Definizione del Problema
Il documento affronta la complessa sfida di ottimizzare simultaneamente la Pianificazione della Sequenza di Assemblaggio (ASP) e il Bilanciamento della Linea di Assemblaggio (ALB). Questi due problemi sono intrinsecamente accoppiati: l'ASP determina l'ordine ottimale di assemblaggio dei componenti per minimizzare i costi, mentre l'ALB assegna tali compiti alle stazioni di lavoro per ridurre al minimo i tempi morti e bilanciare la linea. Entrambi sono classificati come problemi NP-hard con complessità polinomiale. Gli autori osservano che l'ottimizzazione separata di questi problemi porta spesso a prestazioni complessive del sistema subottimali. Inoltre, i metodi esistenti per l'ASP soffrono spesso di "esplosione combinatoria" quando utilizzano la ricerca su grafi, e i metodi tradizionali di generazione di matrici possono essere lenti ed inefficienti per prodotti complessi. Inoltre, molti studi sull'ALB non tengono conto dei cambiamenti dinamici negli strumenti di assemblaggio e nelle direzioni inerenti all'ASP, portando a risultati di bilanciamento che potrebbero risultare impraticabili nei processi di assemblaggio reali.

Metodologia
L'approccio proposto integra l'ASP e l'ALB in un quadro di ottimizzazione multi-obiettivo unificato utilizzando un Algoritmo di Sciame di Pesci Artificiali Ibrido (HAFSA). La metodologia è strutturata in tre fasi principali:

1. Modellazione ASP tramite BOM e Matrice dei Vincoli:

   • Invece di fare affidamento esclusivamente sui grafi AND/OR che causano l'esplosione combinatoria, gli autori costruiscono una matrice di vincoli di assemblaggio modulare basata sul diagramma gerarchico della Distinta Base (BOM).
   • La matrice dei vincoli di assemblaggio ($E(G)$) è definita utilizzando un grafo diretto in cui gli elementi rappresentano le parti e i valori indicano priorità e relazioni di connessione (ad esempio, $1$ per connessione diretta precedente, $-1$ per successiva, $9$ per non diretta precedente, ecc.).
   • Partizionamento dei Sotto-assemblaggi: Un algoritmo analizza la gerarchia BOM per determinare l'indipendenza dei sotto-assemblaggi. Verifica iterativamente i valori delle colonne nella matrice dei vincoli; se un gruppo di parti mostra relazioni coerenti non positive o non negative con le parti esterne, esse vengono identificate come sotto-assemblaggi indipendenti. In caso contrario, l'algoritmo rimuove specifiche righe per creare moduli indipendenti fattibili.
   • Pianificazione Interna: All'interno di ogni sotto-assemblaggio identificato, viene utilizzato un algoritmo specifico di scambio e consolidamento per generare sequenze di assemblaggio interne fattibili basate sui valori della matrice dei vincoli.

2. Modello di Ottimizzazione Multi-obiettivo:
   Il modello integrato cerca di minimizzare simultaneamente tre funzioni obiettivo:

   • Bilanciamento dei Tempi della Stazione di Lavoro: Minimizzazione della varianza tra il ritmo di produzione ($T_c$) e i tempi delle singole stazioni di lavoro ($T_m$).
   • Costi di Commutazione: Minimizzazione del numero totale di cambi di utensili di assemblaggio e di cambi di direzione di assemblaggio tra compiti consecutivi.
   • Tempo Massimo della Stazione di Lavoro: Minimizzazione del tempo di ciclo (il tempo massimo tra tutte le stazioni di lavoro).

3. Algoritmo di Sciame di Pesci Artificiali Ibrido (HAFSA):
   Per risolvere questo problema multi-obiettivo, gli autori propongono un HAFSA che combina l'Algoritmo di Sciame di Pesci Artificiali (AFSA) con l'Ottimizzazione a Sciame di Particelle (PSO) e i concetti di ottimalità di Pareto.

   • Codifica/Decodifica: I compiti di assemblaggio sono codificati in base ai pesi di priorità all'interno dei sotto-assemblaggi. La decodifica assegna i compiti alle stazioni di lavoro in sequenza, aprendo nuove stazioni solo quando viene superato il vincolo del tempo di ciclo.
   • Insieme di Soluzioni Pareto: Un repository esterno memorizza le soluzioni non dominate. Viene utilizzato un meccanismo di distanza di affollamento (crowding distance) per mantenere la diversità e gestire la dimensione del repository.
   • Miglioramenti dell'Algoritmo:
     • Logica Comportamentale: L'algoritmo segue un ordine di ricerca seriale: inseguimento della coda (tail-chasing), foraggiamento (foraging), raggruppamento (clustering) e comportamento casuale.
     • Integrazione PSO: Per evitare che l'algoritmo cada in ottimi locali (un limite noto del normale AFSA), vengono introdotte operazioni PSO. Ciò include l'uso di un criterio di Metropolis (concetto di annealing simulato) per accettare soluzioni peggiorative con una certa probabilità, permettendo alla ricerca di uscire dalle trappole locali.
     • Inerzia Dinamica: Il "campo visivo" (intervallo di ricerca) dei pesci artificiali è regolato dinamicamente utilizzando un peso d'inerzia ($\omega$) ispirato al PSO, partendo da un campo ampio per l'esplorazione globale e restringendolo per la convergenza locale.

Contributi Chiave

• Quadro Integrato: Il documento propone un metodo per pianificare congiuntamente ASP e ALB anziché trattarli sequenzialmente, riconoscendo la loro interdipendenza.
• Identificazione dei Sotto-assemblaggi basata su Matrice: Un approccio innovativo che utilizza la gerarchia BOM e la matrice dei vincoli di assemblaggio per identificare automaticamente i sotto-assemblaggi indipendenti, riducendo lo spazio di ricerca ed evitando l'esplosione combinatoria.
• Algoritmo HAFSA: Lo sviluppo di un Algoritmo di Sciame di Pesci Artificiali Ibrido basato su Pareto che migliora il normale AFSA incorporando operazioni PSO e principi di annealing simulato per potenziare le capacità di ricerca globale ed evitare ottimi locali.
• Gestione Multi-obiettivo: L'inclusione esplicita dei cambi di utensili e dei cambi di direzione come obiettivi di ottimizzazione insieme al tradizionale bilanciamento dei tempi.

Risultati
Il metodo proposto è stato validato tramite un caso di studio di un prodotto specifico con 21 compiti di assemblaggio. L'HAFSA (denominato AFSA&PSO) è stato confrontato con un algoritmo di Ottimizzazione a Sciame di Particelle (PSO) standard e un algoritmo di Sciame di Pesci Artificiali (AFSA) standard.

• Bilanciamento delle Stazioni di Lavoro: Tutti e tre gli algoritmi hanno ottenuto lo stesso tempo massimo di operazione della stazione di 31 minuti. Tuttavia, il valore di bilanciamento inter-stazione per l'HAFSA è stato di 0,69, superiore al risultato del PSO (0,75) ed uguale all'AFSA standard (0,69).
• Efficienza di Commutazione: L'HAFSA ha raggiunto un totale di 22 cambi (utensile + direzione). Questo era uguale al risultato del PSO (22), ma significativamente migliore dell'AFSA standard, che ha prodotto 24 cambi.
• Conclusione dai Dati: L'HAFSA ha dimostrato la capacità di trovare una soluzione Pareto-ottimale che bilancia efficacemente i tempi delle stazioni minimizzando al contempo il numero totale di commutazioni operative, superando l'AFSA standard nella riduzione delle commutazioni e eguagliando o superando il PSO nelle metriche di bilanciamento.

Significatività e Rivendicazioni
Il documento afferma che la sua importanza primaria risiede nel miglioramento dell'efficienza e della fattibilità della pianificazione congiunta di ASP e ALB. Utilizzando la gerarchia BOM per pre-elaborare i sotto-assemblaggi, il metodo rende lo spazio di ricerca più mirato, migliorando così l'efficienza della soluzione ed evitando la generazione di un gran numero di soluzioni non fattibili.

Gli autori sostengono che il proposto HAFSA sia più efficace degli algoritmi tradizionali AFSA e PSO per questo specifico problema multi-obiettivo. L'integrazione delle operazioni PSO nel comportamento dello sciame di pesci consente all'algoritmo di uscire meglio dagli ottimi locali, produendo soluzioni Pareto di qualità superiore. Lo studio conclude che questo approccio integrato fornisce un metodo di pianificazione più ragionevole ed efficiente per le linee di assemblaggio di prodotti complessi, specialmente dove i cambi di utensili e di direzione sono fattori di costo critici.