Hyper-Heuristics and Scheduling Problems: Strategies, Application Areas, and Performance Metrics

Abstract

Scheduling problems, which involve allocating resources to tasks over specified time periods to optimize objectives, are crucial in various fields. This work presents hyper-heuristic applications for scheduling problems, analyzing 215 peer-reviewed publications over the last decade. We categorize and examine the prevailing strategies and configurations of hyper-heuristics, mainly focusing on their application across diverse scheduling scenarios such as job shop, flow shop, timetabling, and project scheduling. Our findings reveal a strong inclination towards selection and perturbative hyper-heuristics, with evolutionary computation emerging as the most commonly employed technique in this context, particularly in job shop and timetabling problems. Despite the robust development in hyper-heuristic methodologies, our analysis indicates an under-representation of multi-objective optimization and a limited use of performance metrics beyond makespan and tardiness. We also identify potential areas for future research, such as expanding hyper-heuristic applications to underexplored industries and exploring less conventional performance metrics. By providing a comprehensive overview of the current landscape and outlining future research directions, we aim to guide and inspire ongoing innovations in scheduling problem research.

Keywords

• Combinatorial optimization problems
• hyper-heuristics
• job shop scheduling
• scheduling problems