Examination timetabling assigns examinations to a given number of time slots so that there are no conflicts. A conflict occurs if a student has to take more than one examination at the same time, or when the number of students that must take an exam exceeds the capacity of the classroom assigned. The objective is to minimize penalties from proximity constraints. We present new algorithms based on local search and report on an extensive experimental study. We consider also a variant where the concern is to produce conflict-free timetables minimizing the number of time slots, regardless of how close exams appear in the schedule. The algorithms proposed also manage the trade-off between the two objective functions and produce the best results on several standard benchmark instances, compared to the best existing algorithms.

Novel Local-Search-Based Approaches to University Examination Timetabling / M., Caramia; P., Dell'Olmo; Italiano, G. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - 20:1(2008), pp. 86-99. [10.1287/ijoc.l070.0220]

Novel Local-Search-Based Approaches to University Examination Timetabling

ITALIANO G
2008

Abstract

Examination timetabling assigns examinations to a given number of time slots so that there are no conflicts. A conflict occurs if a student has to take more than one examination at the same time, or when the number of students that must take an exam exceeds the capacity of the classroom assigned. The objective is to minimize penalties from proximity constraints. We present new algorithms based on local search and report on an extensive experimental study. We consider also a variant where the concern is to produce conflict-free timetables minimizing the number of time slots, regardless of how close exams appear in the schedule. The algorithms proposed also manage the trade-off between the two objective functions and produce the best results on several standard benchmark instances, compared to the best existing algorithms.
Novel Local-Search-Based Approaches to University Examination Timetabling / M., Caramia; P., Dell'Olmo; Italiano, G. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - 20:1(2008), pp. 86-99. [10.1287/ijoc.l070.0220]
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/199801
Citazioni
  • Scopus 47
  • ???jsp.display-item.citation.isi??? 39
social impact