Monte Carlo Tree Search for Job Shop Scheduling Problems

Scheduling problems are among the most common problems in industry. They deal with the allocation of a number of objects to a number of resources. Examples are human resource planning, machine scheduling, or the allocation of arriving trains to station platforms. These problems can be simple, if for example the number of objects and resources is very small and if there are no further constraints. But the higher the number of objects or resources and the more constraints have to be considered, the more difficult the problems become. Different algorithms try to solve such problems in order to reduce costs, time, or energy and to increase quality and performance. In this master thesis the Reinforcement Learning method Monte Carlo Tree Search is used for solving Job Shop Scheduling problems. In particular, as evaluation functions we use the bandit algorithms Upper Confidence Bound for Trees and Threshold Ascent. These methods are tested on a set of Job Shop Scheduling problems.