Simulated annealing with improved reheating and learning for the post enrolment course timetabling problem

Goh, Say Leng; Kendall, Graham; Sabar, Nasser R.

Abstract

In this paper, we utilise a two-stage approach for addressing the post enrolment course timetabling (PE-CTT) problem. We attempt to find a feasible solution in the first stage. The solution is further improved in terms of soft constraint violations in the second stage. We present an enhanced variant of the Simulated Annealing with Reheating (SAR) algorithm, which we term Simulated Annealing with Improved Reheating and Learning (SAIRL). We propose a reinforcement learning-based methodology to obtain a suitable neighbourhood structure for the search to operate effectively. We incorporate the average cost changes into the reheating temperature function. The proposed enhancements are tested on three widely studied benchmark data-sets. Our algorithm eliminates the need for tuning parameters in conventional SA as well as neighbourhood structure composition in SAR. The results are highly competitive with SAR and other state of the art methods. In addition, SAIRL is scalable when the runtime is extended. The algorithm achieves new best results for 6 instances and new mean results for 14 instances.

Citation

Goh, S. L., Kendall, G., & Sabar, N. R. (2019). Simulated annealing with improved reheating and learning for the post enrolment course timetabling problem. Journal of the Operational Research Society, 70(6), 873-888. https://doi.org/10.1080/01605682.2018.1468862

• Journal Article Type: Article
• Acceptance Date: Apr 20, 2018
• Online Publication Date: Jun 22, 2018
• Publication Date: 2019
• Deposit Date: May 11, 2020
• Journal: Journal of the Operational Research Society
• Print ISSN: 0160-5682
• Electronic ISSN: 1476-9360
• Publisher: Taylor and Francis
• Peer Reviewed: Peer Reviewed
• Volume: 70
• Issue: 6
• Pages: 873-888
• DOI: https://doi.org/10.1080/01605682.2018.1468862
• Public URL: https://nottingham-repository.worktribe.com/output/1854602
• Publisher URL: https://www.tandfonline.com/doi/abs/10.1080/01605682.2018.1468862?journalCode=tjor20
• Additional Information: Peer Review Statement: The publishing and review policy for this title is described in its Aims & Scope.; Aim & Scope: http://www.tandfonline.com/action/journalInformation?show=aimsScope&journalCode=tjor20