TY - THES

T1 - Monte Carlo Tree Search for Job Shop Scheduling Problems

AU - Reichenhauser, Catrin

N1 - embargoed until null

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Monte Carlo Tree Search

KW - Upper Confidence Bound

KW - Threshold Ascent

KW - Job Shop Scheduling

KW - Monte Carlo Tree Search

KW - Upper Confidence Bound

KW - Threshold Ascent

KW - Job Shop Scheduling

KW - Reinforcement Learning

M3 - Master's Thesis

ER -