Dominant Strategies in Stochastic Allocation and Scheduling Problems

Some problems of stochastic allocation and scheduling have the property that there is a single strategy which minimizes the expected value of the cos ts incurred up to every fi ni te time hori zon. We present a sufficient condition for this to occur in the case where the problem can be modelled by 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~ 1. DOMINANT STRATEGIES The aim in many stochastic allocation and scheduling problems is to attain a desired state at the least possible cost. In job scheduling problems one may want to minimize the expected value of the makespan or flowtirne. In a reliability problem one may want to minimize the expected repair costs. Some problems of this type have the special property that there exists a single strategy which not only minimizes the expected cost of reaching the desired state, but also minimizes the expected value of the cost incurred at e~ery time. A strategy with this property shall be called expectation dominant ( ED). A s t rat egy wi 11 be calI ed s t 0 chas ti c d0minant (SD) iff0 r alI times t it minimizes in distribution the cost incurred at time t. Weeks and Wingler [14J have argued that stochastic dominance is the property most desired in a scheduling strategy. To give an example of a problem in which the optimal strateg