Riassunto analitico
Questa tesi è stata scritta in conclusione di un'attività di tirocinio aziendale.
Lo scopo di questa tesi è quello di presentare il famoso Job Shop Problem, uno dei più complessi problemi di ricerca operativa, sia come problema teorico, sia come modello matematico del problema concreto della pianificazione di produzione di un'azienda.
Nel primo capitolo andremo a introdurre il problema, fornendo alcune definizioni di base, esempi e criticità dovute alla complessità del problema stesso. Tratteremo inoltre degli Algoritmi di Branch and Bound, una classe di algoritmi ampiamente utilizzata, in combinazione con diverse euristiche, per la risoluzione di problemi di ottimizzazione combinatoria, quale può essere considerato il Job Shop Problem. Infine presenteremo Or Tools, una libreria open source molto usata per risolvere computazionalmente problemi di ottimizzazione, e un primo piccolo esempio di codice Python risolutivo del Job Shop Problem.
Nel secondo capitolo mostreremo come modellare matematicamente un problema reale di pianificazione della produzione di un'azienda, basandosi sul modello del Job Shop problem, ma introducendo un grande numero di casistiche aggiuntive da dover gestire, quali i turni degli operatori, i fermi di macchina, la gestione del magazzino e così via. Presenteremo poi la soluzione sviluppata dall'azienda sede del tirocinio per la risoluzione di tale problema, soffermandoci in particolare sul modello, ovvero sulla creazione delle variabili e sull'imposizione dei vincoli.
Nel terzo capitolo infine ci concentreremo sui punti più critici del modello precedentemente presentato. Spiegheremo in quali errori si possa incorrere e mostreremo quindi possibili miglioramenti introducibili. Presenteremo poi i risultati di alcune sperimentazioni effettuate su dati reali di un'azienda manifatturiera.
|
Abstract
This thesis was written as part of a company internship. The aim of this thesis is to present the famous job shop problem, one of the most complex operational research problems, both as a theoretical problem and as a mathematical model of the concrete problem of a company's production planning. In the first chapter we will introduce the problem, providing some basic definitions, examples and critical issues due to the complexity of the problem itself. We will also discuss Branch and Bound Algorithms, a class of algorithms widely used, in combination with different heuristics, for solving combinatorial optimization problems, such as the Job Shop Problem. Finally, we will present Or Tools, an open source library widely used to computationally solve optimization problems, and a first small example of Python code solving the Job Shop Problem. In the second chapter we will show how to mathematically model a real-world production planning problem, based on the model of the Job Shop problem, but introducing a large number of additional cases to be managed, such as operator shifts, machine stops, warehouse management and so on. We will then present the solution developed by the company home of the internship for the resolution of this problem, focusing in particular on the model, namely on the creation of variables and the imposition of constraints. Finally, in the third chapter we will focus on the most critical points of the previously presented model. We will explain what errors can be incurred and then show possible improvements that can be introduced. We will then present the results of some trials carried out on real data of a manufacturing company.
|
