Two example optimisation problems from the world of education

This work considers two distinct combinatorial optimisation problems related to education, namely lecture timetabling and school bus scheduling, both of which are known to be NP-hard. Our research into these problems has centred around the design of various high-performance heuristics that are able to produce good quality solutions to these problems in short amounts of time. To do this, we propose that it is necessary to “get to the heart” of these problems by identifying their underlying sub-problems. This, in turn, helps to inform the design of algorithmic operators that are able to exploit these structures and help to produce the solutions we need. In this extended abstract these problems are briefly considered in turn