Optimal control of service rates in networks of queues

R. Weber and S. Stidham, Adv. Appl. Prob. 19 202-218, 1987.

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 pf 
$\cdot/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 $[0,\bar{\mu}]$, where the cost $c_i(\mu)$ is charged for each 
unit of time that the service rate $\mu$ 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 at 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$.

back to list of papers