Genetic algorithm for job-shop scheduling : a case study in Tenaris Dalmine

In recent decades, the solution of the Job Shop Scheduling Problem (JSPP) was an argument of great interest for both academic and industrial world, due to its complexity typical of the so-called NP-complete problem. In this work, this problem is assessed by examining the industrial case of a Job Shop manufacturing plant. The aim is to bring the academic and industrial world closer about this issue by implementing a tool for industrial activity scheduling. This tool combines a meta-heuristic calculation method and a simulation model that allows to search the solution space looking for the best solution by minimizing the makespan. The introduction is dedicated to an overview of the scheduling problem and the available methods to address it with a particular attention to the genetic algorithm that is the chosen method. Subsequently, the industrial case is presented with an in-depth analysis of the production mix and technological processes. Then it will be possible to build the simulation model that will be integrated into the genetic algorithm, and a first validation of the simulation model is carried out to evaluate the correct implementation of the industrial logics. Finally, to ensure that the instrument is customized to the considered industrial environment, experiments are conducted on the GA parameters of interest, in order to select the most suitable values. A final validation is performed to test the goodness of the scheduling tool. In the end, this works show that the interaction between the academical and the industrial world is profitable and this scheduling tool reveals to be an effective support for the industrial environment in which applies. For this reason, the Company foresees to implement it in its informatic system in order to make it accessible to other company systems and to develop other version to apply other part of the plant.

Una delle tematiche di più grande interesse sia accademico che industriale degli ultimi decenni è la soluzione dello Job Shop Scheduling Problem (JSPP), la cui complessità deriva dal fatto che è un problema NP-completo. Il lavoro sviluppato in questa tesi vuole studiare questo problema prendendo in esame il caso industriale di un impianto manifatturiero Job Shop. L’obiettivo è quello di avvicinare il mondo accademico e industriale costruendo uno strumento per la schedulazione dei processi industriali. Questo strumento utilizza un metodo di calcolo meta-euristico (algoritmo genetico) che, combinato con uno modello di simulazione, permette di ricercare e valutare la soluzione ottima minimizzando il tempo di attraversamento. Dopo aver introdotto il problema della schedulazione, il lavoro si focalizza sulla descrizione dell’algoritmo genetico. Successivamente viene presentato il caso industriale, illustrando il mix produttivo e i processi tecnologici che si svolgono al suo interno. Quindi viene definito il modello di simulazione, che diventa parte integrante dell’algoritmo genetico. Il modello viene opportunamente validato, con il fine di verificare che le logiche dell’impianto siano correttamente implementate. Infine, un’analisi di sensitività viene effettuata per definire i parametri dell’algoritmo. In conclusione, questo lavoro dimostra che l’interazione tra ricerca e industria su questo argomento è profittevole e questo strumento di schedulazione si rivela un aiuto efficace per l’ambiente industriale in cui si applica. L’azienda prevede infatti di implementarlo nei propri sistemi informativi affinchè possa interagire con il proprio sistema IT e di svilupparne altre verisoni che possano applicarsi ad altre aree della fabbrica.