Job Shop Production Planning under Uncertainty: A Monte Carlo Rollout Approach

Axel Simroth, Denise Holfeld, Renè Brunsch

Abstract


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. 


Keywords


OPTIMIZATION UNDER UNCERTAINTY; ROBUST OPTIMIZATION; MONTE CARLO ROLLOUT METHOD; COMBINATORIAL PROBLEMS; SCHEDULING PROBLEM

Full Text:

PDF

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.




DOI: http://dx.doi.org/10.17770/etr2015vol3.617

Refbacks

  • There are currently no refbacks.


SCImago Journal & Country Rank