Optimal control of service rates in networks of queues

TLDR

The study considers a cycle of M/1 queues with customers moving around the cycle. The authors prove monotonicity results for optimal service‑rate and arrival‑rate control in queueing networks. They model each queue with a convex holding cost and a controllable service rate, incurring a cost for the chosen rate. The optimal policy has a monotone structure, but this property can fail under average‑cost criteria or when zero service rates are unavailable, and convex holding costs cannot always be relaxed.

Abstract

We prove a monotonicity result for the problem of optimal service rate control in certain queueing networks. Consider, as an illustrative example, a number of ·/ M /1 queues which are arranged in a cycle with some number of customers moving around the cycle. A holding cost h i ( x i ) is charged for each unit of time that queue i contains x i customers, with h i being convex. As a function of the queue lengths the service rate at each queue i is to be chosen in the interval , where cost c i ( μ ) is charged for each unit of time that the service rate μis in effect at queue i. It is shown that the policy which minimizes the expected total discounted cost has a monotone structure: namely, that by moving one customer from queue i to the following queue, the optimal service rate in queue i is not increased and the optimal service rates elsewhere are not decreased. We prove a similar result for problems of optimal arrival rate and service rate control in general queueing networks. The results are extended to an average-cost measure, and an example is included to show that in general the assumption of convex holding costs may not be relaxed. A further example shows that the optimal policy may not be monotone unless the choice of possible service rates at each queue includes 0.