Sviluppo di tecniche di miglioramento dinamico di rollout per lo scheduling

Nella maggior parte dei sistemi produttivi gli obiettivi principali sono quelli che riguardano la pianificazione ed esecuzione della produzione e dello scheduling delle attività in tempo per le consegne, ed allo stesso tempo la massimizzazione del valore del prodotto.
Questi due scopi sono spesso in conflitto, dal momento che i numerosi tempi di setup e di idle portano ad una diminuzione della produttività (più i costi di produzione sono elevati e più si minimizzano i tempi).
Spesso queste attività di decisione vengono condotte da persone che sviluppano schedulazioni attuabili e predittive basate sulla loro esperienza e sulla loro intuizione.
Lo sviluppo e l’implementazione di efficaci sistemi computerizzati per questi problemi richiede che vengano tenuti in considerazione molti aspetti, che raramente vengono esaminati allo stesso tempo dalla teoria dello scheduling.
Si ha a che fare, quindi, con problemi di natura NP-Completa, dei quali non si conosce un metodo esatto di risoluzione e che comunque comportano una notevole complessità computazionale.
Gli studi della ricerca operativa e dell’automazione industriale, che si occupano di questo tipo di problemi, si sono pertanto orientati verso approcci euristici. Questi consistono nell’utilizzo di euristiche per ottenere delle buone soluzioni in tempi computazionali soddisfacenti.
Uno di questi metodi è quello proposto da Bertsekas e che viene chiamato algoritmo di rollout. Il rollout offre soluzioni migliori e più robuste rispetto ad altri metodi euristici, ma ancora non abbastanza efficienti dal punto di vista dei tempi computazionali di risoluzione.
L’argomento centrale di questa tesi è quello di sviluppare delle tecniche di miglioramento dinamico dell’algoritmo di rollout applicato ad una particolare classe di problemi di scheduling.
Il miglioramento dinamico comporta un abbassamento dei tempi computazionali senza perdita nella bontà della soluzione rispetto al rollout originale ed è ottenuto attraverso l’applicazione, durante l’esecuzione, di modifiche allo schema base dell’algoritmo.