Scheduling in un Flexible Flow Shop: modellazione e Analisi di Strategie di Ottimizzazione

Abstract

Il presente lavoro di tesi affronta il problema dell'ottimizzazione della pianificazione produttiva all'interno di un sistema Flexible Flow Shop (FFS). La scelta di questo argomento nasce dall'esigenza delle moderne realtà industriali di superare i rigidi sistemi in linea, gestendo scenari produttivi complessi caratterizzati da macchine parallele non correlate e vincoli operativi stringenti, come i tempi di rilascio. L'obiettivo primario è la minimizzazione del tempo totale di completamento. Data la natura NP-Hard del problema, è stato sviluppato un framework computazionale in ambiente MATLAB per confrontare tre architetture meta-euristiche: un Algoritmo Genetico (GA) puro, una Tabu Search (TS) innescata dall'euristica costruttiva NEH, e un Algoritmo Memetico ibrido progettato per fondere l'esplorazione globale con l'intensificazione locale. I risultati computazionali dimostrano che la combinazione NEH-TS rappresenta la soluzione ingegneristica d'elezione per istanze di dimensioni contenute, raggiungendo l'ottimo globale con estrema efficienza e superando le convergenze premature del Genetico. L'Analisi di Sensibilità sull'Algoritmo Memetico evidenzia come tale architettura, pur risolvendo istantaneamente l'istanza in esame, risulti computazionalmente sovradimensionata per questa scala, confermandosi tuttavia come lo stato dell'arte per futuri sviluppi su scenari industriali massivi.

This thesis addresses the problem of production scheduling optimization within a Flexible Flow Shop (FFS) system. The choice of this topic stems from the need of modern industrial environments to move beyond rigid in-line systems, managing complex production scenarios characterized by unrelated parallel machines and stringent operational constraints, such as release dates. The primary objective is the minimization of the total completion time (makespan). Given the NP-Hard nature of the problem, a computational framework was developed in the MATLAB environment to compare three metaheuristic architectures: a pure Genetic Algorithm (GA), a Tabu Search (TS) initialized by the NEH constructive heuristic, and a hybrid Memetic Algorithm designed to merge global exploration with local intensification. The computational results demonstrate that the NEH-TS combination represents the engineering solution of choice for small-sized instances, reaching the global optimum with extreme efficiency and overcoming the premature convergences of the Genetic Algorithm. The Sensitivity Analysis on the Memetic Algorithm highlights how this architecture, while solving the instance under examination instantaneously, is computationally oversized for this scale; nevertheless, it confirms its status as the state-of-the-art for future developments in massive industrial scenarios.