Alexander Hübner | 05.04.2022
Creating good course timetables at a university is a challenging combinatorial optimization problem that has received considerable interest in the optimization and operations research literature (cf. [1]). In principle, the tasks consists of assigning weekly lectures to time slots and rooms while respecting a number of hard constraints. For instance, a lecturer can teach at most one lecture at a time, no two lectures can take place in the same room at the same time and no two lectures of the same curriculum must be scheduled in parallel. The quality of a solution to the problem (a timetable) can be measured by different quality criteria that are mainly related to the convenience of students and lecturers. Since the problem is computationally hard to solve, many solution approaches are based on (meta-) heuristics, but mixed integer linear programming (MILP) is also applied (see, for example, [2, 3]). Approaches from the literature, however, are most of the time not directly applicable to practical problem instances from a particular university since the specific requirements and constraints on good timetables can differ substantially between universities. Hence, existing solution approaches for one university’s problem usually have to be adapted considerably before they can be used at a different university. The goal of this master’s thesis is to formulate a mathematical model for the specific course timetabling problem at the TUM Campus Straubing for Biotechnology and Sustainability (http://www.cs.tum.de) that includes all relevant constraints of the practical problem. In addition, a comprehensive literature review on university timetabling approaches should be performed. Afterwards, suitable methods from the literature (e.g., heuristics or MILP approaches) should be selected and adapted in order to solve the problem.
The specific tasks to be performed include:
- Collecting and summarizing the relevant literature on optimization approaches to university course timetabling in a comprehensive literature review
- Collecting and summarizing all relevant constraints of the practical planning problem at the TUM Campus Straubing for Biotechnology and Sustainability
- Creating a mixed integer programming (MILP) formulation for the practical planning problem (e.g., based on the models in [2, 3])
- Selecting suitable solution methods and adapting them to the obtained problem formulation
- Implementing the solution methods in a suitable programming language (e.g., Python or OPL)
- Testing the implemented solution methods on example data and analyzing the results
The thesis will be supervised by the Chair of Supply and Value Chain Management (Prof. Dr. Alexan-der Hübner). If you are interested, please send an email to alexander.huebner@tum.de
References
[1] H. Babaei, J. Karimpour, and A. Hadidi, A survey of approaches for university course timetabling problem, Computers & Industrial Engineering 86 (2015), 43–59.
[2] G. Lach and M. E. Lübbecke, Optimal university course timetables and the partial transversal polytope, Proceedings of the 7th International Workshop on Experimental and Efficient Algorithms (WEA), LNCS, vol. 5038, 2008, pp. 235–248.
[3] _____, Curriculum based course timetabling: new solutions to Udine benchmark instances, Annalsof Operations Research 194 (2012), 255–272.