Keywords: optimization under uncertainty, robust optimization, Monte Carlo rollout method, combinatorial problems, scheduling problem, bin packing problem.

To optimize a combinatorial problem one can use complex algorithms, e.g. branch- and-bound algorithms. However, these are time consuming for extensive problems. By the need of real-time decisions in industrial applications, complex algorithms are inapplicable. Additionally, as a consequence of changes, solutions have to be calculated very often to adapt plans to the changes. Another aspect that makes a fast solution necessary. The Monte Carlo rollout method (MCR) is a novel approach for the approximate solution of combinatorial optimization problems. The MCR approach 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 repairing bin packing problem and a scheduling problem are shown. Influences of the model parameters, search depth and search width, are examined as well as the influence of process parameters. It also deals with the question as to whether the Lookahead Pathology occurs as identified in game theory.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £75 +P&P)