Brunel University Research Archive (BURA) >
Schools >
School of Information Systems, Computing and Mathematics >
School of Information Systems, Computing and Mathematics Research Papers >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/5985

Title: A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling
Authors: Jat, SN
Yang, S
Keywords: Post enrolment course timetabling problem
University course timetabling problem
Guided search genetic algorithm
Local search
Tabu search
Publication Date: 2011
Publisher: Springer
Citation: Journal of Scheduling, 14(6): 617-637, Dec 2011
Abstract: The post enrolment course timetabling problem (PECTP) is one type of university course timetabling problems, in which a set of events has to be scheduled in time slots and located in suitable rooms according to the student enrolment data. The PECTP is an NP-hard combinatorial optimisation problem and hence is very difficult to solve to optimality. This paper proposes a hybrid approach to solve the PECTP in two phases. In the first phase, a guided search genetic algorithm is applied to solve the PECTP. This guided search genetic algorithm, integrates a guided search strategy and some local search techniques, where the guided search strategy uses a data structure that stores useful information extracted from previous good individuals to guide the generation of offspring into the population and the local search techniques are used to improve the quality of individuals. In the second phase, a tabu search heuristic is further used on the best solution obtained by the first phase to improve the optimality of the solution if possible. The proposed hybrid approach is tested on a set of benchmark PECTPs taken from the international timetabling competition in comparison with a set of state-of-the-art methods from the literature. The experimental results show that the proposed hybrid approach is able to produce promising results for the test PECTPs.
Description: Copyright @ Springer Science + Business Media. All rights reserved.
Sponsorship: This work was supported by the Engineering and Physical Sciences Research Council (EPSRC) of UK under Grant EP/E060722/01 and Grant EP/E060722/02.
URI: http://www.springerlink.com/content/d13x4276p5142825/
http://bura.brunel.ac.uk/handle/2438/5985
DOI: http://dx.doi.org/10.1007/s10951-010-0202-0
ISSN: 1094-6136
Appears in Collections:School of Information Systems, Computing and Mathematics Research Papers
Computer Science

Files in This Item:

File Description SizeFormat
Fulltext.pdf339.28 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.

 


Library (c) Brunel University.    Powered By: DSpace
Send us your
Feedback. Last Updated: September 14, 2010.
Managed by:
Hassan Bhuiyan