Using logical and creative thinking to improve course timetabling
Computer Science PhD student James Sakal is using logical and creative thinking – rooted in mathematics – to find solutions to the question ‘What makes a good timetable for scheduling University courses?’ James’s PhD supervisors are Prof Jonathan Fieldsend and Prof Edward Keedwell.
What is your background?
I have had a passion for mathematics for as long as I can remember. I was the annoying child at primary school demanding to be taught basic algebra and negative numbers while my classmates were getting to grips with their times tables. Visualisations in mathematics fascinated me too – from the tessellations and geometric art of M. C. Escher, to pie charts and histograms used for displaying data.
At age seven I also had my first experience with computer programming, writing interactive games using GW-BASIC. It is perhaps no surprise therefore that I went on to take degrees with both applied mathematics and computer science components. What people who perceive maths as dull or dry perhaps fail to realise is just how much of an art form it becomes at a higher level.
For my PhD, I am making creative use of mathematics both for modelling and solving of a real world problem. Specifically, university course timetabling – which is the puzzle of assigning lectures and courses to rooms and time periods in a way that minimises the amount of clashes for the thousands of students and lecturers attending the university. The sheer scale of numbers makes this problem almost impossible to solve manually. So, I am using and adapting ideas inspired by nature to design computer programs that, when run over a period of time, gradually generate better and better timetables. This field is known more broadly as optimisation. The fact that inspiration has come from phenomena as diverse as the path-finding ability of ant colonies and biological genetic reproduction highlights the innovative and creative elements of this project.
What’s next for your research?
At the heart of this project is the question: What makes a good timetable? Properties that we may desire can be defined individually. Some examples of these include: Wanting to locate a particular lecture consistently in the same room, ensuring lectures of a course have a reasonable spread throughout the week and not filling rooms beyond their capacity. All of these can then be formulated in the language of mathematics and treated as different objectives that we seek to optimise.
Currently I am working with algorithms that attempt to tackle all of these objectives simultaneously. The next step may involve a more targeted and sequential approach, in which we focus on improving one particular objective at a time. As the computer program runs, we could assess the state of the best timetable found so far, find out which objectives are scoring poorest, and guide the search in real time by deploying more resources to those areas, for example.
What are the best and worst things about your field of work?
With large-scale timetabling, finding the absolute ‘best’ solution is not considered a practical goal. Rather, the optimisation process seeks to find timetables that are sufficiently good for use, within an acceptable timeframe. The scope, therefore, for devising algorithms that are better, faster, or more specialised is almost unlimited. I have found this to be a blessing and a curse in equal measure!
On the one hand, the project is rarely boring as there are always new avenues and concepts to explore. On the other hand, it is important to set realistic aims and exhaust the potential of each new idea before advancing to the next. Optimisation runs can be time consuming, and often have to be repeated many times in order to generate statistically significant results. To this end, I have a powerful computer that is crunching numbers 24/7. However, full sets of results for multiple test problems and repetitions can take days or weeks to emerge. This can lead to a fragmented work flow and also means I have to be careful about which runs I commit to in advance.
These technical aspects aside, the opportunity to work in the kind of stimulating and supportive environment that the University of Exeter and my department provide is wonderful. Ultimately, what attracts me to my research subject is that it is abstract in its detail but with potential for real world benefits. It involves both logical and creative thinking, which keeps both halves of my brain happy.