Ricerca Euristica su Rete di Petri per Scheduling con Vincoli di Risorsa

Un metodo innovativo per affrontare il Problema di Scheduling di Progetti con Risorse Vincolate (RCPSP) lo concettualizza come una ricerca ottimale all'interno del grafo di raggiungibilità di una Rete di Petri a Transizioni Temporizzate che incorpora Risorse, utilizzando token a ritardo relativo. La soluzione impiega A*, guidata da un'euristica che integra il Percorso Critico e limiti inferiori basati sulle risorse, dimostrata coerente con la semantica temporale basata sui token. I test sui benchmark PSPLIB indicano che questa tecnica supera i robusti benchmark esatti di Programmazione Lineare Mista Intera (MIP) (SCIP, CBC) sia in termini di tasso di successo che di tempo di risoluzione. L'analisi di singoli casi mostra che la ricerca euristica e il MIP si deteriorano lungo dimensioni diverse: A* è influenzato dalla rigidità delle risorse, mentre il MIP è influenzato dalla dimensione della formulazione, con la forza delle risorse che determina quale risolutore beneficia dell'aumento di scala.