Decomposition of university course timetabling

Britta Herres () and Heinz Schmitz ()
Additional contact information
Britta Herres: Hochschule Trier
Heinz Schmitz: Hochschule Trier

Annals of Operations Research, 2021, vol. 302, issue 2, No 5, 405-423

Abstract: Abstract Suppose we like to find non-overlapping periods for a set of events which may have multiple teachers assigned, is this easy or hard in terms of complexity? Or assume that only a single teacher is fixed per event, but we like to allocate rooms and periods simultaneously. What if a single teacher and a room is already given and we look for periods alone? And how do requests of teachers for specific rooms or additional student conflicts change the computational complexities of these questions from university course timetabling (UCT)? We provide a complete hard/easy-list of all UCT subproblems derived from a typical set of hard constraints. We obtain this list with a systematic study of the fine structure of UCT in terms of complexity w.r.t. the order in which rooms, periods and teachers are assigned to events. These kind of subproblems appear in practice when some entities in a timetable are fixed while the assignments of others are (re-)computed, and they also appear as necessary conditions for the existence of feasible timetables. Moreover, we identify which of the seemingly different subproblems are essentially the same computational tasks by reducing them to the same bipartite assignment problem, and we discuss some variations of constraints.

Keywords: Foundations of university course timetabling; Complexity analysis; Decomposition approach; Bipartite assignment problems (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-019-03382-0 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:annopr:v:302:y:2021:i:2:d:10.1007_s10479-019-03382-0

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

DOI: 10.1007/s10479-019-03382-0

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

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