Investigating Hyper-heuristics for Real-World Test Laboratory Scheduling

Abstract

Selection hyper-heuristics are a class of high-level problem solving methods that operate on a set of problem-specific low-level operators, instead of directly over a solution space. This allows them to be adaptive and problem-independent, even for previously unknown problem domains. One such domain is the Test Laboratory Scheduling Problem (TLSP), which is an extension of the well-known RCPSP. In the TLSP, solvers have to produce a schedule by first grouping tasks into jobs and then assigning a mode, time slot, and resources to the jobs. We have modeled the TLSP as a problem domain for selection hyper-heuristics, using the HyFlex framework, which has become the de-facto standard in this area. This includes defining a solution representation and evaluation function, as well as a diverse portfolio of low-level operators of different types, including large neighborhood operators. Using a newly developed and problem-independent hyper-heuristic based on reinforcement learning, we were able to find high-quality solutions for the TLSP that are competitive with the current state of the art and could even improve the results for some instances. In addition, our hyper-heuristics produce good results on both small and large instances, compared to the existing problem-specific approaches, whose performance depends a lot on the instance size. We could further show the generality of our approach by achieving high scores on the original problem domains contained in HyFlex, which contain a selection of the most well-known NP-complete optimization problems.