Influence of Instance Size on Selection Hyper-Heuristics for Job Shop Scheduling Problems

摘要

Hyper-heuristics stand as a novel tool that combines low-level heuristics into robust solvers. However, training cost is a drawback that hinders their applicability. In this work, we analyze the effect of training with different problem sizes, to determine whether an effective simplification can be made. We train selection hyper-heuristics for the Job Shop Scheduling problem through Simulated Annealing. Results from preliminary experiments suggest that the aforementioned simplification is feasible. To better understand such an effect, we carry out experiments training on two different instance sizes, 5 × 5 and 15×15, while testing on instances of size 15 × 15. Our data show that hyper-heuristics trained in small-sized instances perform similarly to those trained in larger problems. Thus, we discuss a possible explanation for this effect.