Improving Hyper-heuristic Performance for Job Shop Scheduling Problems Using Neural Networks

Abstract

Job Shop Scheduling problems have become popular because of their many industrial and practical applications. Among the many solving strategies for this problem, selection hyper-heuristics have attracted attention due to their promising results in this and similar optimization problems. A selection hyper-heuristic is a method that determines which heuristic to apply at given points of the problem throughout the solving process. Unfortunately, results from previous studies show that selection hyper-heuristics are not free from making wrong choices. Hence, this paper explores a novel way of improving selection hyper-heuristics by using neural networks that are trained with information from existing selection hyper-heuristics. These networks learn high-level patterns that result in improved performance concerning the hyper-heuristics they were generated from. At the end of the process, the neural networks work as hyper-heuristics that perform better than their original counterparts. The results presented in this paper confirm the idea that we can refine existing hyper-heuristics to the point of being able to defeat the best possible heuristic for each instance. For example, one of our experiments generated one hyper-heuristic that produced a schedule that reduced the makespan of the one obtained by a synthetic oracle by ten days.

Xavier F. C. Sánchez Díaz

PhD candidate in Artificial Intelligence

PhD candidate in Artificial Intelligence at the Department of Computer Science (IDI) of the Norwegian University of Science and Technology