Pilot, Rollout and Monte Carlo Tree Search Methods for Job Shop Scheduling

Thomas Runarsson 1 Marc Schoenauer 2, 3 Michèle Sebag 3
1 School of Engineering and Natural Sciences
University of Iceland [Reykjavik]
2 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : Greedy heuristics may be attuned by looking ahead for each possible choice, in an approach called the rollout or Pilot method. These methods may be seen as meta-heuristics that can enhance (any) heuristic solution, by repetitively modifying a master solution: similarly to what is done in game tree search, better choices are identified using lookahead, based on solutions obtained by repeatedly using a greedy heuristic. This paper first illustrates how the Pilot method improves upon some simple well known dispatch heuristics for the job-shop scheduling problem. The Pilot method is then shown to be a special case of the more recent Monte Carlo Tree Search (MCTS) methods: Unlike the Pilot method, MCTS methods use random completion of partial solutions to identify promising branches of the tree. The Pilot method and a simple version of MCTS, using the $\varepsilon$-greedy exploration paradigms, are then compared within the same framework, consisting of 300 scheduling problems of varying sizes with fixed-budget of rollouts. Results demonstrate that MCTS reaches better or same results as the Pilot methods in this context.
Type de document :
Communication dans un congrès
Youssef Hamadi and Marc Schoenauer. Learning and Intelligent OptimizatioN (LION'6), Jan 2012, Paris, France. Sringer Verlag, 7219, pp.408-423, 2012, Learning and Intelligent OptimizatioN (LION'6) - Selected papers
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00736968
Contributeur : Marc Schoenauer <>
Soumis le : lundi 1 octobre 2012 - 07:03:37
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 18:57:00

Fichiers

mctscomb.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00736968, version 1
  • ARXIV : 1210.0374

Collections

Citation

Thomas Runarsson, Marc Schoenauer, Michèle Sebag. Pilot, Rollout and Monte Carlo Tree Search Methods for Job Shop Scheduling. Youssef Hamadi and Marc Schoenauer. Learning and Intelligent OptimizatioN (LION'6), Jan 2012, Paris, France. Sringer Verlag, 7219, pp.408-423, 2012, Learning and Intelligent OptimizatioN (LION'6) - Selected papers. 〈hal-00736968〉

Partager

Métriques

Consultations de la notice

415

Téléchargements de fichiers

757