University timetabling by constraint-based reasoning: A case study

Abstract

This paper presents a case-study which applies constraint-based reasoning to university timetable planning. The timetabling problem is formulated as a constraint satisfaction model and this model is solved using constrained-directed search algorithms with built-in forward checking and constraint propagation. The model and algorithms were tested with real data containing 536 lessons to be scheduled into 45 timeslots and 21 rooms. The solution to the problem was obtained with minimal computing effort and processing time. This study showed that modelling and remodelling could be carried out easily through a proposed parameterised model formulation. The proposed approach has also successfully maximised room utilisation and minimised the number of timeslots required to deliver all the lectures. This finding may facilitate the widespread implementation of automated timetabling systems to larger scale problems and a wider variety of application domains.