Dynamic control of a queue with adjustable service rate

We consider a single-server queue with Poisson arrivals, where holding costs are continuously incurred as a nondecreasing function of the queue length. The queue length evolves as a birth-and-death process with constant arrival rate lambda = 1 and with state-dependent service rates mu (n) that can be chosen from a fixed subset A of [0, infinity). Finally, there is a nondecreasing cost-of-effort function c(.) on A, and service costs are incurred at rate c(g.) when the queue length is n. The objective is to minimize average cost per time unit over an infinite planning horizon. The standard optimality equation of average-cost dynamic programming allows one to write out the optimal service rates in terms of the minimum achievable average cost z*. Here we present a method for computing z* that is so fast and so transparent it may be reasonably described as an explicit solution for the problem of service rate control. The optimal service rates are nondecreasing as a function of queue length and are bounded if the holding cost function is bounded. From a managerial standpoint it is natural to compare z*, the minimum average cost achievable with state-dependent service rates, against the minimum average cost achievable with a single fixed service rate. The difference between those two minima represents the economic value of a responsive service mechanism, and numerical examples are presented that show it can be substantial.