A Hidden Markov Model Approach to the Problem of Heuristic Selection in Hyper-Heuristics with a Case Study in High...

Area of Science:

• Operations Research
• Computer Science
• Combinatorial Optimization

Background:

• Operations research (OR) is a critical field for decision support in business and public sectors.
• Efficient solutions in OR significantly impact organizational operations.
• The high school timetabling problem is a complex OR challenge involving resource and event scheduling under constraints.

Purpose of the Study:

• To introduce a novel sequence-based selection hyper-heuristic for high school timetabling.
• To provide an easy-to-implement, maintain, and effective solution method.
• To validate the approach on a diverse benchmark of real-world timetabling instances.

Main Methods:

• Development of a sequence-based selection hyper-heuristic algorithm.
• Testing on a unified benchmark of real-world high school timetabling problems from various countries.
• Comparative analysis against existing state-of-the-art methods.

Main Results:

• The proposed hyper-heuristic achieved excellent results on the benchmark instances.
• New best-known solutions were discovered for several timetabling problems.
• The sequence-based method demonstrated superior performance compared to the state of the art.

Conclusions:

• Sequence-based selection hyper-heuristics are effective for solving high school timetabling problems.
• The developed method is practical, easy to implement, and maintain.
• This research advances the capabilities of hyper-heuristics in combinatorial optimization.