Toggle Main Menu Toggle Search

ePrints

The development of a Genetic Algorithm Tool for university course timetabling

Lookup NU author(s): Dr Pupong Pongcharoen, Professor Christian Hicks

Downloads

Full text for this publication is not currently held within this repository. Alternative links are provided below where available.


Abstract

University timetabling is an NP-hard problem, which means that the amount of computation required to find solutions increases exponentially with problem size. The process is subject to hard constraints that must be satisfied in order to produce feasible timetables and soft constraints are not absolutely essential. This paper describes a Genetic Algorithm Timetabling Tool (GATT) that has been developed for university course timetabling. The algorithm includes a repair process, which ensures that all hard constraints are satisfied. This prevents clashes and ensures that the rooms are sufficiently large to accommodate the classes. The algorithm evaluates timetables in terms of three soft constraints: i) minimising student movement; ii) avoiding fragmentation in the timetable for students and lecturers; and iii) satisfying lecturers’ preferences for the timing of classes. The algorithm was tested using two sets of timetabling data from the Faculty of Science and Technology at Loei Rajabhat University in Thailand. A ‘small’ problem included 10 degree programmes, 69 subjects, 46 lecturers and 251 classes. A large problem included 30 degree programmes, 128 subjects, 111 lecturers and 758 classes. The best experimental results obtained from GATT satisfied all hard and soft constraints. The GATT was significantly faster than random search and the results were significantly better.


Publication metadata

Author(s): Pongcharoena P, Promtetb W, Yenradeec P, Hicks C

Editor(s): Grubbstrom, RW

Publication type: Conference Proceedings (inc. Abstract)

Publication status: Published

Conference Name: Fourteenth International Working Seminar on Production Economics

Year of Conference: 2006

URL: http://www2.ipe.liu.se/rwg/igls/igls.htm


Share