Strip packing bidimensionale con items deformabili con applicazione allo scheduling di task in ambito HPC

La tesi presenta un nuovo problema di ottimizzazione combinatoria, noto come strip packing bidimensionale con elementi deformabili, che modella alcune applicazioni tipiche dello scheduling di task in contesti di High Performance Computing. Per il problema in esame vengono proposte diverse formulazione di programmazione lineare intera e alcuni algoritmi euristici e metaeuristici di soluzione. Tutti gli algoritmi sono stati implementati in codici di calcolo e sono stati testati su un ampio benchmark di istanze derivanti da problemi test della letteratura, al fine di valutare le prestazioni, in termini di qualità della soluzione e tempo di calcolo, dei diversi approcci. L'analisi sperimentale condotta mostra che gli algoritmi proposti sono in grado di determinare delle soluzioni ottime o quasi ottime in tempi di calcolo compatibili con l'applicazione reale.