Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem

Lewis, R. ORCID: https://orcid.org/0000-0003-1046-811X and Thompson, J. 2015. Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem. European Journal of Operational Research 240 (3) , pp. 637-648. 10.1016/j.ejor.2014.07.041

Preview

PDF - Accepted Post-Print Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (638kB) | Preview

Abstract

This paper provides a mathematical treatment of the NP-hard post enrolment-based course timetabling problem and presents a powerful two-stage metaheuristic-based algorithm to approximately solve it. We focus particularly on the issue of solution space connectivity and demonstrate that when this is increased via specialised neighbourhood operators, the quality of solutions achieved is generally enhanced. Across a well-known suite of benchmark problem instances, our proposed algorithm is shown to produce results that are superior to all other methods appearing in the literature; however, we also make note of those instances where our algorithm struggles in comparison to others and offer evidence as to why.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Additional Information:	Available online 4 August 2014. PDF uploaded in accordance with publisher's policy at http://www.sherpa.ac.uk/romeo/issn/0377-2217/ [accessed 29/08/2014]
Publisher:	Elsevier
ISSN:	0377-2217
Date of First Compliant Deposit:	30 March 2016
Date of Acceptance:	25 July 2014
Last Modified:	13 Apr 2024 06:30
URI:	https://orca.cardiff.ac.uk/id/eprint/63924

Citation Data

Cited 38 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item