Dynamic control of a queue with adjustable service rate

We consider a single-server queue with Poisson arrivals, where holding cost s are continuously incurred as a nondecreasing function of the queue length . The queue length evolves as a birth-and-death process with constant arriv al rate lambda = 1 and with state-dependent service rates mu (n) that can b e chosen from a fixed subset A of [0, infinity). Finally, there is a nondec reasing cost-of-effort function c(.) on A, and service costs are incurred a t rate c(g.) when the queue length is n. The objective is to minimize avera ge cost per time unit over an infinite planning horizon. The standard optim ality 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 transpa rent 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 bo unded. From a managerial standpoint it is natural to compare z*, the minimu m average cost achievable with state-dependent service rates, against the m inimum average cost achievable with a single fixed service rate. The differ ence between those two minima represents the economic value of a responsive service mechanism, and numerical examples are presented that show it can b e substantial.