An effective hybrid local search approach for the post enrolment course timetabling problem

Say Leng Goh (), Graham Kendall (), Nasser R. Sabar () and Salwani Abdullah ()
Additional contact information
Say Leng Goh: Universiti Malaysia Sabah Labuan International Campus
Graham Kendall: Universiti Malaysia Sabah Labuan International Campus
Nasser R. Sabar: Universiti Malaysia Sabah Labuan International Campus
Salwani Abdullah: Universiti Kebangsaan Malaysia

OPSEARCH, 2020, vol. 57, issue 4, No 5, 1163 pages

Abstract: Abstract We address the post enrolment course timetabling (PE-CTT) problem in this paper. PE-CTT is known as an NP-hard problem that focuses on finding an efficient allocation of courses onto a finite number of time slots and rooms. It is one of the most challenging resources allocation problems faced by universities around the world. This work proposes a two-phase hybrid local search algorithm to address the PE-CTT problem. The first phase focuses on finding a feasible solution, while the second phase tries to minimize the soft constraint violations of the generated feasible solution. For the first phase, we propose a hybrid of Tabu Search with Sampling and Perturbation with Iterated Local Search. We test the proposed methodology on the hardest cases of PE-CTT benchmarks. The hybrid algorithm performs well and our results are superior compared to the recent methods in finding feasible solutions. For the second phase, we propose an algorithm called Simulated Annealing with Reheating (SAR) with two preliminary runs (SAR-2P). The SAR algorithm is used to minimize the soft constraint violations by exploiting information collected from the preliminary runs. We test the proposed methodology on three publicly available datasets. Our algorithm is competitive with the standards set by the recent methods. In total, the algorithm attains new best results for 3 cases and new best mean results for 7 cases. Furthermore, it is scalable when the execution time is extended.

Keywords: Tabu Search with Sampling and Perturbation (TSSP); Iterated local search (ILS); TSSP-ILS; SAR; SAR-2P (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s12597-020-00444-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:opsear:v:57:y:2020:i:4:d:10.1007_s12597-020-00444-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/12597

DOI: 10.1007/s12597-020-00444-x

Access Statistics for this article

OPSEARCH is currently edited by Birendra Mandal

More articles in OPSEARCH from Springer, Operational Research Society of India
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().