Discrete event systems simulation-optimization : time buffer framework

The optimization of stochastic Discrete Event Systems (DES’s) is a critical and difficult task to be addressed. Indeed, besides the search for the optimal system configuration, it requires the assessment of the system performance. In other words, both an optimization problem and a simulation problem need to be solved. In the literature this framework is referred to as Simulation–Optimization.Traditionally, the simulation–optimization architecture is made of two decoupled modules: an optimization module (generative module), solving the optimization problem and a simulation module (evaluative module), solving the simulation problem. These two modules work iteratively until the optimal solution is found or a predefined stopping condition is met. The optimization module does not contain the description of the system dynamics. The simulation module, instead, can evaluate the system performance since it embeds the description (explicit or implicit) of the system behaviour; however, as no optimization procedure is contained within this module, it cannot optimize the system configuration. Hence, in the scope of simulation– optimization, both modules are required. Mathematical Programming Representation (MPR) can be applied to avoid this decoupled architecture. Indeed, if the dynamics of the system can be represented by means of a set of constraints, they can be embedded in the optimization model. As a result, the DES is optimized and simulated at the same time. This thesis proposes an integrated simulation–optimization framework based on the use of mathematical programming for both configuration generation (i.e., to solve the optimization problem) and system performance assessment (i.e., to solve the simulation problem). Specifically, LP models for simulation–optimization, developed based on the Time Buffer (TB) concept, are proposed. The TB is a continuous approximation to replace the integer decision variables defined in the original optimization problem. In general, to approximate a discrete variable with a TB, it must be possible to formally describe its effects on the events characterizing the system dynamics.Herein, the time buffer framework is formalized, describing the tractable classes of Discrete Event Systems and optimization problems. The approach steams from the description of the simulation–optimization problem, i.e., (1) the objective of the optimization, (2) the constraints on the decision variables, (3) the description of the system behavioural rules. Afterwards, the IP mathematical model for simulation optimization can be developed and the TB–based LP counterpart can be derived. The solution of the TB models provides a good approximate integer solution to the optimization problem and robust bounds on the exact solution, i.e., upper and lower limit defining the interval where the optimal solution lays. The time buffer concept has been applied for approximating the buffer capacity in an open flow line to solve the Buffer Allocation Problem and for approximating the number of pallets in a loop line to solve the Pallet Allocation Problem. For the open line case, the characteristics of the TB models were exploited to analyse the second order properties of objective function and constraints. The algorithm TBoptSIM was developed for the solution of the Buffer Allocation Problem and its asymptotic properties were analysed in terms of convergence. Moreover, this thesis represents the first contribution in the modelling of closed queuing networks adopting the TB approach. Hence, at first, it was necessary to prove that the loop system case was tractable within the time buffer framework. The tractability was proved showing the bounds derivation from the approximate simulation model. The algorithm (PAP) was developed to solve the Pallet Allocation Problem; differently from the TBoptSIM algorithm, the analysis of the PAP algorithm asymptotic behaviour is still ongoing work. This work was partially funded by the European research project Virtual Factory Framework (grant agreement No.: NMP2–LA–2010– 228595). In the scope of the project, the developed simulation – optimization application has been integrated within the Virtual Factory (VF) platform forming, with other connected tools, a first proposal of a comprehensive suite for the factory design. This framework answers a relevant industrial problem: the need for a unique platform of applications for the design of complex manufacturing systems. In summary, this thesis provides a new approach towards the optimization (and simulation) of a class of Discrete Event Systems using mathematical programming. The obtained models can be used as the first step of the optimization procedure, providing the subsequent search algorithm with a good starting solution and robust bounds.

L’ottimizzazione di sistemi stocastici a eventi discreti (SED) è un task critico e complesso. Infatti, oltre alla ricerca della configurazione ottima, le performance del sistema devono essere valutate. In altre parole, si devono risolvere sia un problema di ottimizzazione che un problema di simulazione. In letteratura, questo framework va sotto il nome di Simulazione – Ottimizzazione. Tipicamente, l’architettura di Simulazione-Ottimizzazione consta di due moduli indipendenti: un modulo di ottimizzazione (modulo di generazione) atto a risolvere il problema di ottimizzazione e un modulo di simulazione (modulo di valutazione) dedito a risolvere il problema di simulazione. Tali moduli lavorano iterativamente fino a quando una determinata condizione di stop viene soddisfatta. Il modulo di ottimizzazione non contiene la descrizione della dinamica del sistema. Il modulo di simulazione, invece, può stimare la performance del sistema dal momento che incorpora la descrizione del comportamento del sistema stesso in modo implicito o esplicito. Tuttavia, dal momento che tale modulo non contiene alcuna procedura di ottimizzazione, non può identificare in alcun modo la configurazione ottima. Per tale ragione entrambi i moduli risultano necessari. La tecnica di Programmazione Matematica (PM) può rappresentare un alternativa a quanto presentato finora. Infatti, se la dinamica del sistema può essere modellata mediante un insieme di vincoli, allora i medesimi vincoli possono essere inseriti nel modello (matematico) di ottimizzazione. Il risultato di questo il SED è ottimizzato e simulato allo stesso tempo. Questo lavoro propone un framework integrato di simulazione e ottimizzazione basato sulla programmazione matematica sia per la generazione della configurazione ottima (i.e., per risolvere il problema di ottimizzazione) sia per la valutazione delle performance del sistema (i.e., per risolvere il problema di simulazione). In dettaglio, modelli lineari (LP) per la simulazione e ottimizzazione sono stati sviluppati basandosi sul concetto di Time Buffer (TB), una approssimazione nel continuo che rimpiazza le variabili di tipo intero definite nel problema di ottimizzazione originale. In generale, per poter approssimare una variabile intera con il time buffer deve essere possibile descrivere gli effetti che la variabile intera reca alla sequenza degli eventi che caratterizzano il sistema. In questo lavoro, il framework basato sul time buffer viene formalizzato descrivendo la classe di SED e problemi di ottimizzazione che ivi risultano trattabili. L’approccio presentato si sviluppa dalla descrizione del problema di simulazione – ottimizzazione, i.e., (1) la funzione obiettivo, (2) i vincoli sulle variabili decisionali, (3) la descrizione della dinamica del sistema. A valle di questo, il modello matematico intero (IP) per risolvere il problema viene sviluppato e il modello LP approssimato basato sul TB può essere derivato. La soluzione del modello TB rappresenta una soddisfacente approssimazione della soluzione al problema IP originale e un intervallo, robusto, all’interno del quale giace la soluzione ottima. Il concetto del TB è stato applicato per approssimare la capacità dei buffer in una linea a trasferta risolvendo il problema dell’allocazione ottima della capacità. Inoltre, si è approssimato il numero di pallet in una linea chiusa per risolvere il problema della ricerca del numero minimo di pallet per garantire una certa capacità produttiva. Per il caso delle linee aperte e dell’ottimizzazione dei buffer, il framework di PM è stato sfruttato per derivare le proprietà di primo e secondo ordine dei modelli approssimati. Per risolvere il problema viene proposto l’algoritmo TBoptSIM per il quale vengono formalizzate le proprietà in termini di convergenza. Questo lavoro di tesi rappresenta il primo contributo nella modellazione di sistemi chiusi mediante modelli basati su TB. In tal modo è stato possibile provare la trattabilità di questo tipo di sistemi mediante il framework proposto. Anche per il caso di sistemi chiusi (problema di allocazione ottima del numero di pallet) è stato sviluppato un algoritmo per la soluzione dell’ottimizzazione. Tuttavia, la dimostrazione delle proprietà di tale algoritmo fa parte degli sviluppi attuali. Questa tesi è stata parzialmente finanziata dal progetto Virtual Factory Framework (grant agreement No.: NMP2–LA–2010–228595) è stato proprio nell’ambito del progetto che la applicazione di simulazione – ottimizzazione sviluppata è stata integrata nella piattaforma VFF, i.e., una prima proposta di ambiente integrato per la progettazione di fabbrica. Questo framework costituisce una rilevante risposta ad una importante problematica industriale: la necessità di un’unica piattaforma per le applicazioni dedite alla progettazione di sistemi di fabbricazione complessi. Questa tesi fornisce un nuovo approccio per l’ottimizzazione e simulazione di sistemi a eventi discreti basato su programmazione matematica. Inoltre, i modelli risultanti possono essere usati come primo step di una più ampia ricerca dell’ottimo fornendo agli algoritmi successivi una buona soluzione iniziale e un intervallo all’interno del quale si può garantire la presenza dell’ottimo.