Computing and Information Systems - Theses

Permanent URI for this collection

Search Results

Now showing 1 - 1 of 1
  • Item
    Thumbnail Image
    Techniques for academic timetabling
    Merlot, Liam ( 2005)
    This thesis examines two different academic timetabling problems: the Examination Timetabling problem and the Population and Class Timetabling Problem. Initially an extensive survey of academic timetabling literature is undertaken, examining those methods and algorithms that have proved useful for solving academic timetabling problems. A hybrid algorithm, combining constraint programming, simulated annealing and hill climbing, is presented as a method for solving the examination timetabling problem. This algorithm is able to solve the examination timetabling problem at the University of Melbourne, and provides good results on international benchmark data. The population and class timetabling problem is decomposed using the blocking decomposition into a series of integer programs that are all solved to optimality. A model is presented for a simplified version of the class blocking and population problem which solves this problem to optimality without further decomposition. The model is expanded to solve this problem faced by Xavier College, an Australian secondary school. Two separate overlapping blocking schemes are used to allow the problem for different year levels to be solved simultaneously. Two more integer programs allocate to sessions the lessons of the blocks and a subset of the classes from the school. When combined these three stages produce a feasible timetable for Xavier College in a fraction of the time it takes using the current methodology.