IJASEIT

International Journal on Advanced Science, Engineering and Information Technology, Vol. 10 (2020) No. 3, pages: 1051-1057, DOI:10.18517/ijaseit.10.3.10233

Two-stage Heuristic for Primary School Timetabling Problem with Combined Classes Consideration

San Nah Sze, See Yan Tan, Kang Leng Chiew, Wei King Tiong

Abstract

This research focuses on a primary school timetabling problem, a small-scale primary school that is located at Pengerang, Johor. In this small-scale primary school, six classes have been allotted, from standard one until standard six. Most of the primary school timetables are manually developed, which is extremely time-consuming. According to the new policy announced on 12^th Dec 2017by the Ministry of Education (MoE) Malaysia, due to the shortage of teachers, combined-classes should be implemented in low-enrolment schools with fewer than 30 students. MoE has introduced another policy on 30^th June 2018 that recommends schools to reduce the number of subjects that are being taught in a day to solve the overloaded school bag issue. There is a set of hard constraints in this primary school timetabling problem due to the stipulation that a teacher can only teach one subject at a time; each subject must satisfy the total weekly period(s), and the combined classes can only combine one subject at a time. The main objective of this study is to propose a heuristic solution to this solves primary school timetabling problem with the consideration of combined-classes. A two-stage timetabling heuristic approaches been offered due to its simplicity in dealing with numerous constraints. The two-stage heuristic method was clustered into subject groups in the first stage to ease the timeslots allocation in the second stage. A clash-free timetable can be obtained from this proposed algorithm. The result generated by this proposed solution outperforms the current manual practice in solution quality and computing efficiency.