Riassunto analitico
Ogni anno le università si trovano a dover affrontare il problema non banale della pianificazione dell'orario, ossia l'assegnazione delle lezioni appartenenti a diversi corsi a delle aule in determinati giorni ed orari. Creare un orario privo di sovrapposizioni ed in grado di soddisfare le esigenze di studenti e docenti è un'impresa che si rivela essere tutt'altro che banale: il problema del timetabling universitario rientra infatti nella categoria dei problemi NP hard, classe di problemi particolarmente difficili da risolvere. Ad oggi, nella maggior parte dei casi, l'orario viene definito dal personale di ateneo dopo ingenti sforzi di tempo e di risorse; l'assenza di un modello matematico di riferimento rende tuttavia difficile anche solo stabilire quanto la soluzione ottenuta sia buona o di quanto differisca dalla soluzione ottima del problema. Questo lavoro di tesi si pone un duplice obiettivo: analizzare e formalizzare il problema della pianificazione dell'orario, con particolare attenzione al sistema universitario italiano, attraverso un modello di programmazione lineare intera, e proporre un algoritmo basato su tecniche metaeuristiche per la risoluzione di problemi reali di grandi dimensioni.
|