A parallelized matheuristic for the International Timetabling Competition 2019

The International Timetabling Competition 2019 (ITC 2019) presents a novel and generalized university timetabling problem composed of traditional class time and room assignment and student sectioning. In this paper, we present a parallelized matheuristic tailored to the ITC 2019 problem. The matheur...

Full description

Saved in:
Bibliographic Details
Published in:Journal of scheduling 2022-08, Vol.25 (4), p.429-452
Main Authors: Mikkelsen, Rasmus Ø., Holm, Dennis S.
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Business and Management
Calculus of Variations and Optimal Control
Optimization
Colleges & universities
Competition
Integer programming
Linear programming
Lower bounds
Mixed integer
Operations Research/Decision Theory
Optimization
Production methods
Supply Chain Management
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The International Timetabling Competition 2019 (ITC 2019) presents a novel and generalized university timetabling problem composed of traditional class time and room assignment and student sectioning. In this paper, we present a parallelized matheuristic tailored to the ITC 2019 problem. The matheuristic is composed of multiple methods using the graph-based mixed-integer programming (MIP) model defined for the ITC 2019 problem by Holm et al. (A graph-based MIP formulation of the International Timetabling Competition 2019. J Sched, 2022. https://doi.org/10.1007/s10951-022-00724-y ). We detail all methods included in the parallelized matheuristic and the collaboration between them. The parallelized matheuristic includes two methods for producing initial solutions and uses a fix-and-optimize matheuristic to improve solutions. Additionally, the method uses the full MIP model to calculate lower bounds. We describe how the methods perform collaboratively through solution sharing, and a diversification scheme invoked when the search stagnates. Furthermore, we explain how we decompose the problem for instances with a large number of students. We evaluate components of the parallelized matheuristic using the 30 benchmark instances of the ITC 2019. The complete parallelized matheuristic performs well, even solving some instances to proven optimality. The presented method is the winning algorithm of the competition, further demonstrating its quality.
ISSN:1094-6136
1099-1425
DOI:10.1007/s10951-022-00728-8