A hybrid adaptive harmony search with modified great deluge algorithm for school timetabling
High school timetabling problem (HSTP) is an important NP-complete problem to generate a weekly-based timetable for classes, avoiding conflict of teachers and timeslots, which has been actively researched spanning many decades to this day. Harmony Search Algorithm (HSA) is one superior metaheuristic...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://etd.uum.edu.my/12057/2/s904147_01.pdf https://etd.uum.edu.my/12057/ |
| Abstract | Abstract here |
| Summary: | High school timetabling problem (HSTP) is an important NP-complete problem to generate a weekly-based timetable for classes, avoiding conflict of teachers and timeslots, which has been actively researched spanning many decades to this day. Harmony Search Algorithm (HSA) is one superior metaheuristic method to solve timetabling problem due to its search efficiency and less parameters settings. However, previous studies often overlooked some crucial factors on the interaction among parameters that control the balance between exploration and exploitation during the search process. Due to the unbalance exploration and exploitation, the search unable to jump out of local optima that deteriorate the solution quality. This research enhances HSA by hybridizing it with the Great Deluge Algorithm (GDA) using a four-phase methodology. In Phase 1, heuristic rules refine the time assignment stage to improve an existing construction algorithm. Phase 2 adaptively tunes parameters based on iteration position, solution number, behavioral status, and parameter linkages. Phase 3 enhances search diversity by integrating HSA and GDA, and Phase 4 evaluates the algorithms on benchmark and real-world datasets. Computational results demonstrate that the improved constructive model generates better initial solutions. The adaptive HSA and hybrid HSA-GDA further enhance solution quality, with the adaptive HSA achieving best-known solutions for 12.8% of instances (5/39) and tying in 10.3% (4/39), while the hybrid approach attains best-known solutions in 10.3% (4/39) and ties in 10.3% (4/39) against state-of-the-art methods. In conclusion, the proposed algorithms significantly improve HSTP solutions, demonstrating their superiority and establishing them as effective strategies for solving complex optimization problems, particularly in high school timetabling. |
|---|