Riassunto analitico
Questa tesi presenta i risultati del lavoro svolto con il FZI Forschungszentrum Informatik (Centro di Ricerca per l’Informatica) di Karlsruhe, riguardante la formulazione e la risoluzione di un problema di schedulazione di un'azienda tedesca nel settore dell'automazione. Il problema trattato è noto in letteratura come Unrelated Parallel Machine Scheduling (UPMS) e lo scopo di questo studio è quello di fornire uno strumento per risolvere il problema della schedulazione di componenti da temprare nei forni, con l'obiettivo di minimizzare il tempo totale di completamento. Questo problema è affrontato con lo sviluppo di un modello MILP (Mixed-Integer Linear Programming) della situazione reale. Dato l'ampio tempo di calcolo richiesto da un risolutore basato su Branch-and-Bound per trovare soluzioni ottimali al modello all'aumentare del numero di parti, è presentato anche un approccio di ricerca euristica. In particolare, sono proposti e valutati diversi operatori di vicinato con l'obiettivo di trovare quello più promettente. Sia il modello matematico che l'algoritmo euristico sono implementati in Java e il modello è risolto con l’IBM ILOG CPLEX Optimizer, uno strumento per la risoluzione di problemi di ottimizzazione misti-interi. Il modello matematico e l'approccio euristico sono testati con istanze generate secondo il processo di produzione reale. I loro risultati computazionali vengono confrontati per valutare le prestazioni dell'approccio euristico rispetto al modello e anche per analizzare quale dei diversi operatori proposti fornisca risultati migliori. L'esatto processo di risoluzione della formulazione matematica deve essere migliorato per soddisfare i requisiti del mondo reale in termini di tempo di esecuzione, ma due operatori mostrano risultati promettenti con soluzioni euristiche quasi ottimali.
|
Abstract
This thesis presents the results of the work carried out with the FZI Forschungszentrum Informatik (i.e. Research Centre for Information Technology) of Karlsruhe, concerning the formulation and resolution of a scheduling problem of a German company in the automation industry.
The problem addressed is known in the literature as Unrelated Parallel Machine Scheduling (UPMS) and the aim of this study is to provide a tool to solve the problem of scheduling gear parts to be hardened in furnaces, with the objective of minimizing the total completion time.
This problem is tackled with the development of a Mixed-Integer Linear Programming (MILP) model of the real-world situation. Given the large computation time required by a Branch-and-Bound-based solver to find optimal solutions to the model as the number of parts increases, a heuristic search approach is also presented. In particular, several neighbourhood operators are proposed and evaluated with the aim of finding the most promising one. Both, the mathematical model and the heuristic algorithm, are implemented in Java and the model is solved with IBM ILOG CPLEX Optimizer, a tool for solving mixed-integer optimization problems.
The mathematical model and the heuristic approach are tested with instances generated according to the real-world production process. Their computational results are compared to assess the performance of the heuristic approach with respect to the model and in addition to evaluate which of the different proposed operators gives better results. The exact solving process of the mathematical formulation needs to be improved to meet real-world requirements in terms of runtime, but two operators show promising results with regard to near-optimal heuristic solutions.
|