Best Paper Award at ICAPS: Lucas Kletzander & Nysret Musliu
Lucas Kletzander and Nysret Musliu won the ICAPS 2022 Best Industry and Applications Track Paper Award.
Lucas Kletzander and Nysret Musliu from the Research Unit for Databases and Artificial Intelligence won the ICAPS 2022 Best Industry and Applications Track Paper Award for their paper “Hyper-Heuristics for Personnel Scheduling Domains”.
The 32nd International Conference on Automated Planning and Scheduling (ICAPS), held online from June 13-24, 2022, is the premier forum for exchanging news and research results on theory and applications of intelligent and automated planning and scheduling technology.
In real-life applications problems can frequently change or require small adaptations. Manually creating and tuning algorithms for different problem domains or different versions of a problem can be cumbersome and time-consuming. In this paper we consider several important problems with high practical relevance, which are Bus Driver Scheduling, Rotating Workforce Scheduling, and Minimum Shift Design. Instead of designing very specifc solution methods, we propose to use the more general approach based on hyper-heuristics which take a set of simpler low-level heuristics and combine them to automatically create a ftting heuristic for the problem at hand.
This paper presents a major study on applying hyper-heuristics to these domains, which contributes in three different ways: First, it defnes new low-level heuristics for these scheduling domains, allowing to apply hyper-heuristics to them for the frst time. Second, it provides a comparison of several state-of-the-art hyper-heuristics on those domains. Third, new best solutions for several instances of the different problem domains are found. These results show that hyper-heuristics are able to perform well even on very complex practical problem domains in the area of scheduling and, while being more general and requiring less problem-specifc adaptation, can in several cases compete with specialized algorithms for the specifc problems. These results help to improve industrial systems in use for solving different scheduling scenarios by allowing faster and easier adaptation to new problem variants.