Skip to Main content Skip to Navigation
New interface
Conference papers

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

Thomas Philip 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Marc Schoenauer Connect in order to contact the contributor
Submitted on : Monday, October 1, 2012 - 7:03:37 AM
Last modification on : Tuesday, October 25, 2022 - 4:20:09 PM
Long-term archiving on: : Friday, December 16, 2016 - 6:57:00 PM


Files produced by the author(s)


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


Thomas Philip Runarsson, Marc Schoenauer, Michèle Sebag. Pilot, Rollout and Monte Carlo Tree Search Methods for Job Shop Scheduling. Learning and Intelligent OptimizatioN (LION'6), Jan 2012, Paris, France. pp.408-423. ⟨hal-00736968⟩



Record views


Files downloads