Beyond Hyper-Heuristics: A Squared Hyper-Heuristic Model for Solving Job Shop Scheduling Problems

Abstract

Hyper-heuristics (HHs) stand as a relatively recent approach to solving optimization problems. There are different kinds of HHs. One of them deals with how low-level heuristics must be combined to deliver an improved solution to a set of problem instances. Literature commonly refers to them as selection hyper-heuristics. One of their advantages is that the strengths of each heuristic can be fused into a high-level solver. However, one of their drawbacks is that sometimes this generalization scheme does not suffice. Additionally, it is not easy to reuse these HHs since the model cannot be easily tweaked. So, in this work, we develop a hyper-heuristic model with an additional layer of generalization. The rationale behind it is to preserve the general structure of selecting an adequate solver for a particular situation but to use HHs instead of low-level heuristics. We call this model a Squared Hyper-Heuristic (SHH). To validate our proposal, we pursue a four-stage methodology that covers several testing scenarios. Our data reveal that, under proper conditions, our model can outperform the base HHs. Moreover, it is flexible enough to allow for an increased number of layers so that the complexity of the final model can be tuned. Additionally, different kinds of instances can be used to train each stage of the model, thus setting the groundwork for developing a transfer learning approach for hyper-heuristics.

Keywords

• Job shop scheduling problem
• heuristics
• hyper-heuristics
• optimization
• problem features
• squared hyper-heuristics