Exact and metaheuristic methods for a real-world examination timetabling problem

Mats Carlsson (), Sara Ceschia (), Luca Gaspero (), Rasmus Ørnstrup Mikkelsen (), Andrea Schaerf () and Thomas Jacob Riis Stidsen ()
Additional contact information
Mats Carlsson: RISE Research Institutes of Sweden
Sara Ceschia: University of Udine
Luca Gaspero: University of Udine
Rasmus Ørnstrup Mikkelsen: Technical University of Denmark
Andrea Schaerf: University of Udine
Thomas Jacob Riis Stidsen: Technical University of Denmark

Journal of Scheduling, 2023, vol. 26, issue 4, No 2, 353-367

Abstract: Abstract We propose a portfolio of exact and metaheuristic methods for the rich examination timetabling problem introduced by Battistutta et al. (in: Hebrard, Musliu (eds) 17th International conference on the integration of constraint programming, artificial intelligence, and operations research (CPAIOR-2020), LNCS, vol 12296. Springer, Berlin, pp 69–81, 2020). The problem includes several real-world features that arise in Italian universities, such as examinations split into two parts, possible requirements of multiple rooms for a single examination, and unavailabilities and preferences for periods and rooms. We developed a CP model encoded in the MiniZinc modeling language and solved it with Gecode, as well as two MIP models solved with Gurobi. The first MIP model is encoded natively and the second one again in MiniZinc. Finally, we extended the metaheuristic method based on simulated annealing of Battistutta et al. by introducing a new neighborhood relation. We compare the different techniques on the real-world instances provided by Battistutta et al., which have been slightly refined by correcting some semantic issues. Finally, we developed a solution checker that is publicly available, together with all instances and solutions, for inspection and future comparisons.

Keywords: Examination timetabling; Constraint programming; Integer programming; Simulated annealing (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-023-00778-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:26:y:2023:i:4:d:10.1007_s10951-023-00778-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-023-00778-6

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().