A restarted iterated Pareto greedy algorithm for the multi-objective hybrid flow shop scheduling problem

The scheduling of flow shops with multiple parallel machines per stage, which is usually referred to as the hybrid flow shop (HFS), is a complex combinatorial optimization problem encountered in many real-world applications. The problem is to determine the allocation of jobs to the parallel machines as well as the sequence of the jobs assigned to each machine, so as to create a Gantt chart to guide the production activities. The basic HFS scheduling problem has been thoroughly studied in recent decades, both from single objective as well as from multi-objective perspectives, but to the best of our knowledge, little has been done to the multi-objective scheduling problem considering the reduction of total machine setup time as one of the objectives. Given that the machine setups act as non-value-added activities which should be avoided or mitigated from the manufacturing practices, it is important to make a proper schedule which results in short total setup time together with other performance indicators, such as productivity and on-time product delivery. For this reason, this thesis focuses on the HFS scheduling problem with the total tardiness and total setup time objectives. In this work, a simple, yet powerful algorithm for the sequence dependent setup time hybrid flow shop problem is proposed. The presented method, known as Restarted Iterated Pareto Greedy or RIPG, is compared to the NGSA-II, which is a well-known algorithm for multi-objective optimization in literature. Computational and statistical analyses demonstrate that the proposed RIPG method outperforms the NGSA-II in the test instances. We conclude that the proposed method is a candidate to be the state-of-art method for this important and practical scheduling problem.

Lo scheduling di un flowshop con più macchine parallele per stadio, comunemente chiamato flowshop ibrido (HFS), è un complesso problema di ottimizzazione presente in numerose applicazioni reali. Il problema consiste nel determinare l’allocazione dei lavori sulle macchine parallele così come la sequenza dei lavori assegnati ad ogni macchina, oltre che a creare un diagramma di Gantt come guida delle attività di produzione. ll problema dello scheduling di HFS è stato studiato a fondo negli ultimi decenni, sia per quanto riguarda il caso di singolo obiettivo che per quelli multi-obiettivo, ma per quanto ne sappiamo, poco è stato fatto riguardo il problema di scheduling multi-obiettivo considerando la riduzione del totale tempo di setup delle macchine come uno degli obiettivi. Dato che il setup della macchina rappresenta una attività senza valore aggiunto, le quali dovrebbero essere evitate o moderate nelle pratiche di produzione, è importante fare uno scheduling adeguato che si traduca in un breve tempo totale di setup oltre ad ad altri indicatori di prestazione, come produttività e consegna dei prodotti in tempo reale. Per questo motivo, questa Tesi si concentra sul problema dello scheduling di HFS con gli obiettivi di tardiness totale e tempo totale di setup. In questo lavoro, viene proposto un algoritmo semplice ma potente per risolvere il problema dello scheduling di un HFS con setup dipendente dalla sequenza. Il metodo presentato, noto come “Resteto Iterated Pareto Greedy” o RIPG, viene confrontato con NGSA-II, noto algoritmo per l'ottimizzazione multi-obiettivo presente in letteratura. Le analisi computazionali e statistiche dimostrano che il metodo RIPG proposto supera le NGSA-II nelle istanze dei test effettuati. Concludiamo quindi che il metodo proposto è un candidato per essere un metodo all'avanguardia per questo importante e pratico problema di scheduling.