Resource allocation techniques for planning the teaching timetable

The goal of this thesis is to develop a tool that supports the creation of the course timetable for a university. The timetable generation problem can be modeled as a mixed-integer optimization problem, characterized by large numerical complexity. As a case study, I consider the Teachings of the Degree Courses related to the Computer, Cinema, and Mechatronic Engineering (ICM) and Electronic, Telecommunication, and Physical Engineering (ETF) colleges of the Politecnico di Torino. The timetable must satisfy many constraints. Some constraints are related to the Students, some are related to the Teachers, and others are related to the single Teachings. Among these constraints, I identify hard constraints, which must be respected, and soft constraints, which, if not respected, can introduce penalties in the optimization function. Two theses were conducted on this topic, in which the timetable allocation was modeled as an Integer Linear Programming (ILP) problem and solved using the solver CPLEX. This thesis, also based on ILP, explores a novel methodology, which consists of representing the timetable as a two-dimensional matrix with the Lecture Slots on the columns and the Teachings on the rows. Each element of the matrix is 1 if there is a lecture for that Teaching in that Slot, and 0 otherwise. The aim is to develop a solution that reduces the numerical complexity and run time with respect to the existing approaches. This goal requires a review of the hard and soft constraints. The first phase of the thesis focuses on identifying the requirements of the problem. Some are inherited from the previous works, some are introduced, and some are not considered since they are not useful for finding a valid solution. After the requirements analysis, the thesis provides a study of the technologies and the literature in order to find the models and approaches already available. Following this study, the conclusion is that the best option is to use the CPLEX software, developed by IBM, which is capable of solving optimization problems. CPLEX is widely known for its performance and robustness, and the fact that it was used in the previous works represents an advantage. Initially, I generate timetables considering the courses related to the academic year 2023-24, in order to have a direct comparison between the timetables generated with this new approach and those generated in the previous theses. This requires refining the constraints to obtain compact timetables without too many consecutive lecture Slots or empty Slots. Once satisfactory results are achieved, I retrieve the course data for the academic year 2025-26 and generate the timetables using those Teachings. The final results are encouraging. The generated timetable, obtained in a computational time of 13 hours, satisfies all hard constraints and is able to adequately handle soft constraints. The results therefore meet the needs of both Teachers and Students. Questionnaires are being conducted to identify any possible problems. An important aspect to take into account during this work is code readability and maintainability. For this reason, I use SonarQube to perform code reviews automatically and highlight potential issues in the code structure. The final section of the thesis provides some suggestions for future improvements. The work is complemented by instruction manuals describing how to use the developed tools.