Un'applicazione web per il benchmarking di un problema di ottimizzazione

2 Introduzione al problema
Figura 1.1: Massimo e minimo nella funzione obiettivo
Mathematical programming Stochastic process Statistical methods
Calculus Methods Statistical decision theory Regression analysis
Calculus of variations Markov process Cluster analysis,
pattern recognition
Nonlinear programming Queueing theory Design of experiments
Geometric programming Renewal theory Discriminate analysis
Quadratic programming Simulation methods
Linear programming Reliability theory
Dynamic programming
Integer programming
Stochastic programming
Separable programming
Multiobjective programming
Network methods:
CPM & PERT
Game theory
Simulated annealing
Genetic algorithms
Neural networks
Tabella 1.1: Riepilogo delle principali tecniche e aree di ricerca del settore
1.2 Definizione del problema 3
I problemi di schedulazione (scheduling) trattano l’allocazione di risorse nel tempo, fina-
lizzate allo svolgimento di determinate funzioni: l’esempio classico e` quello del job-shop
industriale, in cui m macchine devono svolgere j attivita` in un determinato periodo. I pro-
blemi di orario (timetabling), invece, riguardano la sistemazione, soggetta ad una serie di
vincoli, di un evento (esame, lezione, ...) in un ristretto numero di slot temporali.
Questa classe di problemi di ottimizzazione e` considerata tra le piu` impegnative che la Ri-
cerca Operativa e l’intelligenza artificiale trattano: le tematiche coinvolte sono, dunque, la
pianificazione temporale e l’ottimizzazione combinatoria, e, per la loro risoluzione, alla ricer-
ca semplice si deve spesso unire quella euristica, cioe` un metodo di approccio alla soluzione
dei problemi che non segue un percorso codificato, ma che si affida all’intuito e allo stato
temporaneo delle circostanze, al fine di generare nuova conoscenza. e` opposto al procedi-
mento algoritmico. In informatica si definisce euristico il lavoro di un software che non opera
meccanicamente, ma utilizza invece una tecnica virtualmente creativa, cioe` che non si limita
ad analizzare i dati secondo confronto di dati noti, ma prova a simularne il comportamento.
Esempi di software euristici sono alcuni moderni antivirus o alcuni programmi contro il phi-
shing informatico, che sono in grado, in taluni casi, di individuare comportamenti pericolosi
anche in virus non ancora classificati, per i quali l’analisi per confronto sarebbe inutile.
I problemi di schedulazione sono considerati cos`ı complessi per svariati motivi:
• sono problemi NP-completi, cioe` che ammettono algoritmi non deterministici per la
determinazione di una soluzione verificabile [Garey & Johnson, 1979];
• l’utilizzo di tecniche euristiche avanzate non garantisce il raggiungimento della solu-
zione ottima;
• particolari istanze dei problemi possono essere complicate dalla presenza di alcuni vin-
coli, possibili solo nell’ambito della schedulazione dell’orario, che rendono inapplicabili
alcuni algoritmi tradizionali di risoluzione;
• i problemi ottenuti da casi reali possono contenere vincoli non facilmente rappresen-
tabili nei modelli studiati.
Con Course Timetabling (CTT) si identificano tutti i problemi di schedulazione delle lezioni
dei corsi universitari, con un numero specificato di aule e periodi didattici disponibili, e con
vincoli relativi a disponibilita` ed aule. Il CTT e` una classe di problemi ampiamente studiata
e si presta a ricevere contributi sempre nuovi in quanto ogni universita` ha le proprie carat-
teristiche e puo` presentare nuove formulazioni dei problemi. Il Curriculum-Based Course
Timetabling (CB-CTT), qui analizzato, riguarda i problemi di schedulazione delle lezioni
universitarie basate su curricula.
1.2 Definizione del problema
Il modello del problema e` costituito da diverse entita` di base:
• giorni, periodi e finestre temporali (timeslot) sono descritti nella Figura 1.2;
• ogni corso ha un numero prefissato di lezioni da schedulare nei diversi periodi, un
insegnante ed un certo numero di studenti frequentanti. Inoltre ha un intervallo di
giorni minimo e massimo in cui le lezioni possono essere distribuite, e un certo numero
di vincoli sui periodi disponibili;
4 Introduzione al problema
Figura 1.2: Esempio di tabella oraria contenente 5 giorni, 5 timeslot e 5x5=25 periodi
• ogni aula ha una capacita` massima, un indicatore dell’edificio in cui si trova e dei
vincoli sulla disponibilita` ad ospitare alcuni corsi in determinati periodi;
• un curriculum e` costituito da un gruppo di corsi, solitamente appartenenti allo stesso
ambito didattico, ma questo aspetto esula dal modello generale del problema.
Per la validazione di una soluzione sono considerate diverse componenti di costo. Le
violazioni ai vincoli fissati possono essere hard o soft. Sono hard :
• la mancata schedulazione di alcuni corsi (lectures);
• le sovrapposizioni di lezioni tra corsi dello stesso curriculum o tenuti dallo stesso
docente (conflicts);
• le sovrapposizioni di lezioni nella stessa aula e nello stesso periodo (room occupancy);
• le lezioni schedulate nei periodi dei corsi non disponibili (availability).
Sono, invece, violazioni soft :
• il superamento della capienza massima dell’aula in cui il corso e` schedulato (room
capacity);
• il mancato rispetto dell’intervallo minimo di giorni in cui le lezioni devono essere
distribuite (min working days);
• la mancata adiacenza temporale delle lezioni relative a corsi dello stesso curriculum
all’interno di una giornata (isolated lectures);
• le ore libere tra lezioni dello stesso curriculum schedulate nello stesso giorno (windows);
• le lezioni di un corso che si svolgono in aule diverse (room stability);
1.3 International Timetabling Competition 5
Problem Formulation: UD1 UD2 UD3 UD4 UD5
Cost Component
Lectures H H H H H
Conflicts H H H H H
RoomOccupancy H H H H H
Availability H H H H H
RoomCapacity 1 1 1 1 1
MinWorkingDays 5 5 — 1 5
IsolatedLectures 1 2 — — 1
Windows — — 4 1 2
RoomStability — 1 — — —
StudentMinMaxLoad — — 2 1 2
TravelDistance — — — — 2
RoomSuitability — — 3 H —
DoubleLectures — — — 1 —
Tabella 1.2: Descrizione delle formulazioni del problema
• il superamento del numero massimo di lezioni giornaliere che ogni curriculum ha
(student load);
• il mancato tempo per lo spostamento degli studenti, se ci sono lezioni adiacenti in aule
appartenenti ad edifici diversi (travel distance);
• le lezioni di alcuni corsi schedulate nelle aule non disponibili ad ospitare tali corsi, a
causa ad esempio della carenza di attrezzature (room suitability);
• la mancata schedulazione, dove richiesto, di alcuni corsi in slot consecutivi e nella
stessa aula (double lectures).
Con il termine formulazione si intende l’insieme di parametri utilizzati per la validazione
delle soluzioni. Ovviamente i pesi e i costi assegnati alle varie violazioni sono totalmente
arbitrari e possono essere oggetto di discussione. Oltre alla formulazione 2 utilizzata nella
competizione (UD2), vengono offerte altre 4 formulazioni che si ritiene coprano una vasta
gamma di possibili varianti; l’aggiunta di altre e` sempre e comunque possibile, a seconda
di particolari esigenze che si vogliono soddisfare da parte della comunita` di ricercatori. La
tabella 1.2 ([2]) riassume le caratteristiche delle varie formulazioni: “H” indica una violazione
di tipo hard, un valore numerico indica la componente di costo associata alla violazione
soft, mentre il trattino significa che la violazione non e` contemplata nella formulazione
corrispondente.
1.3 International Timetabling Competition
La formazione degli orari e` una delle attivita` che richiede piu` risorse nell’ambito universi-
tario: l’International Timetabling Competition (ITC, Figura 1.3) e` nata con l’obiettivo di
creare un terreno di confronto comune per il benchmarking delle tecniche e delle soluzioni
a questo problema, in modo da coinvolgere il maggior numero possibile di utenti e fornire
loro nuovi approcci per la risoluzione delle loro problematiche. La competizione si propone
anche lo scopo, non meno importante, di ridurre il gap esistente tra la ricerca e l’applicazione
6 Introduzione al problema
Figura 1.3: Il logo dell’ITC
pratica di una disciplina come la Ricerca Operativa: per fare questo, si cerca di aumentare la
complessita` dei problemi andando a considerare alcuni aspetti di casi reali precedentemente
non trattati.
Il problema analizzato in questo elaborato e` detto Curriculum-Based Course Timetabling
(CB-CTT), e riguarda la terza traccia dell’ITC versione 2007. La differenza principale rispet-
to agli altri casi riguarda l’origine dei conflitti possibili durante il processo di determinazione
degli orari, che deriva dai curricula in cui sono raggruppati i vari corsi, e non dalle iscrizioni
effettuate dagli studenti. Questa scelta deriva dal fatto che il sistema universitario italiano,
e molti di quelli europei, sono strutturati in base ai curricula: non a caso i dataset utilizzati
per questa parte della competizione sono stati presi dall’Universita` di Udine.
La formulazione del problema e` stata creata con l’obiettivo di semplificare il caso reale e di
coinvolgere il maggior numero di ricercatori; nonostante queste intenzioni, alcuni partecipan-
ti hanno criticato la formulazione proposta e la scelta delle componenti di costo. Per questo
motivo sono state aggiunte delle formulazioni, in modo da cercare di coprire maggiormente
le possibilita` che emergono dai casi reali: ovviamente la complessita` di questa classe di pro-
blemi sta alla base di queste critiche, che comunque, se giustificate, costituiscono sempre un
ottimo feedback per la comunita` e per lo sviluppo della ricerca.
L’ITC-2007 si e` svolta dal primo agosto 2007 al 25 gennaio 2008; i partecipanti dovevano im-
plementare un algoritmo di risoluzione, usando un linguaggio di programmazione a piacere,
che desse come output un orario, il quale doveva possibilmente soddisfare tutti i vincoli hard
e minimizzare il costo associato a quelli soft. Gli algoritmi potevano essere sia deterministici
che stocastici: importante e` la loro compatibilita` con tutte le istanze e formulazioni della
competizione, e il massimo tempo di timeout del programma, entro il quale dovevano ne-
cessariamente generare l’output. Un interessante sviluppo per gli scenari competitivi futuri
potrebbe proprio essere un sistema di punteggio che sia trade-off dell’output ottenuto e del
running time dell’algoritmo.
Le istanze della competizione sono 21; esisteva certamente una soluzione ammissibile per
ognuna (cioe` che non violasse i vincoli hard), mentre i valori ottimi dei costi soft (lower
bound) non erano noti, e sono tuttora disponibili solo in parte nel sito.
Rispetto all’edizione 2002 dell’ITC, il focus sulla ricerca di problemi reali su cui incentrare
la competizione e` stato accentuato dal fatto che sono state introdotte 3 tracce in modo da
cercare di toccare la maggior parte delle tematiche legate alla schedulazione dell’orario in
ambiente scolastico. Inoltre il fatto di accettare comunque utenti che hanno fornito solu-
zioni valide solo per alcune delle istanze proposte ha allargato il campo dei partecipanti e
cio` rappresenta una spinta decisiva verso il confronto e la crescita della comunita`, facilitata
dall’aumento di tali contributi, che rapprsentano a loro volta i presupposti sui quali l’ITC e`
stata costruita.
Le formulazioni provenienti dall’Universita` di Udine sono state semplificate di alcune va-
rianti, quali: