Rollout algorithms for stochastic scheduling problems

Dimitri P. Bertsekas, David A. Castanon

Research output: Contribution to journalConference articlepeer-review

9 Scopus citations


Stochastic scheduling problems are difficult stochastic control problems with combinatorial decision spaces. In this paper we focus on a class of stochastic scheduling problems, the quiz problem and its variations. We discuss the use of heuristics for their solution, and we propose rollout algorithms based on these heuristics which approximate the stochastic dynamic programming algorithm. We show how the rollout algorithms can be implemented efficiently, with considerable savings in computation over optimal algorithms. We delineate circumstances under which the rollout algorithms are guaranteed to perform better than the heuristics on which they are based. We also show computational results which suggest that the performance of the roll-out policies is near-optimal, and is substantially better than the performance of their underlying heuristics.

Original languageEnglish (US)
Pages (from-to)2143-2148
Number of pages6
JournalProceedings of the IEEE Conference on Decision and Control
StatePublished - 1998
Externally publishedYes
EventProceedings of the 1998 37th IEEE Conference on Decision and Control (CDC) - Tampa, FL, USA
Duration: Dec 16 1998Dec 18 1998

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization


Dive into the research topics of 'Rollout algorithms for stochastic scheduling problems'. Together they form a unique fingerprint.

Cite this