Complex university course timetabling

This paper summarizes the work done to solve a complex course timetabling problem at a large university and provides new insights into the overall timetabling process. The first step in the successful solution of this problem was to define a course structure model that allowed application of classical course timetabling methods. Several methods were necessary to solve the complete problem. First, support procedures were needed to detect and correct an infeasible problem where hard constraints were being violated. The resulting timetabling problem was then solved via a search for a complete assignment of times and rooms to classes, taking all hard and soft constraints into account. Methods were also developed for modifying a computed solution in response to changes introduced at a later time while having a minimal impact on existing assignments. These problems are described formally using a weighted constraint satisfaction model of the timetabling problem and solutions are proposed through two types of the algorithms: (1) generic iterative forward search with conflict‐based statistics, and (2) branch and bound. Experimental results from the course timetabling system developed for Purdue University are provided. These include solutions computed by university schedulers using the system for two separate terms along with extensive experiments solving two central and six departmental problems, individually, and as a combined problem with almost 2,500 classes. The system described is currently used on all of the many varied course timetabling problems encountered each term at Purdue University.