Energy-efficient scheduling of Flexible Manufacturing Systems

Routing-flexible Flexible Manufacturing Systems (FMSs) with shared machines and finite Work-in-Process (WIP) limits give rise to an Energy-Efficient Scheduling (EES) problem in which feasibility preservation and computational scalability are tightly coupled. Blocking, synchronization, and route-level congestion make feasibility highly sensitive to route-selection, sequencing and timing decisions, so that locally admissible choices may propagate into downstream infeasibility. At the same time, exact optimization through time-indexed Mixed-Integer Linear Programming (MILP) is attractive for its rigor, but its computational tractability deteriorates rapidly as the planning horizon grows. Existing approaches therefore tend to emphasize either discrete-event feasibility preservation or algebraic optimality, while a structured integration of feasibility modeling, exact improvement and scalability control remains limited. To address this gap, this thesis develops an integrated framework combining Petri Net (PN)-based discrete-event modeling, heuristic schedule construction, exact optimization and safe-horizon design. First, a Timed and Energy-aware Transition Petri Net (TETPN) is proposed to model routing flexibility, shared resources, technological precedence and route-level WIP constraints within explicit token-flow dynamics. On this basis, a Hybrid Filtered Beam Search Algorithm (HFBSA), together with its Randomized Beam-Retention extension (RBR-HFBSA), is developed to construct executable non-preemptive schedules while preserving feasibility at the system level. Second, a time-indexed MILP formulation semantically consistent with the TETPN is derived, and PN-generated schedules are translated into valid warm-start assignments for the optimization solver. In this way, discrete-event feasibility knowledge is injected into the exact optimization layer, substantially improving robustness in feasible-incumbent attainment and accelerating branch-and-bound convergence under time limits. Third, to address the dominant scalability bottleneck of time-indexed formulations, a lemma-based safe-horizon principle is established. By combining the objective value of a feasible schedule with a valid lower bound on production energy, a provably safe yet substantially tighter upper bound on the optimal makespan is derived. This principle is then operationalized through an aggregated route-selection model coupled with PN reconstruction and Discrete-Event Rollout (DER), yielding safe horizon values that reduce formulation size while preserving optimality. Extensive computational experiments on heterogeneous routing-flexible benchmark scenarios show that the proposed framework improves feasibility attainment, strengthens time-limited exact optimization and significantly enhances scalability, especially in large-scale and congestion-intensive settings. Overall, the thesis establishes a structured and scalable connection between discrete-event feasibility modeling and exact optimization for the EES of routing-flexible FMSs.

I sistemi manifatturieri flessibili (Flexible Manufacturing Systems, FMS) con flessibilità di instradamento, macchine condivise e limiti finiti di Work-in-Process (WIP) danno origine a un problema di scheduling energeticamente efficiente (Energy-Efficient Scheduling, EES) in cui la preservazione della fattibilità e la scalabilità computazionale risultano strettamente interconnesse. Fenomeni di blocco, sincronizzazione e congestione a livello di instradamento rendono la fattibilità altamente sensibile alle decisioni di selezione dei percorsi, sequenziamento e temporizzazione, cosicché scelte localmente ammissibili possono propagarsi generando infeasibilità a valle. Al tempo stesso, l’ottimizzazione esatta mediante programmazione lineare mista intera indicizzata nel tempo (Mixed-Integer Linear Programming, MILP) è attrattiva per il suo rigore metodologico, ma la sua trattabilità computazionale si deteriora rapidamente all’aumentare dell’orizzonte di pianificazione. Gli approcci esistenti tendono pertanto a privilegiare alternativamente la preservazione della fattibilità propria dei modelli a eventi discreti oppure l’ottimalità algebrica, mentre rimane limitata un’integrazione strutturata tra modellazione della fattibilità, miglioramento esatto e controllo della scalabilità. Per colmare tale lacuna, questa tesi sviluppa un framework integrato che combina modellazione a eventi discreti basata su reti di Petri (Petri Nets, PN), costruzione euristica degli schedule, ottimizzazione esatta e progettazione di orizzonti sicuri. In primo luogo, viene proposta una rete di Petri a transizioni temporizzate ed energeticamente consapevoli (Timed and Energy-aware Transition Petri Net, TETPN) per modellare la flessibilità di instradamento, le risorse condivise, le precedenze tecnologiche e i vincoli WIP a livello di percorso attraverso dinamiche esplicite di flusso dei token. Su questa base, viene sviluppato un algoritmo Hybrid Filtered Beam Search (HFBSA), insieme alla sua estensione Randomized Beam-Retention HFBSA (RBR-HFBSA), per costruire schedule eseguibili e non preemptive preservando la fattibilità a livello di sistema. In secondo luogo, viene derivata una formulazione MILP indicizzata nel tempo semanticamente coerente con la TETPN, e gli schedule generati tramite PN vengono tradotti in assegnamenti di warm start validi per il solutore di ottimizzazione. In questo modo, la conoscenza di fattibilità propria del modello a eventi discreti viene incorporata nel livello di ottimizzazione esatta, migliorando in modo sostanziale la robustezza nel conseguimento di incumbent fattibili e accelerando la convergenza branch-and-bound in presenza di limiti di tempo. In terzo luogo, per affrontare il principale collo di bottiglia in termini di scalabilità delle formulazioni indicizzate nel tempo, viene stabilito un principio di orizzonte sicuro basato su lemma. Combinando il valore della funzione obiettivo di uno schedule fattibile con un lower bound valido sull’energia di produzione, viene derivato un limite superiore sull’ottimo makespan che è dimostrabilmente sicuro e, al contempo, sostanzialmente più stretto. Tale principio viene quindi reso operativo mediante un modello aggregato di selezione dei percorsi accoppiato con una ricostruzione PN e con un Discrete-Event Rollout (DER), ottenendo valori di orizzonte sicuri che riducono la dimensione della formulazione preservando l’ottimalità. Estesi esperimenti computazionali su scenari benchmark eterogenei di FMS con flessibilità di instradamento mostrano che il framework proposto migliora il conseguimento della fattibilità, rafforza l’ottimizzazione esatta sotto limiti di tempo e accresce significativamente la scalabilità, in particolare in contesti di larga scala e caratterizzati da elevata congestione. Nel complesso, la tesi stabilisce una connessione strutturata e scalabile tra modellazione della fattibilità a eventi discreti e ottimizzazione esatta per l’EES di FMS con flessibilità di instradamento.