Routing in queueing networks under imperfect information: stochastic dominance and thresholds

Publisher Website
Google Scholar
Abstract
Optimal policies for routing between two servers under imperfect information is treated by discrete time dynamic programming. It is proved that certain inequalities involving stochastic ordering of information measures can be propagated inductively from one epoch to the next. Convexity conditions on the instantaneous costs insure proper initiation and inductive continuation of these properties. Consequently, an inductive procedure shows that threshold routing policies are optimal, and that the total cost is convex and monotone. Two examples are provided. The first deals with a tandem queue having inputs to both work stations, and only inferential information available on the state of the second station. It is first shown that the optimal control is bang-bang, and then that the hypotheses dictating a threshold policy resulting in convex and monotone costs are satisfied. The second example considers optimal routing for customers arriving in a renewal stream, when the routing decision is between two parallel exponential servers, and the observations are both delayed and subject to random errors. It is again shown that the optimal policy is of the threshold type, and that the costs are monotone and convex.

This publication has 11 references indexed in Scilit: