Hybrid particle swarm optimization with particle elimination for the high school timetabling problem
- PDF / 1,349,433 Bytes
- 16 Pages / 595.276 x 790.866 pts Page_size
- 96 Downloads / 209 Views
RESEARCH PAPER
Hybrid particle swarm optimization with particle elimination for the high school timetabling problem Joo Siang Tan1 · Say Leng Goh1 · Suaini Sura1 · Graham Kendall2,3 · Nasser R. Sabar4 Received: 13 March 2020 / Revised: 2 July 2020 / Accepted: 6 August 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract In this paper, a PSO-based algorithm that hybridized Particle Swarm Optimization (PSO) and Hill Climbing (HC) is applied to high school timetabling problem. This hybrid has two features, a novel solution transformation and particle elimination. The proposed methodologies are tested on the XHSTT-2014 dataset (which is relatively new for the school timetabling problem) plus other additional instances. The experimental results show that the proposed algorithm is effective in solving small and medium instances compared to standalone HC and better than the conventional PSO for most instances. In a comparison to the state of the art methods, it achieved the lowest mean of soft constraint violations for 7 instances and the lowest mean of hard constraint violations for 1 instance. Keywords Particle swarm optimization · Hill climbing · Hybridisation · School timetabling
1 Introduction Timetable construction is a Non-Polynomial (NP) complete decision problem [16]. It belongs to both NP and the NPhard complexity classes. With the exponential increase of decision problem size, it is impossible for a deterministic algorithm to find an optimal solution under polynomial time, as most scientists believed P ≠ NP [2]. Generally, four * Say Leng Goh [email protected] Joo Siang Tan [email protected] Suaini Sura [email protected] Graham Kendall [email protected] Nasser R. Sabar [email protected] 1
Optimization Research Group, Faculty of Computing and Informatics, Universiti Malaysia Sabah, Sabah, Malaysia
2
The University of Nottingham Malaysia Campus, Jalan Broga, 43500 Semenyih, Selangor Darul Ehsan, Malaysia
3
The University of Nottingham, University Park, Nottingham NG7 2RD, UK
4
Department of Computer Science and Information Technology, La Trobe University, Melbourne, Australia
common parameters are used in educational timetabling problem: times, resources, meetings and constraints. The objective is to assign times and resources to the meetings by minimising the constraints violations [22]. There are many types of timetabling problems, e.g. educational [11–14], sports [27], transportation [24], nurse rostering [4] etc. High school timetabling is a variant of the educational timetabling problem. High school timetabling problem involves assigning time and resources (teachers, students, classes and rooms) to a collection of events while respecting certain constraints. Some of the usual constraints are; two subjects cannot occur simultaneously in the same room, a teacher cannot be assigned to two subjects at the same time, no idle time for students and workload limit for teachers. In practice, it is important to have an efficient timetable to prevent teachers
Data Loading...
