Job Shop Production Planning under Uncertainty: A Monte Carlo Rollout Approach
DOI:
https://doi.org/10.17770/etr2015vol3.617Keywords:
OPTIMIZATION UNDER UNCERTAINTY, ROBUST OPTIMIZATION, MONTE CARLO ROLLOUT METHOD, COMBINATORIAL PROBLEMS, SCHEDULING PROBLEMAbstract
The Monte Carlo Rollout method (MCR) is a novel approach to solve combinatorial optimization problems with uncertainties approximatively. It combines ideas from Rollout algorithms for combinatorial optimization and the Monte Carlo Tree Search in game theory. In this paper the results of an investigation of applying the MCR to a Scheduling Problem are shown. The quality of the MCR method depends on the model parameters, search depth and search width, which are strong linked to process parameters. These dependencies are analyzed by different simulations. The paper also deals with the question whether the Lookahead Pathology occurs.
Downloads
References
M. Rosner: Untersuchung des Monte-Carlo-Rollout-Verfahrens fuer Optimierungsprobleme unter Ungewissheit, Diplomarbeit TU Dresden, 2013.
D.P. Bertsekas, J.N. Tsitsiklis, C. Wui: Rollout Algorithms for Combinatorial Optimization, Journal of Heuristics, 3, 245–262, 1997.
D.P. Bertsekas, D. A. Castanon: Rollout Algorithms for Stochastic Scheduling Problems, Journal of Heuristics, 5, 89-108, 1999.
G. Chaslot, S. Bakkes, I. Szita, P. Spronck: Monte-Carlo Tree Search: A New Framework for Game AI, Proceedings of the Fourth Artificial Intelligence and Interactive Digital Entertainment Conference, 5, 216-217., 2008.
L. Kocsis, C. Szepesvari: Bandit based Monte-Carlo Planning,
ECML-06. Number 4212 in LNCS, Springer, 5, 282-293, 2006.
B. Brügman: Monte Carlo Go,1993
C. Browne, E.J. Powley, D. Whitehouse, S.M. Lucas, P.I. Cowling, P.Rohlfshagen, S. Tavener, D. Perez, S.Samothrakis, S. Colton: A survey of Monte Carlo tree search methods, IEEE Trans. Comput. Intell. AI Games, 4, 1, 2012.
