Enhanced Genetic Algorithm to Solve the Energy-efficient Flexible Job Shop Scheduling Problem

Energy-efficient scheduling represents a challenging real-world optimisation problem with profound implications for the manufacturing sector, offering the opportunity of reducing energy consumption through minimal initial investment. This master thesis addresses the Multi-Objective Energy-efficient Flexible Job Shop Scheduling Problem with Transportation Times (MO-EFJSP-TT). The scheduling optimisation problem integrates both time and energy objectives in a flexible job shop production environment where also the transportation times of Automated Guided Vehicles (AGVs) are considered. The problem is initially modelled using a Mixed Integer Linear Programming (MILP) approach. Given the complexity of this issue, Multi-Objective Genetic Algorithms (MOGA) have been developed to address medium to large-sized problems efficiently within a feasible time-frame. A novel MOGA algorithm, called EVNS-NSGA-II, is developed, merging conventional genetic algorithms with local search techniques. In addition, the initialisation process is improved with an innovative algorithm based on dispatching rules, named Mixed Dynamic Dispatching Rules (MDR), which is capable of introducing in the initial population high quality individuals both for the energy and makespan objective. The methodology has been validated using real data from a Chinese manufacturing company and other 15 generated instances. The findings from the computational experiments demonstrate that the proposed methodology significantly outperforms the traditional NSGA-II, achieving in the same computational time an average improvement of 14% and 4% in the best makespan and energy objectives, respectively. Moreover, it yields a 450% increase in the number of optimal solutions on the Pareto front.

La schedulazione energeticamente intelligente rappresenta una sfida di ottimizzazione con profonde implicazioni per il settore manifatturiero, in quanto offre la possibilità di ridurre il consumo energetico attraverso un investimento iniziale minimo. Questa tesi di laurea affronta un problema multi-obiettivo di schedulazione di un ambiente di produzione per reparti specializzati flessibile, energeticamente efficiente. Inoltre, vengono considerati i tempi di trasporto dei Veicoli a Guida Automatica (AGV) adibiti al trasporto di materiale tra le macchine. Inizialmente, il problema è formulato con un modello di Programmazione Lineare Intera Mista (MILP). Data la complessità del problema, sono stati sviluppati Algoritmi Genetici Multi-Obiettivo (MOGA) per risolvere problemi di dimensioni medio grandi in un tempo minore. È stato sviluppato un nuovo algoritmo MOGA, chiamato EVNS-NSGA-II, che fonde algoritmi genetici convenzionali con tecniche di ricerca locale. Inoltre, il processo di inizializzazione è stato migliorato con un algoritmo innovativo basato su regole di dispacciamento, denominato Regole di Dispacciamento Dinamico Misto (MDR), che è capace di introdurre nella popolazione iniziale individui di alta qualità sia per l'efficienza energetica che per quella temporale. La metodologia è stata validata utilizzando dati reali di un'azienda manifatturiera cinese e altri 15 esempi con caratteristiche differenti. I risultati dei test dimostrano che la metodologia proposta supera l'algoritmo NSGA-II, ottenendo nel medesimo tempo un miglioramento del 14% e del 4% rispettivamente nel tempo di completamento ed energia consumata. Inoltre, ottiene un aumento del 450% nel numero di soluzioni ottimali sul fronte di Pareto.