Minimal Perturbation in University Timetabling with Maximum Satisfiability

EasyChair Preprint 2821

Abstract

Every new academic year, scheduling new timetables due to disruptions is a major problem for universities. However, computing a new timetable from scratch may be unnecessarily expensive. Furthermore, this process may produce a significantly different timetable which in many cases is undesirable for all parties involved. For this reason, we aim to find a new feasible timetable while minimizing the number of perturbations to the original disrupted timetable.

The contribution of this paper is a maximum satisfiability (MaxSAT) encoding to solve large and complex university timetabling problem instances which can be subject to disruptions. To validate the MaxSAT encoding, we evaluate university timetabling real-world instances from the International Timetabling Competition (ITC) 2019. We use the originally found solutions as a starting point to evaluate the capacity of the proposed MaxSAT encoding to find a new solution with minimal perturbation. Overall, our model is able to efficiently solve the disrupted instances.

Keyphrases: MaxSAT, Minimal Perturbation, university timetabling

@booklet{EasyChair:2821,
  author    = {Alexandre Lemos and Pedro T. Monteiro and Inês Lynce},
  title     = {Minimal Perturbation in University Timetabling with Maximum Satisfiability},
  howpublished = {EasyChair Preprint 2821},
  year      = {EasyChair, 2020}}