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 12th 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 30th 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.


Keywords


combined classes; government policy; primary school timetabling; small scale primary school; two-stage heuristic.

Full Text:

PDF

References


N. Pillay, “A review of hyper-heuristics for educational timetabling,†Ann. Oper. Res., vol. 239, no. 1, pp. 3–38, 2016.

A. Schaerf, “A survey of automated timetabling,†Artif. Intell. Rev., vol. 13, no. 2, pp. 87–127, 1999.

E. Demirović and N. Musliu, “Modeling high school timetabling with bitvectors,†Ann. Oper. Res., vol. 252, no. 2, pp. 215–238, 2017.

E. Demirovic and N. Musliu, “Modeling high school timetabling as partialweighted maxsat,†in LaSh 2014: The 4th Workshop on Logic and Search (a SAT/ICLP workshop at FLoC 2014), July 18, Vienna, Austria, 2014.

E. Demirović and P. J. Stuckey, “Constraint Programming for High School Timetabling: A Scheduling-Based Model with Hot Starts,†in International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2018, pp. 135–152.

E. K. Burke, B. McCollum, A. Meisels, S. Petrovic, and R. Qu, “A graph-based hyper-heuristic for educational timetabling problems,†Eur. J. Oper. Res., vol. 176, no. 1, pp. 177–192, 2007.

A. Meisels, J. Ellâ€sana, and E. Gudes, “Decomposing and solving timetabling constraint networks,†Comput. Intell., vol. 13, no. 4, pp. 486–505, 1997.

T. Birbas, S. Daskalaki, and E. Housos, “School timetabling for quality student and teacher schedules,†J. Sched., vol. 12, no. 2, p. 177, 2009.

A. Kheiri, E. Özcan, and A. J. Parkes, “A stochastic local search algorithm with adaptive acceptance for high-school timetabling,†Ann. Oper. Res., vol. 239, no. 1, pp. 135–151, 2016.

N. Poddar and B. Mondal, “An instruction on course timetable scheduling applying graph coloring approach,†Int. J. Recent Sci. Res., vol. 9, no. 2(C), pp. 23939–23945, 2018.

M. Sørensen and F. H. W. Dahms, “A two-stage decomposition of high school timetabling applied to cases in Denmark,†Comput. Oper. Res., vol. 43, pp. 36–49, 2014.

O. Abayomi-Alli, A. Abayomi-Alli, S. Misra, R. Damasevicius, and R. Maskeliunas, “Automatic Examination Timetable Scheduling Using Particle Swarm Optimization and Local Search Algorithm,†in Data, Engineering and Applications, Springer, 2019, pp. 119–130.

M. H. Abdalla, J. H. Obit, R. Alfred, and J. Bolongkikit, “Agent based integer programming framework for solving real-life curriculum-based university course timetabling,†in Computational Science and Technology, Springer, 2019, pp. 67–76.

R. Alvarez-Valdes, G. Martin, and J. M. Tamarit, “Constructing good solutions for the Spanish school timetabling problem,†J. Oper. Res. Soc., vol. 47, no. 10, pp. 1203–1215, 1996.

H. M. M. ten Eikelder and R. J. Willemen, “Some complexity aspects of secondary school timetabling problems,†in International Conference on the Practice and Theory of Automated Timetabling, 2000, pp. 18–27.

C. Lara, J. J. Flores, and F. Calderón, “Solving a school timetabling problem using a bee algorithm,†in Mexican International Conference on Artificial Intelligence, 2008, pp. 664–674.

A. Kheiri and E. Keedwell, “A hidden markov model approach to the problem of heuristic selection in hyper-heuristics with a case study in high school timetabling problems,†Evol. Comput., vol. 25, no. 3, pp. 473–501, 2017.

A. F. Khair, M. Makhtar, M. Mazlan, M. A. Mohamed, and M. N. A. Rahman, “An ant colony algorithm for universiti sultan zainal abidin examination timetabling problem,†Indones. J. Electr. Eng. Comput. Sci., vol. 13, no. 1, pp. 191–198, 2019.

M. Dener and M. H. Calp, “Solving the exam scheduling problems in central exams with genetic algorithms,†arXiv Prepr. arXiv1902.01360, 2019.

A. Rozaimee, A. N. Shafee, N. A. A. Hadi, and M. A. Mohamed, “A framework for university’s final exam timetable allocation using genetic algorithm,†World Appl. Sci. J., vol. 35, no. 7, pp. 1210–1215, 2017.

M. F. Zibran, “A multi-phase approach to university course timetabling.†Lethbridge, Alta.: University of Lethbridge, Faculty of Arts and Science, 2007, 2007.

I. Méndez-Díaz, P. Zabala, and J. J. Miranda-Bront, “An ILP based heuristic for a generalization of the post-enrollment course timetabling problem,†Comput. Oper. Res., vol. 76, pp. 195–207, 2016.

A. Shatnawi, M. Fraiwan, and H. S. Al-Qahtani, “Exam scheduling: A case study,†in 2017 Ninth International Conference on Advanced Computational Intelligence (ICACI), 2017, pp. 137–142.

S. Kumar, “Solving University Course Timetabling Problem Using AHP Method.,†IUP J. Comput. Sci., vol. 10, 2016.

J. Wahid and N. M. Hussin, “Combination of graph heuristics in producing initial solution of curriculum based course timetabling problem,†in AIP Conference Proceedings, 2016, vol. 1761, no. 1, p. 20104.




DOI: http://dx.doi.org/10.18517/ijaseit.10.3.10233

Refbacks

  • There are currently no refbacks.


Published by INSIGHT - Indonesian Society for Knowledge and Human Development