Two Competing Queues with Linear Costs and Geometric Service Requirements

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 queue sizes. Under the model assumptions, a fixed prioritization scheme known as the µc-rule, is shown to be optimal for the long run average criterion and for the expected discounted-criterion, over both finite and infinite horizons. Two different approaches are proposed to solve these problems. One is based on dynamic programming methodology for Markov decision processes and assumes the arrival to be i.i.d. The other is valid under no additional assumptions on the arrival streams and uses direct comparison arguments. In both cases, the sample path properties of the adopted state-space model are exploited.