Un Algoritmo Metaeuristico per Scheduling Robusto con Tempi di Trasporto Stocastici

Abstract

Nei moderni sistemi di produzione flessibile (FMS), la logistica interna può rappresentare un collo di bottiglia critico: piccoli ma frequenti ritardi nei trasporti possono trasformare una pianificazione apparentemente ottimale in una che si rivela inefficiente nella realtà. Questa tesi affronta il problema della pianificazione flessibile della produzione con tempi di trasporto in condizioni di incertezza (FJSP-T) sul benchmark AIP-PRIMECA di Valenciennes, concentrandosi sulla variabilità dei trasporti, un aspetto che viene spesso semplificato nei modelli di pianificazione. Per superare le ipotesi stocastiche idealizzate, i tempi di trasporto vengono campionati da distribuzioni empiriche generate tramite simulazioni NetLogo del layout. Una formulazione di programmazione lineare a variabili miste intere (MILP) rilassata viene sviluppata come base di validazione su un numero limitato di istanze, mentre il metodo di soluzione principale è un algoritmo genetico ibrido che decide congiuntamente le operazioni di sequenziamento e l'assegnazione delle macchine attraverso una rappresentazione a doppio cromosoma. Per mantenere la ricerca computazionalmente gestibile, le pianificazioni candidate vengono valutate su un singolo scenario di trasporto campionato durante l'ottimizzazione. La robustezza viene quantificata successivamente tramite una validazione incrociata su tutti gli scenari di trasporto. La robustezza viene valutata analizzando la distribuzione del makespan incrociato tramite la sua media, deviazione standard (DS), coefficiente di variazione (CoV) e intervallo. Tre criteri decisionali sono implementati come regole di selezione: migliore prestazione media, migliore prestazione empirica nel caso peggiore e un criterio per il rischio che bilancia media e variabilità in base al rischio.

In modern flexible manufacturing systems (FMS), internal logistics can be a critical bottleneck: small but frequent transportation delays may turn an ostensibly optimal schedule into one that poorly performs on the shop floor. This thesis addresses the Flexible Job Shop Scheduling Problem with Transportation Times under uncertainty (FJSP-T) on the AIP-PRIMECA Valenciennes benchmark, focusing on transport variability- an aspect that is often simplified in scheduling models. To move beyond idealized stochastic assumptions, transportation times are sampled from empirical distributions generated through NetLogo simulations of the AIP-PRIMECA Valenciennes layout. A relaxed Mixed Integer Linear Programming (MILP) formulation is developed as a validation baseline on limited instances, while the main solution method is a hybrid genetic algorithm that jointly decides the operations sequencing and the machine assignment through a dual-chromosome representation. To keep the search computationally tractable, candidate schedules are evaluated on a single sampled transport scenario during the optimization. Robustness is quantified afterwards through an out-of-sample cross-testing across all the transport scenarios. Robustness is assessed by analyzing the cross-tested makespan distribution via its mean, standard deviation (SD), coefficient of variation (CoV) and range. Three decision criteria are implemented as selection rules: best average performance, best empirical worst-case performance and a risk-adjusted criterion that trades off mean and variability. Across the experimental campaign, transport uncertainty induces a moderate but non-negligible dispersion of the makespan values (CoV roughly spanning 0.03-0.17), confirming that transportation variability can materially affect schedule reliability. In addition, results show a fast convergence of the genetic algorithm and scenario dependent trade-offs between the three selected criteria.