Dynamic Scheduling of Three Queues in Tandem

Three queues in tandem compete for a single server. At each instant of time the cost is a weighted sum of the number of customers in the queues. The problem of finding the optimal control policy is the dual of the celebrated problem of dynamically scheduling a number of queues in parallel which share a single server. We analyze the conditions for optimality, and in particular we derive the optimal policy for the infinite horizon discounted version of the problem. In doing so, we find that the optimal policy is not always myopic, which contrasts with the well known "cu" rule for the primal problem. Finally, we show that a "cu type" rule is always optimal for the long run average version of the problem.