Improving Hyper-heuristic Performance for Job Shop Scheduling Problems Using Neural Networks
| Autor: | José Carlos Ortiz-Bayliss, Xavier Sánchez-Díaz, Erick Lara-Cárdenas, Iván Amaya |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Schedule
021103 operations research Optimization problem Artificial neural network Job shop scheduling Heuristic Computer science business.industry 0211 other engineering and technologies 02 engineering and technology Oracle 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Artificial intelligence Hyper-heuristic business Selection (genetic algorithm) |
| Zdroj: | Advances in Soft Computing ISBN: 9783030337483 MICAI |
| DOI: | 10.1007/978-3-030-33749-0_13 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|