Two Competing Queues with Linear Costs: The μc-rule is Often Optimal

A discrete-time model is presented for a system of two queues competing for the service attention of a single server with infinite buffer capacity. The service requirements are geometrically distributed and independent from customer to customer as well as from the arrivals. The allocation of service attention is governed by feedback policies which are based on past decisions and buffer content histories. The cost of operation per unit time is a linear function of the queue sizes. Under the model assumptions, a fixed prioritization scheme, known as the uc-rule, is shown to be optimal for the expected long-run average criterion and for the expected discounted criterion, over both finite and infinite horizons. Two different approaches are proposed for solving these problems. One is based on the dynamic programming methodology for Markov decision processes, and assumes the arrivals to be i.i.d. The other is valid under no additional assumption on the arrival stream and uses direct comparison arguments. In both cases, the sample path properties of the adopted state-space model are exploited.