Metodi di
Ottimizzazione
University Timetabling
Bombardi Fabio, Crociani Michele
Scopo

10/12/2002
Realizzazione dell'orario
universitario: assegnare l'orario
d'inizio e fine e un'aula
adeguata a ciascuna lezione di
ogni corso
Cesena - Metodi di Ottimizzazione 2002
2
Problema…

Soddisfare:
i vincoli materiali
(aule, proiettori, …)
 le condizioni relative al modo in
cui ciascuna università vuole
organizzare il suo insegnamento
(numero di ore, giorni, …)

10/12/2002
Cesena - Metodi di Ottimizzazione 2002
3
…ma

La difficoltà principale è relativa
alla dimensione del problema:

10/12/2002
Esso coinvolge un gran numero di
studenti, di insegnanti, corsi e
aule, legati in diversi modi
attraverso gli obiettivi e i vincoli.
Cesena - Metodi di Ottimizzazione 2002
4
Oggi


10/12/2002
L’orario universitario viene fatto
manualmente
Viene impiegato molto tempo e
spesso non si trova subito una
soluzione adeguata
Cesena - Metodi di Ottimizzazione 2002
5
Soluzione

10/12/2002
Creare un software che
permetta la realizzazione
automatica dell’orario.
Cesena - Metodi di Ottimizzazione 2002
6
Tecniche

Sono state utilizzate molte
tecniche di ricerca locale:
Tabu Search
 Simulated Annealing
 Algoritmi Genetici


Ma…se il problema non è ampio

10/12/2002
È possibile ottenere una soluzione
ottima attraverso un modello LP
Cesena - Metodi di Ottimizzazione 2002
7
Scelta




10/12/2002
Modello ILP in MPL
Soluzione Ottima da CPLEX
Database MsAccess
GUI: maschere di MsAccess
Cesena - Metodi di Ottimizzazione 2002
8
Modello: dati







10/12/2002
T l’insieme degli insegnanti
C l’insieme dei corsi
P l’insieme dei periodi
Rt l’insieme dei tipi di aule
D l’insieme dei giorni
Cl l’isieme delle classi
CT l’insieme dei corsi associati
agli insegnanti
Cesena - Metodi di Ottimizzazione 2002
9
Modello: dati (II)






10/12/2002
CC l’insieme dei corsi associati alle classi
DP l’insieme dei periodi nei vari giorni
RRT l’insieme delle richieste di un tipo di
aula r da parte di un corso
UT l’insieme dei periodi di indisponibilità
degli insegnanti
WP il vettore dei periodi totali da fare alla
settimana per ogni corso
NRT il vettore della disponibilità di ogni
tipo r di aula non binario
Cesena - Metodi di Ottimizzazione 2002
10
Modello: variabili decisionali
xcp =
1

0
a seconda che il corso c
inizi nel periodo p, binaria.
10/12/2002
Cesena - Metodi di Ottimizzazione 2002
11
Modello: Vincoli
1. ogni corso deve essere svolto in x periodi la
settimana:
cl  Cl , c  CC
x
cp
WPc
p
2. ogni insegnante non può svolgere più di una
lezione nello stesso periodo:
p  P, t  T ,
x
cCT
10/12/2002
cp
1
Cesena - Metodi di Ottimizzazione 2002
12
Modello: Vincoli (II)
3. non ci possono essere per ogni classe due
corsi da frequentare nello stesso periodo:
p  P, cl  Cl ,
x
cCC
cp
1
4. non ci possono essere più di due corsi uguali
dello stesso anno nello stesso giorno
(stesso corso per anni diversi ha nome diverso):
c  C , d  D,
x
d DP
10/12/2002
cp
1
Cesena - Metodi di Ottimizzazione 2002
13
Modello: Vincoli (III)
5. la richiesta di aule r non deve superare
il numero di aule r disponibili:
d  D, r  Rt ,
x
cp
pDP , cRRT
 NRTdr
6. le richieste non devono superare il
numero totale di aule:
d  D,

pDP , c
10/12/2002
xcp   NRTd
r
Cesena - Metodi di Ottimizzazione 2002
14
Modello: Vincoli (IV)
7. se un professore non è disponibile in un dato
periodo in esso non ci deve essere nessun
corso associato a quel professore:
p  P, t  UT ,
x
cp
0
c
10/12/2002
Cesena - Metodi di Ottimizzazione 2002
15
Funzione Obiettivo

Realizzabilità:


10/12/2002
Min 0
Abbiamo minimizzato 0 (ovvio)
per vedere se almeno tutti i
vincoli venivano soddisfatti
Cesena - Metodi di Ottimizzazione 2002
16