Rollout Algorithms for Stochastic Scheduling Problems

Abstract

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, and we delineate circumstances under which they 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 rollout policies is near-optimal, and is substantially better than the performance of their underlying heuristics.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1998
Accession Number
ADA459559

Entities

People

  • D. P. Bertsekas
  • David A. Castañón

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computational Complexity
  • Computations
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Dynamic Programming
  • Electrical Engineering
  • Engineering
  • Information Processing
  • Monte Carlo Method
  • Probability
  • Q Factor
  • Random Variables
  • Scheduling (Production)
  • Simulations

Fields of Study

  • Computer science

Readers

  • Operations Research

Technology Areas

  • Space