Final published version
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
}
TY - GEN
T1 - An online learning selection hyper-heuristic for educational timetabling
AU - Steenson, Alexander
AU - Özcan, Ender
AU - Kheiri, Ahmed
AU - McCollum, Barry
AU - McMullan, Paul
PY - 2022/8/23
Y1 - 2022/8/23
N2 - Examination and course timetabling are computationally difficult real-world resource allocation problems. In 2007, an International Timetabling Competition (ITC) consisting of three classes: (i) examination timetabling, (ii) post enrollment-based, and (iii) curriculum-based course timetabling was organised. One of the competing algorithms, referred to as CPSolver, successfully achieved the first place in two out of these three tracks. This study investigates the performance of various multi-stage selection hyper-heuristics sequencing low-level heuristics/operators extending the CPSolver framework which executes hill climbing and two well-known local search metaheuristics in stages.The proposed selection hyper-heuristic is a multi-stage approach making use of a matrix which maintains transitional probabilities between each low-level heuristic to select the next heuristic in the sequence. A second matrix tracks the probabilities of ending the sequence on a given low-level heuristic. The best configuration for the selection hyper-heuristic is explored tailoring the heuristic selection process for the given timetabling problem class. The empirical results on the ITC 2007 problem instances show that the proposed selection hyper-heuristics can reduce the number of soft constraint violations, producing improved solutions over CPSolver as well as some other previously proposed solvers, particularly, in examination and curriculum-based course timetabling.
AB - Examination and course timetabling are computationally difficult real-world resource allocation problems. In 2007, an International Timetabling Competition (ITC) consisting of three classes: (i) examination timetabling, (ii) post enrollment-based, and (iii) curriculum-based course timetabling was organised. One of the competing algorithms, referred to as CPSolver, successfully achieved the first place in two out of these three tracks. This study investigates the performance of various multi-stage selection hyper-heuristics sequencing low-level heuristics/operators extending the CPSolver framework which executes hill climbing and two well-known local search metaheuristics in stages.The proposed selection hyper-heuristic is a multi-stage approach making use of a matrix which maintains transitional probabilities between each low-level heuristic to select the next heuristic in the sequence. A second matrix tracks the probabilities of ending the sequence on a given low-level heuristic. The best configuration for the selection hyper-heuristic is explored tailoring the heuristic selection process for the given timetabling problem class. The empirical results on the ITC 2007 problem instances show that the proposed selection hyper-heuristics can reduce the number of soft constraint violations, producing improved solutions over CPSolver as well as some other previously proposed solvers, particularly, in examination and curriculum-based course timetabling.
M3 - Conference contribution/Paper
VL - I
SP - 129
EP - 146
BT - Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling
T2 - 13th International Conference on the Practice and Theory of Automated Timetabling
Y2 - 23 August 2022 through 26 August 2022
ER -