Bertsekas, Dimitri P.; Castañon, David A. Rollout algorithms for stochastic scheduling problems. (English) Zbl 0997.90037 J. Heuristics 5, No. 1, 89-108 (1999). 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. Reviewer: V.Kaňková (Praha) Cited in 28 Documents MSC: 90B36 Stochastic scheduling theory in operations research 90C39 Dynamic programming 90C15 Stochastic programming 90C59 Approximation methods and heuristics in mathematical programming Keywords:stochastic scheduling problems; deterministic quiz problems; stochastic quiz problems; dynamic programming; rollout; suboptimal solution algorithms; heuristic approach; Monte Carlo simulation; computational experiments PDFBibTeX XMLCite \textit{D. P. Bertsekas} and \textit{D. A. Castañon}, J. Heuristics 5, No. 1, 89--108 (1999; Zbl 0997.90037) Full Text: DOI