Mateuristiche per il Fair Task Allocation Problem

Il seguente lavoro di tesi esamina la questione riguardante la distribuzione di compiti ad un insieme di agenti con la prerogativa di far fronte agli impegni contrattuali che li caratterizzano. I principali strumenti utilizzati per gestire il problema sono modelli di programmazione lineare. L'implementazione del problema è basata su un modello matematico noto come Fair Task Allocation Problem (FTAP). Mentre per il caso generale il problema è definito NP-hard, ciò significa che lo spazio delle soluzioni cresce in maniera esponenziale all’aumentare della dimensione del problema stesso, si dimostrerà come, per un determinato numero di compiti ed agenti, la sua risoluzione possa avere tempistiche polinomiali. L’obiettivo del lavoro di tesi riguarda dunque la progettazione e lo sviluppo di un algoritmo che permetta l'allocazione ottima dei tasks in tempi di risoluzione accettabili. L’algoritmo di risoluzione che si vuole progettare per risolvere questo problema è un algoritmo mateuristico affiancato ad un metodo di miglioramento della soluzione con approccio multi-start. Per sviluppare l’algoritmo inizialmente sono stati analizzati i tempi di calcolo del problema tramite la risoluzione con un metodo approssimato. Tale approccio ha permesso di individuare quali fossero le istanze che richiedevano l’implementazione di un’euristica per la loro risoluzione. Inoltre è stato effettuato un confronto dei risultati ottenuti con due diversi solver di ottimizzazione da cui è emersa una risoluzione più rapida con l’utilizzo di Cplex. I risultati ottenuti con l’implementazione della mateuristica hanno riportato sul modello notevoli miglioramenti in termini di tempi di calcolo mentre l’algoritmo di miglioramento della soluzione multi-start ha permesso una riduzione del gap della funzione obiettivo rispetto al suo valore ottimale. Questi riscontri permettono di confermare la competitività dell’algoritmo sviluppato rispetto ad altri modelli già presenti come il Tabu Search che richiedono modellizzazioni più complesse. Il computer utilizzato per la risoluzione del modello matematico è un HP core i5-3317U, 1,7 GHZ, con 8 GB di memoria RAM, mentre i solver di ottimizzazione impiegati sono stati Xpress IVE e Cplex.