Lower bounds and compact mathematical formulations for spacing soft constraints for university examination timetabling problems

摘要

The examination timetabling problem (ETT) can be described as a set of exams to be scheduled over an examination session while respecting numerous hard and soft constraints. In this paper we consider the spacing soft constraints that seek to prevent students sitting more than one exam per day. Out of consideration for candidates, these soft constraints often feature in real ETT problems that academic institutions seek to solve. Work on ETT has tended to focus on heuristic approaches, and little effort has gone into developing lower bounds, although both are of practical and theoretical interest. For this study we consider formulations of these soft constraints as defined in the ITC2007 examination timetabling track. In existing mathematical formulations of these spacing soft constraints the number of equations is of the order of the square of the number of exams, and current solvers may face problems at runtime because of their large memory requirement. In this study we present a generic model for computing lower bounds, together with more compact formulations where the number of equations is of the order of the number of exams. Computational results on spacing soft constraints that seek to prevent students sitting more than one exam per day are an improvement on results obtained so far on lower bounds, and our new formulations yield a more compact model that gives better results than those given by existing formulations. (C) 2019 Elsevier Ltd. All rights reserved.