Riassunto analitico
L’obiettivo di questo lavoro di Tesi è quello di sviluppare e sperimentare un nuovo sistema di supporto alle decisioni per la riprogettazione del layout industriale di un impianto produttivo. Il lavoro di Tesi svolto apporta delle modifiche ad un algoritmo metaeuristico Ant Based per la risoluzione del Quadratic Assignment Problem (QAP) per adattarlo alla soluzione di problemi reali di progetto del layout. Il modello di base per la definizione del layout è il QAP, problema di ottimizzazione combinatoria NP-difficile. Dato un set di n zone ed un set di n reparti il problema chiede di assegnare i reparti alle zone minimizzando il costo totale di assegnamento. Tale costo è funzione della distanza tra le zone ed il flusso tra i reparti. Essendo estremamente onerosa, dal punto di vista computazionale, la risoluzione esatta del modello matematico, si è fatto ricorso ad un algoritmo metaeuristico Ant Based, il Fast Ant System (FANT). L’ algoritmo è stato poi modificato per poter assecondare le logiche del sistema di supporto alle decisioni per il problema della definizione del layout aziendale. La prima novità introdotta è relativa al vincolo sulle “capacità di area” ed è stato trattato con l’introduzione di una matrice di "Contro-Feromoni" e di una componente di costo “Incompatibilità”. La matrice dei “Contro-Feromoni” contiene informazioni sulla “bontà” degli assegnamenti. Il Contro-Feromone è alto in corrispondenza delle coppie reparto-zona che rispettano il vincolo di capacità, al contrario, laddove il vincolo non è rispettato, i Contro-Feromoni assumono un valore molto basso.La seconda modifica è relativa a vincoli spaziali e modella il problema aggiungendo alla formulazione base del QAP una valutazione sulla la sovrapposizione tra zone. Per trattare la sovrapposizione sono stati seguiti due approcci: un vincolo rigido (hard) di non sovrapposizione e un vincolo flessibile (soft), che ammette sovrapposizioni, ma con penalizzazioni. Nella trattazione “rigida”, una soluzione che prevede sovrapposizione tra zone viene considerata inammissibile e dunque scartata. Nella trattazione flessibile, invece, si è disposti ad accettare sovrapposizione tra le zone (entro determinati limiti) a fronte di un notevole miglioramento della funzione obiettivo. La terza ed ultima modifica che ho apportato alla metaeuristica originale è relativa alla trattazione del problema non come mono-obiettivo ma come multi-obiettivo. I flussi di prodotti tra reparti sono stati valorizzati con diverse grandezze, quali: volume, peso, frequenza e quantità. Per ogni grandezza si vorrebbe minimizzare il valore della funzione obiettivo. Il sistema provvede a generare soluzioni Pareto-ottimali tra cui il decisore selezionerà la soluzione “ottima” secondo il suo giudizio empirico. Il caso applicativo è fornito da Dallara Automobili Spa, azienda specializzata nella produzione di vetture da corsa. Il problema specifico richiede di riprogettare il layout dell’officina produttiva a fronte della costruzione di un nuovo capannone dove saranno trasferiti due dei reparti produttivi dell’azienda. Si richiede di riorganizzare il layout del capannone attuale con i restanti reparti. Si tratta dunque di una situazione che non può giovare della libertà progettuale tipica dell’”ex novo”, ma che deve tenere in considerazione i vincoli spaziali attuali (muri portanti, pilastri).
|
Abstract
The objective of this thesis is the development and experimentation of a new decision support system for the redesign of factory layout. The thesis brings some modifications to an Ant Based Algorithm for the resolution of the Quadratic Assignment Problem (QAP) in order to readapt it to “real life” design problems of layout displacement. The basic model for the layout definition is the QAP, combinatorial optimization problem NP-hard. Given a set of n zones and a set of n departments, the aim of the problem is to assign the departments to zones minimizing the total assignment cost. The cost is a function of distances between zones and flows between departments. From a computational point of view, the exact resolution of the model is extremely complex so a metaheuristic Ant Based Algorithm has been used, namely the Fast Ant System (FANT). The algorithm has been modified in order to allow the logics of the decision support system for the factory layout design problem. The first contribution introduced is relative to “capacity constraints” and has been treated through the use of a "Counter-Pheromones" matrix and cost component called "Incompatibility”. The matrix of the "Counter-Pheromones" contains information about the goodness of assignments. The Counter-Pheromone is high relatively to department-area couples that meet the “capacity constraint” , on the contrary, they assume very low value if the “capacity constraint” is not respected.The second change is related to spatial constraints and models the problem adding to the basic formulation of the QAP an evaluation of the overlapping between zones. The overlapping between zones has been treated following two approaches: an “hard” constraint of non-overlapping and a “soft” constraint that allows penalized overlapping. In the “hard” version a solution with overlapped zones is considered inadmissible and discarded while, in the “soft” version, overlapping is permitted (within certain limits) if a valuable improvement of the objective function occurs. The last modification that has been brought to the metaheuristic algorithm wants to treat the problem not as a mono-objective but multi-objective. The product flows between departments have been considered in terms of different magnitudes: volume, weight, frequencies and quantities. The willing is to minimize the objective function value for each magnitude. The system provides a set of Pareto-optimal solutions among which the decision maker will individuate the “optimal” solution following his empirical experience. The “real life” case is Dallara Automobili Spa, a company specialized in the production of racing cars. The specific problem requires redesigning the production workshop layout because of the construction of a new building in which two production departments of the company will be moved. The production workshop layout has to be redesigned considering the remaining production departments, thus, the problem has to take into account current spatial constraints (bearing-walls and pillars).
|
