Resource allocation problems in manufacturing systems using white-box-simulation-based cut generation approach

The optimization, including design, control, and operational management, of manufacturing systems is very relevant from a practical point of view and challenging from a scientific perspective. The design, control and operational management parameters generally influence the system intricately, and changing the parameters can improve some performance indicators, but diminish other ones or increase the cost in the meantime. Thus, the parameters should be carefully chosen to deal with the trade-off among performance indicators and cost, so that the manufacturers can improve productivity, reduce cost and gain profit optimally and eventually improve their competitiveness. This thesis solves a wide set of optimization problems in multi-stage high-volume manufacturing systems with blocking mechanisms, namely the extit{resource allocation problem} (RAP). RAPs are constrained optimization problems, with the objective of minimizing the cost respect to target system performances or optimizing a performance measure respect to a given budget. Both performance measures and cost are monotonically increasing on the decision variables, namely amount of resources allocated to different parts of the system. Thus, the optimal solution locates on the feasibility boundary, and it represents difficult cases of constrained optimization. Even though having drawn great attention in the literature, the algorithm design of RAPs is remaining a difficult task. Due to the complex system architecture and the various sources of uncertainty, performance evaluation of manufacturing systems is usually conducted with black-box functions, either analytical approaches or simulation. Consequently, approximate algorithms dominate the literature of optimization of manufacturing systems, and the only few exact methods cannot be applied to deal with large systems. This thesis proposes sample-path exact algorithms to solve RAPs. Despite the variety of problems solved, all the proposed algorithms belong to a common framework. The RAPs are first formulated with Mathematical Programming (MP) models integrating the simulation as the performance evaluation method under the state-of-the-art framework Discrete Event Optimization (DEO). A new solution method is proposed to deal with the computational issue and solve the models efficiently. Specifically, Benders decomposition is applied to the DEO models, resulting in two submodels. The two submodels represent simulation and the optimization, respectively. Following the Benders decomposition procedure, the two submodels compose an iterative procedure, where i) the simulation generates Benders cuts and ii) the optimization of the RAPs is solved as MP. A Benders cut partitions a subset of the solution region of the RAP as infeasible, so that the feasibility boundary is gradually defined with the cuts added. Furthermore, this work proposes simulation-based cut generation approach, with the white-box MP representation of the simulation. The proposed algorithms are applied to throughput improvement via downtime reduction, buffer allocation problem, integer resource allocation problems with performance constraints and joint buffer and pallet allocation. Numerical analysis shows that the proposed approaches outperform the state-of-the-art heuristics or black-box optimization algorithms in terms of the quality of the solutions and computational efficiency. Furthermore, the real cases are also studied with the proposed approaches, showing that the proposed algorithms can solve real cases within reasonable time and provide suggestions to improve the current systems.

L’ottimizzazione dei sistemi di produzione manufatturieri, incluse le fasi di progettazione, controllo e gestione operativa degli stessi, è un concetto tanto rilevante da un punto di vista pratico quanto stimolante da un punto di vista scientifico. I parametri delle suddette fasi di progettazione, controllo e gestione operativa incidono profondamente sul sistema e sulle sue prestazioni e, andando a modificarli, si possono migliorare alcuni indicatori di rendimento ma allo stesso tempo diminuirne altri o aumentare i costi. Pertanto, tali parametri dovrebbero essere scelti accuratamente, cercando di arrivare al miglior compromesso tra costi e performance del sistema. Questo processo porta a migliorare la produttività del sistema, ridurne i costi ed ottenere profitti più alti: in altre parole, tutto ciò porta i produttori ad aumentare la loro competività. Questa tesi risolve un'ampia serie di problemi di ottimizzazione per sistemi di produzione manufatturieri multi-fase con meccanismi di blocco e caratterizzati da un alto volume produttivo; tali problemi di ottimizzazione rientrano nella categoria dei cosiddetti “problemi di allocazione delle risorse” o, dall’inglese “Resource Allocation Problems” (RAP). Quest’ultimi sono problemi di ottimizzazione vincolata, il cui obiettivo può essere o la minimizzazione del costo dato un target di performance del sistema oppure il massimizzare le performance del sistema dato un determinato budget. Tuttavia, sia le misure di performance che i costi sono monotonamente crescenti sulle variabili decisionali, ovvero la quantità di risorse allocate alle diverse parti del sistema. Pertanto, la soluzione ottima si colloca sul confine di fattibilità e rappresenta casi complicati di ottimizzazione vincolata. Nonostante la letteratura riguardante i RAP sia vasta, riuscire a scrivere un algoritmo per tali problemi rimane un compito arduo. A causa della complessa architettura dei sistemi e delle numerose fonti di incertezza, la valutazione delle prestazioni dei sistemi di produzione viene solitamente condotta con funzioni black-box, approcci analitici o simulazioni. Di conseguenza, gli algoritmi approssimati dominano la letteratura sull'ottimizzazione dei sistemi di produzione e gli unici pochi metodi esatti non possono essere applicati per gestire sistemi di grandi dimensioni. Questa tesi, d’altro canto, propone algoritmi esatti e basati su una sequenza di campioni per risolvere i RAP. Nonostante la varietà dei problemi risolti, tutti gli algoritmi proposti appartengono a un framework comune. I RAP vengono prima formulati con modelli di Programmazione Matematica (PM); quest’ultimi utilizzano la simulazione come metodo di valutazione delle prestazioni all’interno del framework all’avanguardia dell’ottimizzazione ad eventi discreti o, dall’inglese, “Discrete Event Optimization” (DEO). Viene quindi proposto un nuovo metodo di soluzione per affrontare il problema computazionale e risolvere dunque i modelli in modo efficiente. In particolare, la decomposizione di Benders viene applicata ai modelli DEO, ottenendo due sottomodelli. I due sottomodelli rappresentano rispettivamente la simulazione e l'ottimizzazione. Seguendo la procedura di scomposizione di Benders, i due sottomodelli compongono una procedura iterativa, dove i) la simulazione genera i cosiddetti “Benders cuts” e ii) l'ottimizzazione dei RAP viene risolta come PM. Un Benders cut partiziona un sottoinsieme della regione di soluzione del RAP etichettandolo come non fattibile; in tal modo il confine di fattibilità viene gradualmente definito con dei cuts aggiuntivi. Inoltre, questo lavoro propone un approccio di generazione dei cuts basato sulla simulazione, con una rappresentazione white-box PM della simulazione stessa. Gli algoritmi proposti in questa tesi vengono applicati al miglioramento del throughput tramite la riduzione dei tempi di fermo, i problemi di allocazione dei buffer, i problemi di allocazione di risorse intere con vincoli di prestazioni e allocazione congiunta di buffer e pallet. L'analisi numerica mostra che gli approcci proposti superano le euristiche all'avanguardia o gli algoritmi di ottimizzazione black-box in termini di qualità delle soluzioni ed efficienza computazionale. Inoltre, vengono studiati anche dei casi reali con gli approcci proposti, dimostrando che gli algoritmi proposti possono risolvere casi reali in tempi ragionevoli e fornire suggerimenti per migliorare i sistemi attuali.