A simulation model for solving the flow shop scheduling problem under uncertainty

This thesis describes a simulation-optimization algorithm for the hybrid flow shop scheduling problem (HFSSP) with stochastic processing times. Since most of the scheduling methods consider a deterministic environment in which all the data are certain, this case study tries to reduce the gap between academic researches and the real industrial world where several uncertain and unexpected events could occur. This investigation was preceded by an extensive literature review on the implementation of the genetic algorithm (GA) in the manufacturing systems and on the most adopted methods to deal with various forms of uncertainty present at the shop floor. The analysis was conducted considering the last 8 years of works in order to highlight the last tendencies and research directions. The HFSSP known as an NP-hard problem and the proposal of an efficient framework tool was taken into consideration in this study. The introduced framework is based on a genetic algorithm, which represents one of the most popular meta-heuristic solving technique as well as one of the most performing methods to solve NP-hard problems. GA is integrated with a simulation model which can consider the real constraints and performances of the production system. Taking as a reference a precedence scientific research on HFSSP, the scheduling framework was tuned in order to replicate some results and a step forward has been made in order to handle the stochastic behavior of the processing times, providing a better solution from the industrial point of view. As proposed by the latest scientific studies on manufacturing systems, a further analysis has been conducted considering lognormal distribution for the processing times which has not been extensively examined even if its features seem to be more suitable than other probability distributions which were fully addressed during the past years. The computational results show that the proposed scheduling framework can generate accurate solutions to handle the HFSSP with stochastic processing times.

La presente tesi ha lo scopo di risolvere il problema della schedulazione di un hybrid flow shop (HFSSP), avente tempi di processamento stocastici, attraverso l’uso di un algoritmo di ottimizzazione e della simulazione. Poiché la maggior parte dei problemi di schedulazione considerano un ambiente deterministico in cui tutti i dati sono certi, questo studio cerca di ridurre il divario fra le ricerche accademiche e il mondo industriale, con tutte le incertezze ed eventi inaspettati che ne derivano. La ricerca è stata preceduta da un esame approfondito della letteratura sull’implementazione dell’algoritmo genetico (GA) nei sistemi di produzione e sui metodi più adottati per affrontare varie forme di incertezza presenti nell’area di produzione. L’analisi è stata condotta considerando gli ultimi 8 anni di studi allo scopo di evidenziare le ultime tendenze e direzioni di ricerca. In questo studio viene preso in considerazione un valido strumento di schedulazione per risolvere l’HFSSP, conosciuto come un problema NP-difficile. Lo strumento proposto si basa sull’algoritmo genetico, che rappresenta una delle tecniche di risoluzione meta-euristiche più popolari, nonché uno dei metodi più performanti per risolvere i problemi NP-difficili. Il GA è stato integrato con un modello di simulazione, che può considerare i vincoli e le prestazioni reali di un sistema di produzione. Prendendo come riferimento una precedente ricerca scientifica, la procedura di schedulazione è stata regolata allo scopo di replicare alcuni risultati proposti in tale ricerca, e un passo avanti è stato fatto per gestire il comportamento stocastico dei tempi di processamento, fornendo una soluzione migliore dal punto di vista industriale. In linea con gli ultimi studi scientifici sui sistemi di produzione, un’ulteriore analisi è stata effettuata considerando la distribuzione lognormale per i tempi di processamento. Tale distribuzione non è stata studiata approfonditamente, nonostante le sue caratteristiche sembrino essere più adatte di quelle relative ad altre distribuzioni di probabilità, esaminate minuziosamente negli anni passati. I risultati computazionali mostrano che la procedura di schedulazione proposta può generare soluzioni accurate per gestire l’HFSSP con tempi di processamento stocastici.