Disruptions in timetables: a case study at Universidade de Lisboa
- PDF / 836,104 Bytes
- 14 Pages / 595.276 x 790.866 pts Page_size
- 30 Downloads / 170 Views
Disruptions in timetables: a case study at Universidade de Lisboa Alexandre Lemos1
· Pedro T. Monteiro1
· Inês Lynce1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Solving university course timetabling problems is a large and complex task. Moreover, every new academic term, a new timetable is likely to be scheduled due to disruptions (e.g., changes in teacher-lecture allocation). Nevertheless, the university infrastructure, the overall curricular plans, and the number of students/teachers is still very similar in consecutive terms. For this reason, a timetable does not need to be always scheduled from scratch since it can produce a completely different solution from the previous one, thus creating undesirable changes for many actors. This paper addresses the Minimal Perturbation Problem (MPP) in university course timetabling. Given a set of disruptions that make a timetable no longer feasible, a solution to the MPP is the closest new feasible timetable with respect to the original timetable. We propose and analyze two different integer programming models to encode the MPP. To validate the proposed models, disruptions are randomly generated based on the probability distributions learned from the history of timetables over the last five years in the Instituto Superior Técnico (IST) the engineering school from Universidade de Lisboa. Overall, our models, combined with an incremental approach, are shown to be able to efficiently solve all problem instances. Keywords Minimal perturbation problem · University course timetabling · Disruption · Integer programming
1 Introduction University course timetabling problems with real-world scenarios are one of the major open challenges in this sub-field (McCollum 2006; Vrielink et al. 2019). Given a set of constraints a solution to a university course timetabling problem is an assignment of all lectures to suitable rooms and time slots in such a way that all the constraints are satisfied.
The authors would like to thank the reviewers for their helpful comments and suggestions that contributed to an improved manuscript. This work was supported by national funds through Fundação para a Ciência e a Tecnologia (FCT) with reference SFRH/BSAB/143643/2019 (sabbatical Grant), SFRH/BD/143212/2019 (PhD Grant), DSAIPA/AI/0044/2018 (project Data2help) and UIDB/50021/2020 (INESC-ID multi-annual funding).
B
Alexandre Lemos [email protected] Pedro T. Monteiro [email protected] Inês Lynce [email protected]
1
Instituto Superior Técnico, Universidade de Lisboa INESC-ID, Rua Alves Redol, 9, 1000-029 Lisbon, Portugal
University course timetabling problems are known to be NPcomplete (Even et al. 1976). Every semester a new timetable needs to be created. At Instituto Superior Técnico (IST), the number of changes between the timetables of consecutive academic terms is small. These changes can be of different types: either constraints are added/changed, or the domain of a variable is changed. These changes may
Data Loading...
