Solving time-tabling problems using evolutionary algorithms and heuristics search

Abstract

The university time-tabling problem deals with scheduling classes into available timeslots without violating any constraints of time, venue and personnel. This problem is considered to be of complexity NP and therefore takes a lot of time to solve manually. In this chapter, a new approach to solve these by using a multi-layered-algorithm combining evolutionary algorithms and heuristic search has been attempted. Instead of considering all the constraints equally and in a concurrent manner, different types of constraints are handled by different techniques in separate layers. An evolutionary algorithm first generates sequences of classes, and a heuristic function is then applied to estimate the cost (in terms of number of timeslots needed) to satisfy all the constraints, which is then used by the evolutionary algorithm to rate its individuals. The heuristic function has the advantage of giving results quite quickly. The implementation of this algorithm on actual data obtained from a large university department has been very successful in solving complicated scheduling problems. Indeed, it takes less than thirty seconds to give multiple feasible solutions to this complex real-life time-tabling problem with vast search space (around 10180 possibilities). © 2009 Springer-Verlag Berlin Heidelberg.