Knowledge-based genetic algorithm for university course timetabling problems

Article type: Research Article

Authors: Kanoh, Hitoshi^{; *} | Sakamoto, Yuusuke

Affiliations: Department of Computer Science, Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba, Ibaraki, 305-8573, Japan

Correspondence: [*] Corresponding author. E-mail: kanoh@cs.tsukuba.ac.jp

Abstract: This paper discusses a new solution to university course timetabling problems. The problems that belong to the NP-hard class are very difficult to solve using conventional optimization techniques. Our solution methodology is based on a genetic algorithm which uses an installed knowledge base and an infection operation. The knowledge base here is a set of candidate partial solutions of the final solution, and is built from timetables used in past years and teachers' requests relating to how they can work more efficiently. Consequently, the timetable obtained may satisfy teachers' requests and can preserve the advantages of past timetables. Experiments using timetables of University of Tsukuba showed that this approach is an effective solution method. The proposed method includes general techniques concerning the use of problem-specific knowledge that can be applied to a variety of large-scale real-life combinatorial optimization problems.

Keywords: Knowledge base, genetic algorithm, timetable, interactive system, real-life problem

DOI: 10.3233/KES-2008-12403

Journal: International Journal of Knowledge-based and Intelligent Engineering Systems, vol. 12, no. 4, pp. 283-294, 2008