|
|
|
|
La gestione dell’informazione
nell’azienda
Schedulazione
intelligente di attivitŕ in presenza di risorse limitate e matching
stabile ed efficiente tra domanda e offerta
Dott.ssa
Maria Silvia Pini
Schedulazione di corsi aziendali con vincoli e preferenze
Descrizione
o Il problema dell’orario e’ un problema combinatorio
che consiste nell’assegnazione settimanale delle lezioni di un insieme di corsi
ai periodi e alle aule disponibili. Questa assegnazione deve soddisfare sia i
vincoli dovuti alla capienza delle aule, alla sovrapposizione delle lezioni e
alla mutualitŕ degli insegnamenti, sia le preferenze dei docenti circa le fasce
orarie in cui tenere le lezioni.
o Il problema dell’orario, in tutte le sue varianti
interessanti in pratica, e’ un problema cosiddetto NP-completo,
cioe’ un problema difficile da risolvere. In pratica,
questo significa che non e’ possibile trovare un algoritmo che lo risolva e il
cui tempo sia limitato da un polinomio nella grandezza dell’input. Per ovviare
a questo problema, spesso vengono usati algoritmi approssimati, che ottengono
soluzioni non ottime ma comunque buone e riescono ad avere un tempo ragionevole
in molti casi pratici. Dall’analisi
degli algoritmi esistenti e delle loro valutazioni sperimentali si evince che
c’e’ uno schema di algoritmo che e’ il migliore in tutti questi contesti,
quindi proponiamo di usarlo.
Articoli scientifici
o
R. Cipriano, L. Di Gaspero,
and A. Dovier. Hybrid Approaches
for Rostering: a Case Study in the Integration of
Constraint Programming and Local Search. Proc. 3rd International Workshop
on Hybrid Metaheuristics. Volume 4030 of Lecture
Notes in Computer Science. Springer-Verlag, 2006.
o
L. Di Gaspero and
A. Schaerf. Il
problema della generazione automatica dell’orario delle lezioni: teoria e
pratica. Intelligenza Artificiale,
1(3):47-54, 2004.
o
Tomas
Muller, ITC2007 solver description: a
hybrid approach. Annals of Operations Research, 172(1): 429-446, 2009.
o
Tomas
Muller, Constraint-based timetabling.
Ph.D. Thesis, Charles University in Pague, 2005.
o
F.
Bacchus and A. Grove. On
The Forward Checking Algorithm. Principles and Practice of Constraint
Programming – CP’95. Volume 976 of
Lecture Notes in Computer Science, 292-309, Springer,
1995.
o
F. Laburthe, N. Jussien. Choco solver documentation. http://choco.mines-nantes.fr, 2011.
Documenti prodotti
o Descrizione
degli algoritmi per il problema dei corsi
o Presentazione
dell’algoritmo per il problema dei corsi
o Presentazione
del risolutore Choco per problemi con vincoli
o Presentazione
dell’algoritmo proposto contenente anche il collegamento con il risolutore di Choco