Evaluating the Potential of Reinforcement Learning for Stochastic Machine Scheduling Problems

Finding a policy for stochastic scheduling problems on parallel machines is a complicated task, as the problem is already NP-hard in the deterministic case. The problem becomes even more challenging in the unrelated machines environment, where the processing time of a job depends on the machine where it is executed. This article proposes an approach based on reinforcement learning to tackle this class of problems. In this study, we apply supervised learning to train a neural network able to handle small instances, using training data obtained by solving a set of instances to optimality, by dynamic programming. Different representations of the stochastic information in the training data are investigated. Our experiments show that the policy derived from the neural network outperforms the state-of-the-art heuristics used in this field, and produce schedules with expected costs within 1% of the true optimal policy. Moreover, the resulting policy generalizes well to stochastic instances with probability distributions of job durations other than those for which it has been trained, as well as instances with more jobs and machines.