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.
References (44)
- 1 Simulated Annealing [DOI]
- 2 Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning [DOI]
- 3 A Survey of Automated Timetabling [DOI]
- 4 An introduction to timetabling [DOI]
- 5 A survey of search methodologies and automated system development for examination timetabling [DOI]
- 6 A survey of metaheuristic-based techniques for University Timetabling problems [DOI]
- 7 A robust simulated annealing based examination timetabling system [DOI]
- 8 Tuning Genetic Algorithm Parameters to Improve Convergence Time [DOI]
- 9 Local search techniques for large high school timetabling problems [DOI]
- 10 A survey of school timetabling research [DOI]
- 11 Computer-aided school and university timetabling: The new wave [DOI]
- 12 An XML format for benchmarks in High School Timetabling [DOI]
- 13 School timetabling for quality student and teacher schedules [DOI]
- 14 Solving effectively the school timetabling problem using particle swarm optimization [DOI]
- 15 Mathematical models and algorithms for a high school timetabling problem [DOI]
- 16 A genetic algorithm selection perturbative hyper-heuristic for solving the school timetabling problem [DOI]
- 17 Timetable construction - an annotated bibliography [DOI]
- 18 Techniques for Producing School Timetables on a Computer and their Application to other Scheduling Problems [DOI]
- 19 University Timetabling: Bridging the Gap between Research and Practice
- 20 A mixed-integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations [DOI]
- 21 Knowledge based genetic algorithm for dynamic route selection [DOI]
- 22 A Language for Specifying Complete Timetabling Problems [DOI]
- 23 Parallelizing simulated annealing algorithms based on high-performance computer [DOI]
- 24 A SA-VNS approach for the High School Timetabling Problem [DOI]
- 25 The Third International Timetabling Competition
- 26 An integer linear programming model of a school timetabling problem [DOI]
- 27 School Timetabling Using Heuristic Search [DOI]
- 28 A GRASP-Tabu Search Algorithm for Solving School Timetabling Problems [DOI]
- 29 New Approaches for the School Timetabling Problem [DOI]
- 30 Comparing Solution Approaches for a Complete Model of High School Timetabling
- 31 A Simulated Annealing Based Approach to the High School Timetabling Problem [DOI]
- 32 Development of a Modified Simulated Annealing to School Timetabling Problem [DOI]
- 33 The Impact of compactness requirements on the resolution of high school timetabling problem [DOI]
- 34 SAT-Based Approaches for the General High School Timetabling Problem [DOI]
- 35 Towards an XML-Based Standard for Timetabling Problems: TTML [DOI]
- 36 A standard data format for timetabling instances [DOI]
- 37 A Cultural Algorithm with Operator Parameters Control for Solving Timetabling Problems [DOI]
- 38 Modeling high school timetabling with bitvectors [DOI]
- 39 A tool for school timetabling
- 40 The Study of SVM Optimized by Culture Genetic Algorithm on Predicting Financial Distress [DOI]
- 41 Multi-population genetic algorithm quality assessment implementing intuitionistic fuzzy logic
- 42 Solving High School Timetabling with Satisability Modulo Theories
- 43 On Multi-Objective Optimization Heuristics for Nurse Rostering Problem
- 44 A Comparative Evaluation of Metaheuristic Approaches to the Problem of Curriculum-Based Course Timetabling
Cited by 15
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
Showing 9 of 15 known citations — external sources report more than can currently be individually listed.
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.
36
Page views
0
PDF downloads
2
Outbound clicks
15
Citations
Views over time
Views by country
Approximate, from request IP at view time — not citizenship or institution. Countries with fewer than 5 views are grouped as "Other".
Traffic sources
Referring site, by host.
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.