Monte Carlo Tree Search for Job Shop Scheduling Problems

Scheduling Probleme sind Problemstellungen, denen man häufig in der Industrie begegnet. Beispiele dafür sind Personalplanung, Maschinenbelegungsplanung oder auch die Zuweisung von Zügen zu Gleisen. Die Aufgabe ist es, eine bestimmte Anzahl von Objekten einer bestimmten Anzahl von Ressourcen unter Berücksichtigung der entsprechenden benötigten Kapazitäten zuzuweisen. Je größer die Anzahl an Objekten und die Anzahl an Ressourcen ist, desto schwieriger wird es, eine solche Zuteilung zu finden. Außerdem erschweren oft zusätzliche Randbedingungen das Lösen eines solchen Scheduling Problems. Heutzutage wird versucht, Scheduling Probleme mittels unterschiedlicher Algorithmen zu lösen, um Zeit, Kosten oder auch Energie zu sparen. In dieser Arbeit wird Monte Carlo Tree Search, eine Methode des Reinforcement Learning, angewandt, um speziell Job Shop Scheduling Probleme zu lösen. Dabei werden zwei unterschiedliche Evaluierungsmethoden (Threshold Ascent und Upper Confidence Bound for Trees) getestet und miteinander verglichen. Schließlich werden die gefundenen Schedules mit den optimalen verglichen und Aussagen über ihre Effektivität und Effizienz getroffen.