Algoritmi di Rollout per il problema del Job Shop Scheduling

Introduzione 0 Introduzione I problemi di scheduling sono problemi decisionali in cui riveste importanza fondamentale il fattore tempo, inteso come risorsa (scarsa) da allocare in modo ottimale. In particolare, nei problemi di scheduling su macchine la risorsa-tempo è identificata con il tempo dedicato da alcune macchine al processamento di attività. Il problema del job shop scheduling è una particolare istanza del problema di scheduling su macchine in cui le attività sono rappresentate da operazioni e l’assegnamento delle operazioni alle macchine avviene rispettando dei vincoli di precedenza tra le operazioni stesse. Questo problema è stato oggetto di numerosi studi nell’ambito della Ricerca Operativa, che hanno consentito di sviluppare diversi modelli che lo rappresentano e differenti metodi per risolverlo. Tuttavia, data la natura NP-HARD del problema (la maggior parte delle istanze non sono risolvibili in tempo polinomiale), a tutt’oggi non è possibile identificare un approccio preferibile in assoluto per la sua soluzione. La sua complessità computazionale ha indirizzato la ricerca verso lo sviluppo di algoritmi euristici, che hanno come obiettivo quello di calcolare una soluzione approssimata, quanto più possibile vicina a quella ottimale. Tra i vari approcci euristici proposti in letteratura i più promettenti risultano essere quelli che impiegano meta- euristiche, quali il tabu search, il simulated annealing e gli algoritmi genetici, che in