Improved local search approaches to solve the post enrolment course timetabling problem
In this work, we are addressing the post enrollment course timetabling (PE-CTT) problem. We combine different local search algorithms into an iterative two stage procedure. In the first stage, Tabu Search with Sampling and Perturbation (TSSP) is used to generate feasible solutions. In the second sta...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Published: |
2017
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/49525/ |
| _version_ | 1848798016129990656 |
|---|---|
| author | Goh, Say Leng Kendall, G. Sabar, Nasser R. |
| author_facet | Goh, Say Leng Kendall, G. Sabar, Nasser R. |
| author_sort | Goh, Say Leng |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | In this work, we are addressing the post enrollment course timetabling (PE-CTT) problem. We combine different local search algorithms into an iterative two stage procedure. In the first stage, Tabu Search with Sampling and Perturbation (TSSP) is used to generate feasible solutions. In the second stage, we propose an improved variant of Simulated Annealing (SA), which we call Simulated Annealing with Reheating (SAR), to improve the solution quality of feasible solutions. SAR has three features: a novel neighborhood examination scheme, a new way of estimating local optima and a reheating scheme. SAR eliminates the need for extensive tuning as is often required in conventional SA. The proposed methodologies are tested on the three most studied datasets from the scientific literature. Our algorithms perform well and our results are competitive, if not better, compared to the benchmarks set by the state of the art methods. New best known results are provided for many instances. |
| first_indexed | 2025-11-14T20:13:04Z |
| format | Article |
| id | nottingham-49525 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T20:13:04Z |
| publishDate | 2017 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-495252020-05-04T19:00:42Z https://eprints.nottingham.ac.uk/49525/ Improved local search approaches to solve the post enrolment course timetabling problem Goh, Say Leng Kendall, G. Sabar, Nasser R. In this work, we are addressing the post enrollment course timetabling (PE-CTT) problem. We combine different local search algorithms into an iterative two stage procedure. In the first stage, Tabu Search with Sampling and Perturbation (TSSP) is used to generate feasible solutions. In the second stage, we propose an improved variant of Simulated Annealing (SA), which we call Simulated Annealing with Reheating (SAR), to improve the solution quality of feasible solutions. SAR has three features: a novel neighborhood examination scheme, a new way of estimating local optima and a reheating scheme. SAR eliminates the need for extensive tuning as is often required in conventional SA. The proposed methodologies are tested on the three most studied datasets from the scientific literature. Our algorithms perform well and our results are competitive, if not better, compared to the benchmarks set by the state of the art methods. New best known results are provided for many instances. 2017-08-16 Article PeerReviewed Goh, Say Leng, Kendall, G. and Sabar, Nasser R. (2017) Improved local search approaches to solve the post enrolment course timetabling problem. European Journal of Operational Research, 261 (1). pp. 17-29. ISSN 0377-2217 Timetabling Combinatorial optimization Local search Tabu Search with Sampling and Perturbation (TSSP) Simulated Annealing with Reheating (SAR) https://doi.org/10.1016/j.ejor.2017.01.040 |
| spellingShingle | Timetabling Combinatorial optimization Local search Tabu Search with Sampling and Perturbation (TSSP) Simulated Annealing with Reheating (SAR) Goh, Say Leng Kendall, G. Sabar, Nasser R. Improved local search approaches to solve the post enrolment course timetabling problem |
| title | Improved local search approaches to solve the post enrolment course timetabling problem |
| title_full | Improved local search approaches to solve the post enrolment course timetabling problem |
| title_fullStr | Improved local search approaches to solve the post enrolment course timetabling problem |
| title_full_unstemmed | Improved local search approaches to solve the post enrolment course timetabling problem |
| title_short | Improved local search approaches to solve the post enrolment course timetabling problem |
| title_sort | improved local search approaches to solve the post enrolment course timetabling problem |
| topic | Timetabling Combinatorial optimization Local search Tabu Search with Sampling and Perturbation (TSSP) Simulated Annealing with Reheating (SAR) |
| url | https://eprints.nottingham.ac.uk/49525/ https://eprints.nottingham.ac.uk/49525/ |