On the Computational Complexity of Stochastic Scheduling Problems,

Abstract

In this paper we consider stochastic scheduling models where all relevant data (like processing times, release dates, due dates, etc.) are independent random variables, exponentially distributed. We are interested in the computational complexity of determining optimal policies for these stochastic scheduling models. We give a number of examples of models in which the optimal policies can be determined by polynomial time algorithms while the deterministic counterparts of these models are NP-complete. We also give some examples of stochastic scheduling models for which there exists no polynomial time algorithm if P is not equal NP. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1981
Accession Number
ADA108089

Entities

People

  • Michael Pinedo

Organizations

  • Georgia Tech

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Computations
  • Distribution Functions
  • Dynamic Programming
  • Engineering
  • Linear Programming
  • Military Research
  • Polynomials
  • Probability
  • Production Engineering
  • Production Management Methods
  • Random Variables
  • Scheduling (Production)
  • Sequences

Fields of Study

  • Mathematics

Readers

  • Operations Research