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 ((mu) n ) 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 (zeta)*. Here we present a method for computing (zeta)* 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 (zeta)*, 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.