Disruptions in timetables: a case study at Universidade de Lisboa

Alexandre Lemos (), Pedro T. Monteiro () and Inês Lynce ()
Additional contact information
Alexandre Lemos: Universidade de Lisboa INESC-ID
Pedro T. Monteiro: Universidade de Lisboa INESC-ID
Inês Lynce: Universidade de Lisboa INESC-ID

Journal of Scheduling, 2021, vol. 24, issue 1, No 4, 35-48

Abstract: 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 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-020-00666-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:24:y:2021:i:1:d:10.1007_s10951-020-00666-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-020-00666-3

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().