We propose a Simulated Annealing approach for the Examination Timetabling problem, in the classical uncapacitated formulation of Carter et al. (1996). Our solver is based on a novel combination of many neighborhoods and a principled tuning procedure performed on artificial training instances. The experimental results on real- world benchmarks show that our solver is able to improve upon all state-of-the-art search methods from the literature on most instances, running time being equal. In addition, we performed an ablation analysis, so as to identify the most important neighborhoods. Finally, we propose a novel dataset obtained by translating real- world instances for other examination timetabling formulations. Instances and solutions, along with our source code, are available on the web for inspection and future comparison.

Two-stage multi-neighborhood simulated annealing for uncapacitated examination timetabling

Ruggero Bellio
Primo
;
Sara Ceschia
Secondo
;
Luca Di Gaspero
Penultimo
;
Andrea Schaerf
Ultimo
2021-01-01

Abstract

We propose a Simulated Annealing approach for the Examination Timetabling problem, in the classical uncapacitated formulation of Carter et al. (1996). Our solver is based on a novel combination of many neighborhoods and a principled tuning procedure performed on artificial training instances. The experimental results on real- world benchmarks show that our solver is able to improve upon all state-of-the-art search methods from the literature on most instances, running time being equal. In addition, we performed an ablation analysis, so as to identify the most important neighborhoods. Finally, we propose a novel dataset obtained by translating real- world instances for other examination timetabling formulations. Instances and solutions, along with our source code, are available on the web for inspection and future comparison.
File in questo prodotto:
File Dimensione Formato  
COR2021.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Licenza: Non pubblico
Dimensione 590.13 kB
Formato Adobe PDF
590.13 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: https://hdl.handle.net/11390/1205152
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 5
social impact