Rollout algorithms for stochastic scheduling problems
type: Item
instance of: scholarly article
title: Rollout algorithms for stochastic scheduling problems
zbMATH Open document ID: 0997.90037
DOI: 10.1023/A:1009634810396
author: Dimitri P. Bertsekas
author: David A. Castanon
published in: Journal of Heuristics
publication date: 1999-12-20T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90B36
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 90C15
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 1358179
zbMATH Keywords: stochastic scheduling problems
zbMATH Keywords: deterministic quiz problems
zbMATH Keywords: stochastic quiz problems
zbMATH Keywords: dynamic programming
zbMATH Keywords: rollout
zbMATH Keywords: suboptimal solution algorithms
zbMATH Keywords: heuristic approach
zbMATH Keywords: Monte Carlo simulation
zbMATH Keywords: computational experiments
reviewed by: Vlasta Kaňková
MaRDI profile type: Publication
full work available at URL: a:1009634810396
OpenAlex ID: W3016548437
Recommended article: Analysis of a rollout approach to sequencing problems with stochastic routing applications
Recommended article: On a stochastic sequencing and scheduling problem
Recommended article: Q4354035
Recommended article: Q4858587
Recommended article: Rearrangement, Majorization and Stochastic Scheduling
Recommended article: Optimal stochastic scheduling
Recommended article: Q3683873
Recommended article: Rollout algorithms for combinatorial optimization
Recommended article: A stochastic batching and scheduling problem
description: scientific article; zbMATH DE number 1358179