Simulation-supported framework for job shop scheduling with genetic algorithm

The JSSP (Job Shop Scheduling Problem) is recognized to be one of the most difficult scheduling problems for NP-completeness feature. In the scientific literature, many studies are focused on this and many different solving techniques were developed: some techniques are focused on the development of optimization algorithms, whilst others are based on simulation models. Since the very beginning, around the 80s, it was stated that a combination of the two could be of big advantage, as it would allow matching advantages from both sides. However, this research stream has not been followed to a great extent and a low number of tools are present in literature that join these two different worlds. The goal of this research is to propose a novel scheduling tool able to match these two really different techniques in one common framework. The base of the framework is composed by a genetic algorithm (GA), which in the last years affirms itself as one of the most performing algorithm able to solve the JSSP. However, the GA lacks in taking into account the real performances of a production system. For this reason, a simulation model is introduced in the evaluation of the fitness function in the GA step, in order to really represent how the manufacturing system works. The need to implement a simulation model involves the decision about which is the best software able to do that in accordance with the actual requirements. The extensive literature survey made on this topic shows a slowing down of the interest on this since the beginning of the century; however, the analysis reveals that it is necessary to update the already existing selection frameworks, because most of the criticalities would be for sure overpassed by software during years: a new evaluation framework is proposed, including both new and classical selection criteria. This novel framework overcomes all of those criticalities found out during the development of a scheduling tool only considering one of the two possibilities, either algorithmic technique or simulation technique. Another purpose of this research is to fill the gap between academic and industrial worlds, through an application of the novel scheduling tool to an industrial case, demonstrating that the tool is able to provide real help during the activity scheduling of the Company. The application to the industrial case shows up another interesting possibility of the tool that is further exploited: the introduction of the stochasticity into the proposed scheduling framework. In so doing the typical variable behavior of the production system could be taken into account and the solution obtained by means of the afore-mentioned methodology could be also statistically demonstrated. The practical confirmation of the framework may allow thinking that this research stream could be further developed to outperform all the other scheduling techniques.

Il JSSP (Job Shop Scheduling Problem) è uno dei più complessi problemi riguardanti la schedulazione delle attività, dovuto principalmente alla caratteristica di essere NP-completo. Nella letteratura scientifica molti studi sono stati svolti con l’obiettivo di risolvere questo problema e sono stati proposti diversi metodi: alcuni sono stati sviluppati nell’ottica di algoritmi di ottimizzazione, altri invece si basano sulla simulazione del sistema produttivo. Sin dalla nascita di questo ramo di ricerca, intorno agli anni 80, è stato confermato che una combinazione delle due filosofie potesse dare ottimi risultati, scaturiti dall’unione dei vantaggi di entrambi i fronti. Nonostante ciò, questa idea non è stata sviluppata molto nel corso degli anni e pochi articoli scientifici trattano della creazione di un modello capace di integrare entrambi gli aspetti, quello del GA e della simulazione. L’obiettivo di questa ricerca è perciò quello di proporre un nuovo strumento di schedulazione capace di unire queste due realtà completamente differenti e fonderle insieme. La base di questo modello è composta dall’algoritmo genetico (GA) che, negli ultimi anni, si è rilevato essere tra i più performanti algoritmi, capace di risolvere la schedulazione nei sistemi produttivi di tipo job shop. Ciò nonostante, il GA non è in grado di poter rappresentare come lavori realmente il sistema produttivo. Per questa ragione è stato introdotto un modello di simulazione, il cui scopo è quello di dare al GA le possibilità per poter conoscere come il sistema produttivo si comporti con determinati input. La necessità di sviluppare tale modello implica la scelta del miglior software adatto allo scopo, che soddisfi i requisiti del problema attuale. Dopo una attenta ricerca nella letteratura scientifica, si è notato un rallentamento nella produzione di articoli scientifici su questo argomento, probabilmente dovuto ad un minor interesse visibile dagli inizi del secolo. Nonostante questo l’analisi ha rilevato che un aggiornamento delle metodologie di valutazione proposte in passato è necessario: molte criticità legate all’implementazione sono state sicuramente sorpassate con lo sviluppo e l’introduzione di nuovi software: per questo motivo una nuova metodologia di valutazione per la selezione del software è proposta, che includa sia nuovi che già presenti criteri. Questo nuovo strumento di schedulazione risolve tutte quelle criticità legate allo sviluppo di metodi di soluzione fedeli ad una sola scuola di pensiero, o quella algoritmica o quella di simulazione. Un ulteriore scopo di questo lavoro di ricerca è colmare la lacuna tra due ambiti distanti, quello accademico e quello industriale, grazie ad una applicazione pratica del nuovo strumento ad un caso reale: questo è in grado di fornire un fondamentale aiuto durante la schedulazione delle attività della Compagnia. L’applicazione del modello ad un caso industriale ha mostrato una grande possibilità di miglioramento: l’introduzione di stocasticità nel sistema produttivo. In questo modo il comportamento aleatorio dei sistemi di produzione può essere tenuto in considerazione e la soluzione trovata potrà avere anche significatività da un punto di vista statistico. La conferma, derivante dall’applicazione pratica, permetterebbe di pensare che il filone di ricerca in questione possa risultare vincente rispetto ad altri metodi di schedulazione.