Solving high school timetabling problems worldwide using selection hyper-heuristics
High school timetabling is one of those recurring NP-hard real-world combinatorial optimisation problems that has to be dealt with by many educational institutions periodically, and so has been of interest to practitioners and researchers. Solving a high school timetabling problem requires schedulin...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Published: |
Elsevier
2015
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/32182/ |
| _version_ | 1848794351656763392 |
|---|---|
| author | Ahmed, Leena N. Özcan, Ender Kheiri, Ahmed |
| author_facet | Ahmed, Leena N. Özcan, Ender Kheiri, Ahmed |
| author_sort | Ahmed, Leena N. |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | High school timetabling is one of those recurring NP-hard real-world combinatorial optimisation problems that has to be dealt with by many educational institutions periodically, and so has been of interest to practitioners and researchers. Solving a high school timetabling problem requires scheduling of resources and events into time slots subject to a set of constraints. Recently, an international competition, referred to as ITC 2011 was organised to determine the state-of-the-art approach for high school timetabling. The problem instances, obtained from eight different countries across the world used in this competition became a benchmark for further research in the field. Selection hyper-heuristics are general-purpose improvement methodologies that control/mix a given set of low level heuristics during the search process. In this study, we evaluate the performance of a range of selection hyper-heuristics combining different reusable components for high school timetabling. The empirical results show the success of the approach which embeds an adaptive great-deluge move acceptance method on the ITC 2011 benchmark instances. This selection hyper-heuristic ranks the second among the previously proposed approaches including the ones competed at ITC 2011. |
| first_indexed | 2025-11-14T19:14:49Z |
| format | Article |
| id | nottingham-32182 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:14:49Z |
| publishDate | 2015 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-321822020-05-04T17:11:44Z https://eprints.nottingham.ac.uk/32182/ Solving high school timetabling problems worldwide using selection hyper-heuristics Ahmed, Leena N. Özcan, Ender Kheiri, Ahmed High school timetabling is one of those recurring NP-hard real-world combinatorial optimisation problems that has to be dealt with by many educational institutions periodically, and so has been of interest to practitioners and researchers. Solving a high school timetabling problem requires scheduling of resources and events into time slots subject to a set of constraints. Recently, an international competition, referred to as ITC 2011 was organised to determine the state-of-the-art approach for high school timetabling. The problem instances, obtained from eight different countries across the world used in this competition became a benchmark for further research in the field. Selection hyper-heuristics are general-purpose improvement methodologies that control/mix a given set of low level heuristics during the search process. In this study, we evaluate the performance of a range of selection hyper-heuristics combining different reusable components for high school timetabling. The empirical results show the success of the approach which embeds an adaptive great-deluge move acceptance method on the ITC 2011 benchmark instances. This selection hyper-heuristic ranks the second among the previously proposed approaches including the ones competed at ITC 2011. Elsevier 2015-08-01 Article PeerReviewed Ahmed, Leena N., Özcan, Ender and Kheiri, Ahmed (2015) Solving high school timetabling problems worldwide using selection hyper-heuristics. Expert Systems with Applications, 42 (13). pp. 5463-5471. ISSN 0957-4174 Benchmarking; Combinatorial optimization; Competition; Heuristic methods; Scheduling Adaptive move acceptance; Adaptive operator selections; Constraint Satisfaction; Great deluge; Timetabling Optimization http://www.sciencedirect.com/science/article/pii/S0957417415001670 doi:10.1016/j.eswa.2015.02.059 doi:10.1016/j.eswa.2015.02.059 |
| spellingShingle | Benchmarking; Combinatorial optimization; Competition; Heuristic methods; Scheduling Adaptive move acceptance; Adaptive operator selections; Constraint Satisfaction; Great deluge; Timetabling Optimization Ahmed, Leena N. Özcan, Ender Kheiri, Ahmed Solving high school timetabling problems worldwide using selection hyper-heuristics |
| title | Solving high school timetabling problems worldwide using selection hyper-heuristics |
| title_full | Solving high school timetabling problems worldwide using selection hyper-heuristics |
| title_fullStr | Solving high school timetabling problems worldwide using selection hyper-heuristics |
| title_full_unstemmed | Solving high school timetabling problems worldwide using selection hyper-heuristics |
| title_short | Solving high school timetabling problems worldwide using selection hyper-heuristics |
| title_sort | solving high school timetabling problems worldwide using selection hyper-heuristics |
| topic | Benchmarking; Combinatorial optimization; Competition; Heuristic methods; Scheduling Adaptive move acceptance; Adaptive operator selections; Constraint Satisfaction; Great deluge; Timetabling Optimization |
| url | https://eprints.nottingham.ac.uk/32182/ https://eprints.nottingham.ac.uk/32182/ https://eprints.nottingham.ac.uk/32182/ |