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 λ = 1 and with state-dependent service rates μ n that can be chosen from a fixed subset A of [0, ∞). Finally, there is a nondecreasing cost-of-effort function c(·) on A, and service costs are incurred at rate c(μ 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 ζ*. Here we present a method for computing ζ* 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 ζ*, 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.