An effective hybrid local search approach for the post enrolment course timetabling problem
- PDF / 394,198 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 95 Downloads / 191 Views
An effective hybrid local search approach for the post enrolment course timetabling problem Say Leng Goh1 · Graham Kendall1,2,3 · Nasser R. Sabar1,4 · Salwani Abdullah5 Accepted: 7 May 2020 © Operational Research Society of India 2020
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
1 Introduction Combinatorial optimization problems (COP) require decision making on the values for variables in a discrete search space, seeking to optimize (maximise or minimize) an objective function. Traveling salesman, vehicle routing, bin packing, timetabling and
B
Say Leng Goh [email protected]
Extended author information available on the last page of the article
123
OPSEARCH
minimal spanning tree are some examples of COP. Timetabling problem involves the placement of resources in time and space in such a way to optimize utilization and satisfy stakeholders’ requirements. Instances of this problem include sports timetabling, educational timetabling, nurse rostering, transportation timetabling, etc. We focus on the PE-CTT problem, a type of educational timetabling. In this context, the timetable is a placement of courses into time slots and rooms, fulfilling a set of constraints. University students are allowed to select their favourite courses every semester. Therefore, the general prerequisite is that they can attend all their registered courses without hindrance such as clashing of courses. In other words, events attended by a student should not be allotted to the identical time slot. This requirem
Data Loading...
