Forced Periodic Optimal Scheduling Policy for Graph Reinforcement Learning

Efficient scheduling is fundamental when tackling large and complex industrial problems. Heuristic methods provide good enough solutions quickly, but their potential is limited. Exact methods and metaheuristics can reach very good results but might require prohibitively high computational times. Alternatively, a reinforcement learning agent can explore an environment by trial and error and create solutions based on the current environment state. This paper proposes periodically replacing the current agent policy with an optimal policy, which can be obtained by using exact methods on moderate sized problems or from known benchmark solutions. This results in a better final policy, even for problems slightly larger than those of the original training dataset. The scheduling problem is encoded as a graph. The agent is a graph neural network trained with Proximal Policy Optimization. Note that a single trained model can solve problems of any size. Results show that the trained agent can outperform heuristics. Also, it is competitive with other reinforcement learning approaches when solving problems in the order of magnitude of the training instances.