Analisi e confronto di algoritmi euristici per il Resource-Constrained Project Scheduling Problem

Le tecniche di pianificazione e allocazione di risorse all’interno delle attività di un progetto, hanno attratto negli ultimi anni una sempre più crescente attenzione. Questo interesse è stato largamente motivato dalla reale importanza pratica e applicabilità che esse assumono in campo industriale e nel mondo del lavoro, si pensi ad esempio: alla produzione di manufatti a commessa, alla realizzazione di nuovi prodotti o di prototipi, alle grandi opere di costruzione, all’istallazione di impianti industriali, allo sviluppo di nuovi sistemi etc. Sia nel settore della produzione che in quello dei servizi, molte società e organizzazioni hanno una struttura basata su progetto, di conseguenza si può dedurre quanto sia importante una corretta opera di pianificazione e controllo delle fasi di un progetto, per evitare di incorrere in problemi quali superamento del budget stanziato, penali amministrative, perdita di alcune caratteristiche peculiari del progetto stesso. I tre elementi fondamentali per il successo di un progetto sono il tempo, il costo, e la qualità, ma molti operatori del settore sostengono, specialmente in campo industriale che la variabile tempo ha un ruolo predominante. Anche perchè, un progetto la cui durata è in linea con quanto pianificato, permette di rispettare il budget previsionale sulle entrate e molto spesso è sinonimo di corretta gestione della tempistica e delle risorse. Il problema in evidenza in questa tesi, chiamato in letteratura RCPSP( Resource Constrained Project Scheduling Problem) si pone l’obiettivo di minimizzare la durata del progetto in presenza di vincoli sulle risorse e di vincoli di precedenza che ogni attività facente parte del progetto deve rispettare per essere correttamente schedulata. In generale risolvere un problema di RCPSP significa ricercare uno schedule ottimo per le attività di un progetto che soddisfi non solo i vincoli di precedenza, ma che provveda anche ad una corretta allocazione delle risorse disponibili quali: manodopera, materie prime, macchinari, equipaggiamenti, capital budget, etc. La ricerca di una soluzione ottima per le istanze di RCPSP specialmente per i problemi che possono capitare in pratica, è un’operazione intrattabile non appena la dimensione del problema diventa significativa e può impedire di risolvere all’ottimo il problema in tempi ragionevoli. Del resto questo problema fa parte della classe NP-Hard ovvero dei problemi di ottimizzazione più difficili, per convincersi di ciò basta osservare che RCPSP generalizza un problema NP-completo noto con il nome Partition. Per ovviare a questa limitazione si ricorre ad approcci euristici che spesso costringono a sacrificare la qualità della soluzione a scapito di tempi di esecuzione accettabili. Normalmente le tecniche euristiche sono algoritmi con una bassa complessità che non garantiscono di ottenere la soluzione ottima, ma in generale sono in grado di fornire una buona soluzione ammissibile per il problema.Lo scopo che si prefigge questa tesi è quello di confrontare e valutare un approccio euristico al problema del RCPSP, gli algoritmi trattati maggiormente in questo lavoro sono di tipo greedy-like e costruiscono lo schedule del progetto iterativamente in conformità a una regola di priorità e a un determinato criterio di assegnazione degli istanti di tempo alle attività selezionate. Il lavoro di tesi riguarda, in primo luogo, proprio lo studio e l’implementazione di algoritmi euristici quali Greedy Seriale e Greedy Parallelo per verificare il comportamento e le variazioni rispetto all’ottimo che si hanno in relazione a una regola di priorità prescelta. In seguito, determinata la regola migliore tra quelle testate, lo studio è esteso all’intorno della soluzione precedentemente determinata mediante l’utilizzo di algoritmi meta-euristici. Gli algoritmi meta-euristici che sono oggetto di questa tesi sono: il simulated annealing, il tabu search e gli algoritmi genetici. Queste tecniche sono state implementate in Matlab, e sono state testate sul campione di istanze. L’oggetto della ricerca è quello di confrontare e valutare il comportamento di questi algoritmi meta-euristici in relazione all’ottimo in modo cosi da individuare quale dei seguenti approcci ha una migliore performance in termini di numero di iterazioni, tempo di calcolo e qualità della soluzione trovata. Inoltre si vuole determinare l’entità del miglioramento della soluzione fornita da questi approcci rispetto alla soluzione iniziale individuata con un algoritmo greedy. Addentrandoci nello specifico del lavoro, lo studio è stato svolto su un campione di 200 istanze di RCPSP caratterizzate da un numero variabile di attività o job che non possono essere interrotte( non-preemption) e che hanno un certo fabbisogno di risorse. Ogni istanza è rappresentata tramite un grafo aciclico AoN dove le attività rappresentate dai nodi del grafo sono topologicamente interconnesse.