A Mathematical Programming Model and Enhanced Simulated Annealing Algorithm for the School Timetabling Problem
O. A. Odeniyi, E. O. Omidiora, S. O. Olabiyisi, C. A. Oyeleye
Asian Journal of Research in Computer Science · pp. 21–38 · Published 2 May 2020
10.9734/ajrcos/2020/v5i330136Abstract
Despite significant research efforts for School Timetabling Problem (STP) and other timetabling problems, an effective solution approach (model and algorithm) which provides boundless use and high quality solution has not been developed. Hence, this paper presents a novel solution approach for solving school timetabling problem which characterizes the problem-setting in the timetabling problem of the high school system in Nigeria. We developed a mixed integer linear programming model and meta-heuristic method - Enhanced Simulated Annealing (ESA) algorithm. Our method incorporates specific features of Simulated Annealing (SA) and Genetic Algorithms (GA) in order to solve the school timetabling problem. Both our solution approach and SA approach were implemented using Matrix Laboratory 8.6 software. In order to validate and demonstrate the performance of the developed solution approach, it was tested with the highly constrained school timetabling datasets provided by a Nigerian high school using constraints violation, simulation time and solution cost as evaluation metrics. Our developed solution approach is able to find optimal solution as it satisfied all the specified hard and soft constraints with average simulation time of 37.91 and 42.16 seconds and solution cost of 17.03 and 18.99, respectively, for JSS and SSS to the problem instance. A comparison with results obtained with SA approach shows that the developed solution approach produced optimal solution in smaller simulation time and solution cost, and has a great potential to solve school timetabling problems with satisfactory results. The developed ESA algorithm can be used for solving other related optimization problems.
Cited by 9
M. Jain, Sharanabasappa Raikoti, Samuvel J Bala · 2025 International Conference on Information, Implementation, and Innovation in Technology (I2ITCON) · 2025
Tio Arya Dewa Prakasa, A. Muklason, I. Gusti Agung Premananda · International Seminar on Intelligent Technology and Its Applications · 2024
Frank Werner, Ioannis X. Tassopoulos, Christina A. Iliopoulou · Algorithms · 2023
Zhe Sun, Qinghua Wu · Data Science and Management · 2023
Kaixiang Zhu, Lily D. Li, Michael Li · Mathematics · 2021
T. Pencheva, Maria Angelova, E. Sotirova · Mathematics · 2021
M. Akkilic, Eren Ozceylan · Proceedings of the International Conference on Industrial Engineering and Operations Management · 2021
Joo Siang Tan, S. Goh, G. Kendall · Expert systems with applications · 2021
Kaixiang Zhu, Lily D. Li, Michael Li · Mathematics · 2021
Related research
- Weather Based Pest Forewarning Model for Major Insect Pests of Rice – An Effective Way for Insect Pest Prediction — shares topic coverage
- Integration of First-order Modeled Differential Equations Using a Quarter-step Method — shares topic coverage
- Mathematical Model for Machining Time of a YAG-Rod Laser Cutting Machine — shares topic coverage
- Measurement and Modelling of Water Content Effects on Thermal Properties of Compressed Soil Building Blocks — shares topic coverage
- An Approach of Exergy Analysis of Human Physiological Response in the Outdoor Conditions during Blocklaying in Ogun State, Nigeria — shares topic coverage
Article metrics
Real usage data collected on this platform.
0
Page views
0
PDF downloads
0
Outbound clicks
9
Citations
Views by country
Approximate, from request IP at view time — not citizenship or institution. Countries with fewer than 5 views are grouped as "Other".
No views recorded yet.
Traffic sources
Referring site, by host.
No traffic recorded yet.
Views and downloads exclude known bots/crawlers. Citations combines this platform's own DOI-resolved index with each external source's own reported total — see Cited by above for individually listed citing works. Last refreshed 0 seconds ago.