Superare il JSP con un algoritmo genetico nello scheduling

Lo scheduling dei processi produttivi è uno dei compiti più critici della produzione ed è stato ampiamente studiato dalla comunità scientifica. Il problema va oltre il puro interesse accademico. Una programmazione efficace delle operazioni processate dallo shop floor riduce l’inventario del processo di lavoro e aumenta la portata con un impatto positivo sull’automazione industriale. Il problema dello scheduling riguarda il posizionamento delle risorse di produzione disponibili rispetto ai compiti da portare a termine, e la determinazione della sequenza delle operazioni che può ottimizzare le metriche di business.

In letteratura, il JSP (job shop scheduling problem) è la formulazione standard del problema di programmazione della produzione. Nel JSP, un’operazione può essere eseguita da una sola macchina e una macchina può eseguire una sola operazione alla volta. Tuttavia, per far fronte a casi reali più complessi, il JSP è stato esteso consentendo un’operazione eseguibile su più di una macchina (Flexible JSP), su tutte le macchine (Total Flexible JSP), o su un sottoinsieme delle macchine (Partial Flexible JSP) (Xie et al., 2019).

Una specifica peculiare e orientata alla pratica del FJSP è quella descritta da Behnke e Geiger. Nel loro lavoro, illustrano un contesto in cui macchine simili sono raggruppate in centri di lavoro. In questo contesto, se un’operazione è assegnabile ad una macchina è anche assegnabile a qualsiasi altra macchina appartenente allo stesso centro di lavoro. Un’altra interessante proprietà del contesto è che la sequenza delle operazioni è fissa e la prima e l’ultima operazione di ogni lavoro devono essere processate da macchine del primo e dell’ultimo centro di lavoro (Behnke e Geiger, 2012).

Quest’ultimo scenario si avvicina a quello incontrato durante il nostro progetto di ricerca, condotto con un’azienda italiana. Qui i centri di lavoro aggregano macchine che eseguono una certa classe di operazioni. Inoltre, mentre la sequenza delle operazioni da un centro di lavoro al successivo è fissa, le operazioni dello stesso centro di lavoro possono essere eseguite in qualsiasi ordine possibile. L’azienda aveva mostrato difficoltà nel trovare una strategia di schedulazione ottimizzata che permettesse di rispettare tali vincoli, non comunemente studiati nel campo FJSP, e distribuire meglio il carico di lavoro. Per rispondere a questa necessità, in questo articolo introduciamo una variante estesa del FJSP con Working Center proposta da Behnke e Geiger e illustriamo un algoritmo genetico adattato con una rappresentazione cromosomica a due stadi, ricerca locale e tecnica del disastro sociale.

Il nostro contributo consiste in:

• la formalizzazione di un problema industriale come variazione del FJSP;
• l’implementazione di un sistema adattato di codifica/decodifica che rende un algoritmo genetico (GA) capace di gestire soluzioni conformi ai vincoli presentati senza eseguire correzioni;
• lo sviluppo di una strategia di programmazione che migliora le prestazioni umane in un contesto industriale.

Un algoritmo genetico è una metaeuristica basata sulla popolazione, ossia un metodo utilizzato per la soluzione di una classe molto ampia di problemi computazionali combinando diverse procedure con l’obiettivo di ottenerne una più robusta ed efficiente, ed è un approccio molto popolare per risolvere il FJSP.
L’algoritmo integra diverse strategie per generare la popolazione iniziale, selezionare gli individui per la riproduzione e riprodurre nuove soluzioni (Xie et al., 2019). Gli algoritmi genetici, classe di algoritmi euristici utilizzati per tentare di risolvere problemi di ottimizzazione, codificano i problemi per i quali mirano a ottimizzare una funzione di costo in cromosomi: gli individui della popolazione sono vettori i cui elementi sono chiamati geni.

Quando si ha a che fare con il FJSP e le sue relative sottoclassi, è pratica comune rappresentare il problema utilizzando un cromosoma a due lati. Un cromosoma può infatti essere diviso in due parti che si comportano diversamente e codificano informazioni diverse: una codifica l’assegnazione della macchina, mentre l’altra codifica la sequenza delle operazioni (Gao et al., 2008) (Yang et al., 2009) (Zhang et al., 2011) (Rahmati e Zandieh, 2012) (Defersha e Rooyani, 2020). In questo lavoro, estendiamo la pipeline tipica dell’algoritmo genetico con la ricerca locale e la tecnica del disastro sociale.

La ricerca locale può aiutare a evitare i minimi locali esplorando lo spazio locale intorno a una particolare soluzione, possibilmente migliorandola. Può essere usata in diverse fasi della ricerca globale (Yun et al., 2013) o direttamente alla fine del processo (Nouri et al., 2018). La seconda tecnica che usiamo è chiamata tecnica del disastro sociale. L’idea generale è quella di diagnosticare la situazione di perdita di diversità genetica della popolazione, e in tal caso applicare un operatore catastrofico. Questi operatori hanno lo scopo di riportare la popolazione a un grado accettabile di diversità genetica, sostituendo un certo numero di individui selezionati con altri generati a caso (Rocha e Neves, 1999). Entrambe le tecniche sono progettate per aiutare il modello a fornire soluzioni migliori evitando la convergenza prematura verso gli ottimali locali, evitando lo spreco di tempo computazionale in aree infruttuose dello spazio di ricerca.

Risultati sperimentali e discussione

Abbiamo valutato l’algoritmo proposto contro l’euristica di schedulazione attualmente in uso presso l’azienda con cui abbiamo collaborato; abbiamo anche studiato diverse combinazioni di operatori genetici dell’algoritmo proposto.

Ci è stata fornita un’istanza di test composta da un totale di 309 operazioni divise in 16 lavori con una media di 19,3 operazioni ciascuno. L’istanza è anonimizzata in modo che i lavori, le operazioni e i tipi di operazioni siano identificati da id numerici progressivi. Le operazioni sono distribuite tra i tipi di operazioni come segue:

• tipo 1: 55 operazioni
• tipo 2: 29 operazioni
• tipo 3: 27 operazioni

Il numero di macchine disponibili per ogni operazione è variabile e va da 1 a 5. Le caratteristiche delle macchine non sono discusse in questo lavoro e le informazioni sulle macchine alternative disponibili per ogni operazione sono fornite nell’istanza di test. Su questa istanza, abbiamo eseguito il nostro algoritmo 10 volte su 500 generazioni. Abbiamo variato il nostro algoritmo in quattro diverse combinazioni per giustificare la scelta fatta in termini di operatori genetici e per utilizzare una caratteristica aggiuntiva come la ricerca locale:

1. L’approccio proposto;
2. L’approccio proposto senza la ricerca locale;
3. L’algoritmo proposto con un diverso set di operatori genetici, ovvero:

• K-point Crossover invece di Uniform Crossover (Umbarkar e Sheth, 2015);
• OX Crossover invece di MOC Crossover (Magalhaes-Mendes, 2013);
• Twors Mutation invece di Reverse Sequence Mutation (Abdoun et al., 2012);

L’impostazione numero 3 senza la ricerca locale. Gli iperparametri sono tenuti uguali per ogni approccio e sono scelti sperimentalmente come segue:

• Fattore Pop: 1;
• Probabilità di crossover: 0.8;
• Tasso MOC = 0.6;
• Tasso di mutazione = 1.;
• Tasso di flip = 0,2;

Per assomigliare alla schedulazione che verrebbe inviata alla produzione nell’ambiente industriale originale, abbiamo usato come baseline una soluzione ottenuta con l’euristica di schedulazione usata dal responsabile della produzione, che non è diversa dall’euristica min-min come conosciuta in letteratura (Durasevi´c e Jakobovi´c, 2018). L’euristica può produrre diverse soluzioni, quindi l’abbiamo eseguita 1000 volte per rappresentare meglio la variabilità del comportamento umano. Abbiamo poi ordinato i risultati ottenuti per Cmax, selezionato il primo e il quinto migliore per mostrare una gamma di possibili risultati ottenuti da un esperto umano, e li abbiamo usati entrambi come linea di base.

La figura 2 mostra i risultati ottenuti in un grafico a linee. L’area intorno ad ogni linea da un’idea della variabilità dei risultati ottenuti, in quanto è delimitata dal valore minimo e massimo di Cmax visto ad una certa generazione durante le 10 corse. Sia l’approccio 1 che l’approccio 3 hanno prestazioni migliori delle rispettive versioni senza l’uso della ricerca locale, cioè l’approccio 2 e 4, mostrando quanto possa essere importante l’uso efficace di un algoritmo di ricerca locale combinato con l’algoritmo di ricerca globale. L’approccio proposto si comporta meglio di quello alternativo sia nel breve che nel lungo termine: è più veloce in termini di generazioni a raggiungere il livello di fitness ottenuto dall’euristica del direttore di produzione; è migliore al termine delle 100 generazioni, essendo in grado di esplorare in modo efficiente porzioni locali del processo di ricerca e migliorare rapidamente; è migliore dopo 500 generazioni, essendo ancora in grado di migliorare, riuscendo ad uscire dai minimi locali con l’uso della tecnica del disastro sociale.

Rispetto alla linea di base, l’algoritmo è in grado di ottenere un miglioramento dell’8,68% alla soglia delle 100 generazioni e del 10% dopo 500 generazioni. Rispetto alla quarta linea di base, l’algoritmo è in grado di ottenere un miglioramento del 6,73% alla soglia delle 100 generazioni e dell’8% dopo 500 generazioni.

In conclusione, il nostro approccio migliora la programmazione di base risparmiando fino a 412 minuti di tempo di lavoro rispetto alla prima linea di base.

Conclusioni

In questo lavoro, abbiamo presentato una nuova versione del Flexible Job Shop Scheduling Problem con Working Center, in cui le operazioni hanno stretti vincoli di sequenza. Al fine di gestire tali vincoli in un ambiente industriale, abbiamo sviluppato un algoritmo genetico con una rappresentazione cromosomica a due stadi con il suo sistema di codifica/decodifica, operatori genetici adattati, ricerca locale e tecnica del disastro sociale. Per valutare l’algoritmo proposto, abbiamo testato il nostro algoritmo su un’istanza di prova fornita dall’azienda che ha ispirato tale formulazione del problema.

Abbiamo confrontato i risultati con l’euristica adottata dal responsabile della produzione e con diverse impostazioni dell’approccio proposto. Abbiamo mostrato come in entrambe le impostazioni analizzate l’uso della ricerca locale migliori le prestazioni e permetta una rapida convergenza verso buone soluzioni. Inoltre, siamo stati in grado di mostrare miglioramenti significativi contro entrambe le linee di base prodotte da un responsabile di produzione con un margine dall’8% al 10%.

Un ulteriore sviluppo di questo lavoro sarà quello di gestire dinamicamente l’arrivo di nuove operazioni durante il processo di pianificazione, considerando anche il tempo di setup di attacco e stacco, tenendo conto delle prestazioni computazionali, soprattutto in confronto con altri lavori di ricerca e con prodotti commerciali.