Rollout algorithms for stochastic scheduling problems (Q1806711)

The paper deals with a special class of stochastic scheduling problems; the quiz problem and its variations. In particular, the variations are grouped into two classes: deterministic quiz problems and stochastic quiz problems. Examples of these are mentioned in the introduction. Clearly, both types of quiz problems can cover a rather large class of scheduling problems. The above mentioned problems can be viewed as dynamic programming problems as well (especially in the deterministic case) as deterministic combinatorial problems. A brief survey of some possible solution algorithms is given in the introduction. The aim of the paper is to propose rollout types of the (``suboptimal'') solution algorithms for both types of problems. They are based on the heuristic approach; the basic idea (in the deterministic case) can be seen to be relatively simple. In the stochastic case the problem can be viewed in terms of (stochastic) dynamic programming. Monte Carlo simulation seems to be suitable in this case. However, the scenario approaches must be employed in many cases. The last section of the paper is devoted to computational experiments with stochastic quiz problems.