Risolvere varianti di problemi di Shop Scheduling con metodologie di Deep Learning

In the landscape of modern industries, scheduling problems are pivotal as they influence an organization's competitiveness, operational costs, and capacity to meet demands. This work specifically delves into variants of shop scheduling problems involving the planning of production or logistics processes with precedence among tasks/jobs. Our primary attention is directed toward two distinct types of shop scheduling problems: the classical Job Shop Scheduling and a generalization of the Flexible Flow Shop Scheduling. The former, extensively studied in the literature, stands as a perfect candidate for developing innovative resolution methodologies. Conversely, the latter stems from a real-life problem that is first introduced in this work. Our research contributes to the existing literature in two different directions. Motivated by the recent success of learning methodologies in other fields, this work carefully reviews deep learning applications to shop scheduling problems. When strategically employed, these data-driven methodologies can complement and enhance existing methods, offering additional flexibility and customization for end-users. Although several recent works addressing Flow and Job Shop variants exist, mostly relying on Reinforcement Learning, they still lag behind classic methodologies. Therefore, in one research direction, we investigate and advance the applicability of supervised learning paradigms for the resolution of a renowned problem, namely the Job Shop Scheduling. Specifically, we employ supervised strategies to enhance a Tabu Search meta-heuristic by guiding its exploration with a sequential deep learning model. In addition, we devise an end-to-end learning system that relies on a self-supervised training strategy, neither requiring expensive optimal solutions as supervision nor resorting to Reinforcement Learning. Notably, this latter method outperforms all the recent deep learning approaches for the Job Shop. In a different direction, we study a novel and intricate scheduling problem arising from a manufacturing industry, where parallel machines and workforce constraints intertwine with precedence ones. Although these constraints are separately studied in variants of scheduling problems, their confluence creates a distinctive landscape that challenges and modifies assumptions upon which traditional methodologies rely. Thus, we formalize the problem, develop lower bounds to evaluate algorithms, adapt baseline heuristics from related scheduling variants, and propose a new heuristic method to efficiently tackle this problem. We believe that our work makes a step forward in enriching the repertoire of problem-solving methodologies and contributes in adapting techniques to the complexity of real-world industrial challenges.

Nel contesto industriale moderno, i problemi di pianificazione rivestono un ruolo fondamentale poiché influenzano la competitività di un'organizzazione, i suoi costi operativi e la capacità di soddisfare le richieste. Questo lavoro affronta varianti di problemi che interessano la pianificazione di processi produttivi o logistici con precedenze tra compiti/lavori. Nello specifico, vengono trattate due distinte tipologie di problemi di pianificazione: il classico problema conosciuto come Job Shop Scheduling e una generalizzazione del problema nominato Flexible Flow Shop Scheduling. Il primo, ampiamente studiato in letteratura, si configura come un candidato ideale per lo sviluppo di metodologie innovative di risoluzione. Al contrario, il secondo nasce da un problema reale affrontato per la prima volta in questo lavoro. Il contributo di questa ricerca si divide in due diverse parti. Motivati dal recente successo di metodologie basate su Machine Learning, si esaminano applicazioni basate su tali metodologie per problemi di pianificazione detti Shop Scheduling Problem. Queste metodologie, quando utilizzate strategicamente, possono integrare e migliorare i metodi esistenti, offrendo agli utenti finali maggiore flessibilità e personalizzazione. Nonostante esistano diversi lavori recenti che affrontano varianti di Shop Scheduling Problem, basati principalmente su Reinforcement Learning, essi risultano qualitativamente inferiori rispetto alle metodologie classiche. Pertanto, parte di questo lavoro mira ad indagare e sviluppare nuovi paradigmi di apprendimento supervisionato per la risoluzione di un problema ben conosciuto e di rilievo, ovvero il Job Shop Scheduling. In particolare, si utilizzano strategie di apprendimento supervisionato per migliorare un noto algoritmo metaeuristico, il Tabu Search, guidandolo durante l’esplorazione con un modello di Machine Learning sequenziale. Inoltre, sempre in riferimento al problema del Job Shop, viene sviluppato un sistema end-to-end che si basa su una strategia di auto-apprendimento. Tale strategia non richiede soluzioni ottimali costose da cui imparare e non ricorre al Reinforcement Learning. Da notare che quest'ultimo sistema ottiene risultati migliori rispetto a tutti i recenti approcci basati su Machine Learning. Nella restante parte di questo lavoro si studia un nuovo e complesso problema di pianificazione derivante da un'industria manifatturiera, dove macchine parallele e vincoli di forza lavoro si intrecciano con vincoli di precedenze. Nonostante questi vincoli siano già separatamente studiati in varianti di altri problemi, la loro congiunzione crea uno scenario che modifica e invalida le assunzioni alla base di molte metodologie tradizionali. Pertanto, tale problema viene meticolosamente formalizzato, si sviluppano lower bound per valutare nuovi algoritmi, si adattano euristiche derivanti da altri problemi di pianificazione e infine viene proposto un nuovo metodo per risolvere efficientemente il problema. Riteniamo che questo lavoro costituisca un passo in avanti nell'ampliare il repertorio delle metodologie di risoluzione dei problemi di pianificazione e contribuisca ad adattare le tecniche esistenti alle sfide industriali del mondo reale.