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

Mats Carlsson, Sara Ceschia, Luca Di Gaspero, Rasmus Ørnstrup Mikkelsen*, Andrea Schaerf, Thomas Jacob Riis Stidsen

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

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.

Original languageEnglish
JournalJournal of Scheduling
Volume26
Issue number4
Pages (from-to)353-367
Number of pages15
ISSN1094-6136
DOIs
Publication statusPublished - Aug 2023

Keywords

  • Constraint programming
  • Examination timetabling
  • Integer programming
  • Simulated annealing

Fingerprint

Dive into the research topics of 'Exact and metaheuristic methods for a real-world examination timetabling problem'. Together they form a unique fingerprint.

Cite this