Relevant Policies for Markovian Queueing Systems with Many Types of Service

A single station service system with bounded queue capacity operates in discrete time, and at each period, one out of K possible service rates is used. A subclass of the stationary nonrandomized policies—termed relevant—which uses only a subset of the available service rates, is proved optimal for the average cost criterion. If there is some type of service whereby the expected cost per served customer is no more than the expense of losing him, the service rate in all relevant policies increases with the number of customers observed in the system; if there is no such type of service, the service rate in all relevant policies decreases with the number of observed customers.