Topics in Applied Operational Research – University Timetabling

Project Overview

We developed a Mixed-Integer Linear Programming model for university timetabling at the University of Edinburgh. While our model proved effective on small, individual-school scales, it proved infeasible on the university-level dataset. The relaxation formulated to force feasibility combined with the larger scale led to a computationally intractable model. While our model works to generate optimized timetables, our conclusion was that it would not be a practical tool for most practical applications. Our suggestions concerned ways to decrease the computational complexity by changing model inputs and modelling approach.

The University of Edinburgh's Timetabling Office presented several areas of interest in which they wanted exploration of improved timetabling techinques, of which our group selected Time. This meant exploring timetables reducing core teaching hours, ensuring students and staff have a lunch break, delivering core teaching events without clashes within each degree program, and considering the effect these changes would have on timeslot and room utilization. To answer these questions, we formulated and implemented a Mixed-Integer Linear Program minimizing the number of clashes between events associated with any courses, mandatory and elective, that could be taken concurrently on a degree program by assigning course events to timeslots subject to each of these constraints, as well as standard timetabling logic.

This strict model was initially implemented through Gurobi's Python library for The Royal (Dick) School of Veterinary Sciences at the University of Edinburgh, with a feasible timetable generated in a relatively short runtime. Implementing this model on the full university dataset proved infeasible, leading us to reformulate a relaxation of the original model. This led to a model that failed to converge to optimality after 47 hours of runtime. To account for this, we implemented a genetic algorithm, with the purpose of improving incumbent solutions generated by time-limited runs of Gurobi and returning these improved solutions as a warm starting point to the solver. This approach yielded improved timetables over equivalent runtime when comparing to the original approach reliant entirely on the MIP solver.

While our model yielded feasible timetables that minimized violations of the Timetabling Office's proposed considerations, our ultimate suggestion was not to implement or use our model due to its lack of practicality for the Timetabling Office. We assessed this lack of practicality based both on the model's resource requirements and technical complexity. We proposed instead several, non-techincal techniques related to conflict resolution, data collection, and curriculum development that could yield improvements in the timetabling process generally, as well as potentially reduce the data cleaning necessary to use our method and reduce the solution space in a way that may make our method more tractable. We also identified further considerations our model could be extended to make, including spatial relationships between campus locations and consideration of student enrollment data as a prioritizing factor with regard to clash reduction.

Personal Reflection

I got to work on a lot of the applied nature of this project. Once our designated math ringer had an initial model formulation, I was in the weeds in pandas and Excel trying to wrangle the data into something manageable. Then I found myself in another patch of weeds marrying the data and the Gurobi-implemented, entirely-MIP model to get solutions we could use. This meant that it was ultimately my responsiblity to formulate and implement relaxations in order to get a timetable. Once I had solutions, I then had to figure out how to turn them into something comprehensible, which led to the code used for all of our heatmaps. In retrospect, there were probably tighter relaxations available, and the weighting of constraint violation penalties should have been tuned as opposed to arbitrarily picked. In an ideal situation, both of these would have been done in consultation with and with help from my teammates; however, due to time the time crunch we found ourselves in (more on that later), this proved infeasible. I do quite enjoy this sort of applied work, even if parts of it can at times be frustrating beyond belief. I would also like to take this current opportunity to shout out Ben De Sousa, Todd House, Conor McArthur, and Alexandros Zachakos for their contributions to this work; it's always a pleasure working with you gents.

Unfortunately, this project fell short of my initial expectations. This mostly comes down to a failure on our part in time management. I know that I certainly underestimated the amount of work the data would require in terms of cleaning, preparation, and manipulation for use in our model. More importantly, we as a group and I personally felt a false sense of security from the fact that this project spanned the entire spring term. As a result of these combined factors, we seemed to waste a fair bit of the first part of the term focusing on other courses and working with the data. Predictably, this led to a major crunch in the final several weeks of the term, where we had what at times seemed the impossible task of finishing data work, iteratively adapting a base model that was proving infeasible, implementing our genetic algorithm extension, and presenting everything in the written report and oral presentation. While I stand by the work we did here, if I were to do it again, I would try to more effectively use the term, so we could consider further timetabling factors, extension modelling and solution approaches, and perhaps even some consideration of fairness and wellbeing. It would have been nice to consider things like weighting clashes by projected student enrollment, column generation, and fair distributions of program-related events between programs. Additionally, considering various student enrollment scenarios as in A predict-and-prescribe framework for dynamic course scheduling toward strategic university scaling (Aygül et al., 2026) would have been nice. Of course, if ifs and buts were candy and nuts...

That said, I do think some of our struggles had to do with the organization of the course and project. While this project was nominally a consultation for the Timetabling Office, our communication with the Office was limited to a single, one hour Q&A session with a member of Timetabling that occured during Week 3, before we had submitted a project plan or had sufficient time to properly consider the problem or data at hand. In my experience, stakeholder input is essential to this kind of project, and this lack of stakeholder impact meant we had little idea which questions to prioritize or what functionality our tool should have, nor were we able to benefit from the Timetabling Office's expertise in timetabling and the input data. It also did not help that expectations for our final deliverables were not communicated until the final two weeks of the term. Again, I will reiterate, that the brunt of the responsibility for this project's shortcomings falls on me and, to a lesser extent, our group. I only bring up these external factors to provide some additional context as to why the project fell short of my original, day one expectations.

Downloads

Written Report (PDF)

Report

Presentation Slides (PDF)

Slides