Dominant strategies in stochastic allocation and scheduling problems

R.R. Weber and P. Nash, In M.A.H. Dempster, J.K. Lenstra, and A.H.G. Rinnooy Kan, editors, Deterministic and Stochastic Scheduling pages 343-353. Reidel, 1982.


Some problems of stochastic allocation and scheduling have the property that
there is a single strategy which minimizes the expected value of the costs
incurred up to every finite time horizon.  We present a sufficient condition
for this to occur in the case where the problem can be modelled as a Markov
decision process with costs depending only on the state of the process.  The
condition is used to establish the nature of the optimal strategies for problems 
of customer assignment, dynamic memory allocation, optimal gambling, maintenance 
and scheduling.

back to list of papers