Estensioni del Problema del Paging: Analisi di Competitività e Valutazione Sperimentale per la Stampa 3D in Medicina

L'ottimizzazione dei processi produttivi rappresenta un tema di grande interesse sia dal punto di vista teorico sia da quello applicativo. Il presente lavoro nasce da una problematica osservata presso il laboratorio 3D4Med, dove vengono realizzati modelli anatomici mediante stampa 3D per applicazioni chirurgiche. In tale contesto, la limitata disponibilità di slot per le cartucce dei materiali rende necessario decidere, durante la produzione, quali materiali mantenere installati e quali sostituire, con l'obiettivo di ridurre il numero dei cambi e il relativo costo. Il problema è stato affrontato nell'ambito dell'ottimizzazione online, assumendo che la sequenza dei modelli da produrre non sia nota a priori ma venga rivelata progressivamente. Come modello di riferimento è stato considerato il problema del paging, che descrive la gestione di una memoria cache di capacità limitata, successivamente esteso al caso in cui ciascuna richiesta possa coinvolgere simultaneamente più elementi (batch paging). Per rappresentare in modo più fedele il problema reale, è stata inoltre introdotta una versione pesata del modello, nella quale i materiali sono associati a costi di sostituzione non uniformi. In questo contesto sono stati adattati e analizzati alcuni algoritmi online della letteratura, introducendo una versione batch con protezione, nella quale i materiali richiesti dalla stessa stampa non possono essere rimossi durante l'elaborazione della richiesta. Parallelamente, è stato formulato un modello di Programmazione Lineare Intera Mista (MILP), utilizzato per determinare la soluzione ottima offline e come termine di confronto per la valutazione degli algoritmi online. Infine, è stata condotta un'analisi sperimentale su istanze ispirate ai dati del laboratorio 3D4Med, confrontando le prestazioni degli algoritmi proposti con la soluzione ottima ottenuta tramite MILP. I risultati mostrano che l'estensione batch di GreedyDual è in grado di ottenere prestazioni molto vicine all'ottimo offline, evidenziando come l'approccio proposto costituisca una strategia efficace per la gestione delle sostituzioni di materiale nel contesto della stampa 3D medicale.

The optimization of production processes is a topic of great interest from both a theoretical and an applied perspective. This work originates from a problem observed at the 3D4Med laboratory, where anatomical models are produced through 3D printing for surgical applications. In this context, the limited number of available material cartridge slots requires deciding, during the production process, which materials should remain installed and which should be replaced, with the objective of reducing both the number of material changes and their associated costs. The problem is addressed within the framework of online optimization, under the assumption that the sequence of models to be produced is not known in advance but is revealed progressively. As a reference model, the paging problem is considered, describing the management of a cache memory with limited capacity, and subsequently extended to the case in which each request may simultaneously involve multiple items (batch paging). To provide a more realistic representation of the practical problem, a weighted version of the model is also introduced, where materials are associated with non-uniform replacement costs. In this setting, several online algorithms from the literature are adapted and analyzed by introducing a protected batch version, in which the materials required by the same print job cannot be removed while processing the corresponding request. In parallel, a Mixed-Integer Linear Programming (MILP) model is formulated to compute the optimal offline solution and to provide a benchmark for evaluating the performance of the online algorithms. Finally, an experimental analysis is carried out on instances inspired by data provided by the 3D4Med laboratory, comparing the proposed algorithms with the optimal solution obtained through the MILP model. The results show that the batch extension of GreedyDual achieves performance very close to the offline optimum, highlighting the effectiveness of the proposed approach for managing material replacements in the context of medical 3D printing.