Metodi di ottimizzazione delle risorse per la pianificazione didattica = Resource optimization methods for didactic plannig

L’obiettivo di questa tesi è modellare la pianificazione dell’orario delle lezioni di un ateneo come un problema di ottimizzazione. Il caso di studio considerato è la pianificazione dell’orario di circa 200 insegnamenti tra quelli erogati dai collegi di ICM (Informatica, Cinema e Meccatronica) ed ETF (Elettronica Telecomunicazioni e Fisica) su diversi corsi di laurea del Politecnico di Torino. La modellazione ha considerato diversi tipi di vincoli. Sono stati considerati i vincoli strutturali, quali aule e laboratori disponibili in quantità limitata e con capienze note, i vincoli dati dai piani di studio, ad esempio l’impossibilità di sovrapporre insegnamenti obbligatori per un dato orientamento, vincoli dettati dalla disponibilità dei docenti che possono essere coinvolti in più insegnamenti, e vincoli dettati dalle necessità degli studenti di seguire troppe ore di lezione consecutive. Alcuni di questi vincoli sono stati ritenuti forti (hard constraint) . Ad esempio, non è possibile pianificare un orario che usi più aule di quelle presenti in ateneo, non è possibile che un docente insegni contemporaneamente per più insegnamenti e non è possibile soovrappoorre insegnamenti obbligatori. Altri vincoli sono stati considerati deboli (soft constraint), soddisfare o non soddisfare i soft constraint definire introduce penalità o dei bonus. L’obiettivo della modellazione è stato sviluppare un software che supporti nella pianificazione dell’orario usando l’ottimizzazione matematica. L’output di tale software è la versione migliore possibile dell’orario. L’obiettivo dell’ottimizzazione implementata è soddisfare tutte le hard constraint e massimizzare una funzione obiettivo costruita a partire da tutte le soft constraint. Durante la prima fase di questa tesi sono stati descritti formalmente i requisiti per ottenere un modello rigoroso del problema e identificare gli input da collezionare. È seguito uno studio approfondito delle tecnologie e della letteratura informatica per trovare i modelli di ottimizzazione e gli approcci migliori. Risultato di tale ricerca è stata l’individuazione di due problemi validi per quello in esame: “Maximum satisfiability problem” (MaxSMT) e “Integer linear programming” (ILP). In seguito si sono scelti i solver che risolvono tali problemi: Z3 per MaxSMT e IBM CPLEX per ILP. Successivamente, è stato sviluppato un modello matemativo grado di rappresentare coerentemente e fedelmente il problema di ottimizzazione e tutte le tipologie di vincoli emersi durante l’analisi dei requisti. L’ultima fase è l’implementazione del software. Esso include moduli in grado di leggere le informazioni in input (insegnamenti, piani di studio, docenti, aule), di ottenere sotto forma di equazioni matematiche tutti i vincoli e di generare il programma di ottimizzazione. Dopo aver risolto il problema, altri moduli si occupano di salvare l’output per cui è stato sviluppato su un DB sia per visualizzazione che stampa dell’orario generato. Infine con il recepimento dei dati ufficiali si è proceduto alla loro validazione iniziale ed ai successivi tentativi di estrazione di una soluzione valida sfruttando un nodo di calcolo messo a disposizione dall’area IT del nostro ateneo. Concludono la Tesi alcuni spunti per una futura espansione del modello e di miglioramento del software oltre ai manuali d’uso del software che mostrano tutte le opzioni che è possibile configurare ed i vincoli che è possibile aggiungere oltre ad indicare come espandere lo strumento con nuove funzioni.