Being co-chair of both PATAT and MISTA international timetabling and scheduling conferences for the past few years has put me in a good position to ponder one interesting issue from a practical as well as commercial perspective: what use is timetabling research? I won’t attempt to cover the entirety of this complex issue in just one piece, but I’ll introduce you to some of the key themes for researchers and practitioners.
In this post I would like to address the fundamental building block of developing and improving solutions to institutional timetabling problems – the heuristic. I cannot over-emphasise the importance of heuristics as they represent human approaches which have been encapsulated within computer-based approaches, resulting in a methodology that aligns the strength of the human mind with the analytical dexterity of computers, and one which has come to dominate research in the complex field of timetabling. If we are ever to deliver the ‘big red button’ that provides a high quality timetable solution each time it is hit, the heuristic will be the dominant driver in how the button works!
Heuristics are simply rules describing how humans go about solving problems such as creating solutions to a timetabling problem. They don’t necessarily deliver optimum solutions but they are instrumental in either constructing and subsequently improving on that solution. For example, faced with the job of constructing an examination timetable, an enthusiastic timetabler may choose the most ‘problematic’ exams first. These may be exams with the most students enrolled, exams that have to be timetabled early in the session as they are part of a sequence of exams that must be taken in order, exams which have the most students enrolled that are also taking other exams, or exams that have the most students enrolled that require alternative arrangements. The question is which one of these, which sequence or which combination, will ultimately provide the best solution? This is where the power of computing comes into play.
A metaheuristic is a computer construct which allows individual or groups of heuristics to operate repetitively many times per second, with the goal of producing or improving a solution. Which heuristics to use, how to apply them and how to evaluate their effectiveness is the backbone of the ongoing approach within this area of timetabling research. Families of these approaches have evolved, ranging from basic search through engineering and nature-inspired approaches, to more generic approaches known as ‘hyperheuristics’. For those of you interested to hear more please contact EventMAP and we can advise on some of the more accessible research papers to read.
So just how useful are these approaches? From a research perspective, they allow individuals to study how heuristics can be designed and constructed, based on either established benchmark datasets or datasets from specific institutions. Although I believe that research has moved quickly in terms of heuristic design, there is a problematic area with the underlying foundation of the research. The benchmark datasets, although representative of timetabling data, do not contain all of the complexities, incompleteness, uncertainty or, indeed, incorrectness that we see in real world situations. Therefore, in these cases, the research is very much about good heuristic design as opposed to actually addressing the underlying real world problem. In the case where data is used from specific institutions that is not released to other researchers, it is often the case that the heuristics are specifically designed to suit that particular dataset, rendering it difficult to compare with other datasets and approaches. In other cases where data is released, it is often the case that the underlying complexity has been removed meaning the resultant research and comparison of techniques/results is only of limited use in helping to advance the field of research.
Bluntly, I’d argue that this does serve to highlight the fact that research has still much more to contribute to the world of timetabling. So, what is the result of this? Well, institutional timetablers around the world are still faced with all of the same old problems, but with only very limited research-informed tools to draw on. Of course, there are many other factors as to why a gap still remains between research and practice – though for here I have very much taken the practitioner’s view.
As always, we now come to the EventMAP pitch: we have built ‘best-of-breed’ heuristic approaches into our offerings and have the people and skills to implement these in a way that addresses a cornucopia of timetabling problems – ranging from simply getting a solution, to providing a solution that makes best use of space, delivers on staff flexibility and provides the best possible student experience.
EventMAP represent a synergy between research and practice and, through involvement with the likes of PATAT and MISTA, we aim to use the best that research has to offer to inform the development of our products and educate the wider timetabling community on both what is possible and how value can be added to all aspects of timetable construction and improvement.
In subsequent blogs I will approach issues such as automation, optimisation, evaluation and how these areas have developed over the last 25 years.
Dr. Barry McCollum is Managing Director of EventMAP and a Senior Lecturer within the School of Electronics, Electrical Engineering and Computer Science at Queen's University, Belfast. His academic research profile can be viewed here.
