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

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...