Scheduling of an industrial stainer for histological samples

BioOptica’s stainer is an automated instrument composed of a series of reagent tanks used to execute staining protocols for histological samples. Incoming samples are mounted on holders and must visit a specific sequence of reagents (contained in tanks) with prescribed dwell times; both sequence and timings are defined in the protocols. A single robotic arm moves the holders between tanks and stations. The goal of this thesis is to design a scheduling algorithm that orchestrates tank usage and robot’s moves to make the opera tion efficient while strictly respecting protocol constraints. The scheduling problem is formalized as a Mixed-Integer Linear Program that minimizes makespan or weighted tardiness, subject to precedence, dwell-time bounds, and capac ity constraints. Binary disjunctions ensure mutual exclusion on shared resources. The transport-related distance rules are not explicit constraints in the initial model but emerge from the combined effect of these relations; any violation of temporal separation between operations is iteratively detected and corrected through a conflict-resolution loop that adds cuts until all inconsistencies are removed. Warm starts, preprocessing, and optional time-window tightening improve convergence. The software outputs Gantt charts per job and per resource and performs automatic consistency checks to detect infeasible or con tradictory inputs. We evaluate the scheduler on anonymized real protocols and synthetic workloads that vary transport times, resource multiplicity, and release/due-date tightness. Compared with greedy dispatching baselines, the MILP consistently reduces idle time and robot conflicts while preserving throughput. With alternative tanks, it balances loads and al leviates bottlenecks. Sensitivity analyses show robust feasibility under tighter distances and clarify trade-offs between lateness and utilization. The approach is reproducible (scripts and datasets available) and extensible to multi-objective criteria, online arrivals, and learning-augmented priority rules, making it a practical building block for laboratory automation.

Il coloratore automatico BioOptica è uno strumento composto da una serie di vasche di reagenti utilizzate per eseguire protocolli di colorazione su campioni istologici. I campi oni in ingresso vengono montati su appositi supporti e devono attraversare una sequenza specifica di reagenti (contenuti nelle vasche) rispettando tempi di permanenza prestabiliti; sia la sequenza che i tempi sono definiti dai protocolli. Un unico braccio robotico movi menta i supporti tra le diverse vasche e stazioni operative. L’obiettivo di questa tesi è progettare un algoritmo di schedulazione che coordini l’uso delle vasche e i movimenti del robot, rendendo l’intero processo efficiente e conforme ai vincoli imposti dai protocolli. Il problema di scheduling è stato formalizzato come un problema di Programmazione Lineare Intera Mista (MILP), con l’obiettivo di minimizzare il makespan o la tardi ness pesata, soggetto a vincoli di precedenza, limiti di permanenza (dwell time), capacità delle risorse e disgiunzioni binarie per l’esclusione reciproca tra operazioni incompatibili. Le regole di distanza temporale legate ai tempi di trasporto non sono espresse come vincoli espliciti nel modello iniziale, ma emergono come effetto combinato dei vincoli di sequenza, capacità e mutua esclusione. Eventuali violazioni delle separazioni tempo rali vengono rilevate e corrette tramite un ciclo iterativo di rilevamento e risoluzione dei conflitti, che aggiunge progressivamente vincoli fino all’eliminazione completa delle inco erenze. Tecniche di warm start, pre–processing e, facoltativamente, di restringimento delle f inestre temporali migliorano la convergenza del solutore. Il software sviluppato produce diagrammi di Gantt per job e per risorsa, e include controlli di consistenza per prevenire input non ammissibili. La validazione del modello è stata condotta su protocolli reali anonimizzati e su work load sintetici con variazione dei tempi di trasporto, della molteplicità delle risorse e della rigidità dei vincoli di rilascio e scadenza. Rispetto alle euristiche greedy di riferimento, il modello MILP riduce sistematicamente i tempi di inattività e i conflitti del robot, mantenendo invariato il throughput. In presenza di vasche alternative, il sistema bilan cia il carico e allevia i colli di bottiglia. Analisi di sensitività mostrano una robustezza della fattibilità anche in presenza di distanze più restrittive e mettono in evidenza i com promessi tra ritardo (lateness) e grado di utilizzo delle risorse. L’approccio proposto è riproducibile (script e dataset disponibili) ed estendibile a criteri multi–obiettivo, arrivi dinamici e tecniche di scheduling assistite da apprendimento, rendendolo un solido punto di partenza per l’automazione dei laboratori biomedici.