(344g) Decision-Making of Online Rescheduling Procedures Using Neuroevolution of Augmenting Topologies

Online scheduling requires appropriate timing of rescheduling events, as well as the determination of relevant rescheduling horizon lengths. Optimal choices of these quantities are highly dependent on the uncertainty of the scheduling environment and may vary over time. We propose an approach where a neural network is trained to make online decisions on these quantities, as well as on the choice of the rescheduling method (mathematical programming or metaheuristics). In our approach, the neural network is trained using neuroevolution of augmenting topologies (NEAT) in a simulated environment.

NEAT, developed by Stanley and Mikkulainen [1], is a genetic algorithm that simultaneously evolves the topology and weight parameters of the neural network. Such et al. [2] report the performance of the evolutionary neuroevolution algorithms to compare well against the gradient-based backpropagation algorithms. A key feature of NEAT is that the evolution process is initiated from very simple neural networks, the topological complexity of which is then incrementally increased during the evolution. This feature reduces unnecessary complexity of the final neural network, and is not possible when using gradient-based algorithms. Recently, Hausknecht et al. [3] applied NEAT to train a neural network to play 61 different Atari 2600 games, where the controls for the player are to move a joystick and press a button. The controls for our neural network are also of a similar low level of complexity (see the first paragraph), but the critical aspect is their timely execution.

In many previous studies, neural networks have been used to learn dispatching rules from the historical data of scheduling decisions [4]. However, this approach can typically only mimic the historical decisions, and therefore the optimality of the scheduling solutions is highly dependent on the quality of the given historical data. Our neural network approach operates at a higher level; it exploits the strength of mathematical programming at finding the optimal, or near-optimal solution, and focuses on the allocation of the computational resources in the changing scheduling environment.

We benchmark the approach against periodically occurring and event-triggered rescheduling on a dynamic routing problem. The approach is also extensible to rescheduling of industrial batch processes.

References:

[1] K. O. Stanley, R. Miikkulainen, 2002. Evolving neural networks through augmenting topologies. Evolutionary computation 10 (2), 99–127.

[2] F. P. Such, V. Madhavan, E. Conti, J. Lehman, K. O. Stanley, J. Clune, 2017. Deep neuroevolution: genetic algorithms are a competitive alternative for training deep neural networks for reinforcement learning. arXiv preprint arXiv:1712.06567.

[3] M. Hausknecht, J. Lehman, R. Miikkulainen, P. Stone, 2014. A neuroevolution approach to general Atari game playing. IEEE Transactions on Computational Intelligence and AI in Games 6 (4), 355–366.

[4] P. Priore, A. Gómez, R. Pino, R. Rosillo, 2014. Dynamic scheduling of manufacturing systems using machine learning: An updated review. AI EDAM 28 (1), 83–97.