Facoltà: Ingegneria Gestionale per la Produzione Industrial
Collocazione: 12957
Autore: Bardelli Andrea
Data: 20/12/2013
Titolo: Comparison between heuristic algorithms for parallel machine scheduling: Two Real-Case Applications in Plastic Moulding Environment.
Relatore: Rossi Tommaso
Autorizzazione per la consultazione: NO
Le tesi si possono consultare unicamente in sede
All’interno dell’elaborato viene ripercorso l’iter tracciato dai numerosi studi condotti nel campo dello scheduling nel corso degli ultimi sessant’anni. Tale analisi, limitata al campo delle macchine parallele, sviluppa la consapevolezza che gli algoritmi sviluppati fino agli anni novanta possiedono un’impronta prettamente teorica, mentre le pubblicazioni piu recenti hanno progressivamente incentrato il focus su problemi realistici. La finalità di questa ricerca è la selezione di due algoritmi che costituiscano le fondamenta per lo sviluppo dei due software dedicati ai casi aziendali di riferimento. Per incontrare le esigenze aziendali è stato necessario includere negli algoritmi funzionalità aggiuntive al fine di raggiungere una soluzione realmente applicabile. Entrambi i programmi sono stati sviluppati in Excel tramite l’ambiente Visual Basic for Applications, seguendo una struttura basata su tre layer: algoritmo, database ed interfaccia. Quest’ultima è stata sviluppata in modo tale da garantire una facile interazione con l’utilizzatore. Obiettivo primario di questo elaborato è sviluppare un confronto tra le due soluzioni proposte, al fine di fornire ad un eventuale committente degli strumenti di valutazione per effettuare la scelta tra le due soluzioni proposte. Per effettuare un confronto che valuti anche la bontà della soluzione, intesa come distanza dal punto di ottimo, viene implementato un metodo enumerativo in grado di trovare la soluzione esatta in un tempo esponenzialmente crescente. Per questo motivo, il confronto tra il metodo enumerativo ed i due algoritmi può essere condotto solo su problemi di dimensioni ridotte. Al fine di ottenere un confronto esaustivo è necessario estendere le dimensioni dei problemi considerati. Questo permette di prendere in esame casi reali, valutando quale sia l’algoritmo maggiormente adattabile ad un contesto che contempli un obiettivo non pienamente coincidente con quello ottimizzato dall’algoritmo. Si è riscontrata la presenza di un trade-off tra i due algoritmi in termini di tempi di calcolo - bontà della soluzione, sebbene ambedue gli algoritmi dimostrino una buona adattabilità. SUMMARY In the dissertation the route drawn by numerous studies conducted in the field of scheduling, over the last sixty years, is retraced. This analysis, limited to the parallel machines environment, highlights that the algorithms developed until the nineties show a purely theoretical imprint. On the other hand, the more recent publications progressively focus on more realistic problems. The purpose of this research is represented by the selection of two algorithms, which lay the foundations for both companies software development. In order to meet the business needs and to find a real-applicable solution, it has been necessary to include additional features into each algorithm. Both programs were developed in Excel using the Visual Basic for Applications, following a three-tier layered structure: an algorithm, database and user interface. The latter has been developed in order to ensure an easy user interaction. This paper’s primary objective is to develop a comparison between the two proposed implementations. This provides to a possible buyer the assessment tools necessary to assist the choice. To evaluate the quality of the solution, intended as the distance from the optimum, an enumerative method is implemented. This can find the exact solution in an exponentially growing time. For this reason, the comparison between the enumerative method and the two algorithms is conducted only on reduced-dimension instances. In order to obtain an effectual appraisal it is necessary to extend the problems size. This allows examining realistic instances, assessing which algorithm is the most adaptable to a context with a not fully coincident target. A trade-off between the two algorithms in terms of computational time - goodness of the solution is found, even if both algorithms show a good adaptability.
