Monte Carlo Tree Search for Job Shop Scheduling Problems

Catrin Reichenhauser

Research output: ThesisMaster's Thesis

258 Downloads (Pure)

Abstract

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.
Translated title of the contributionMonte Carlo Tree Search für Job Shop Scheduling Probleme
Original languageEnglish
QualificationDipl.-Ing.
Awarding Institution
  • Montanuniversität
Supervisors/Advisors
  • Ortner, Ronald, Supervisor (internal)
Award date15 Dec 2017
Publication statusPublished - 2017

Bibliographical note

embargoed until null

Keywords

  • Monte Carlo Tree Search
  • Upper Confidence Bound
  • Threshold Ascent
  • Job Shop Scheduling
  • Reinforcement Learning

Cite this