Page 297 - A First Course In Stochastic Models

OPTIMIZATION OF QUEUES 291

a Markov decision model with a finite state space. Using a simple but generally
useful embedding idea, we avoid brute-force truncation of the infinite set of states.

Example 7.4.1 Optimal control of a stochastic service system

A stochastic service system has s identical channels available for providing service,
where the number of channels in operation can be controlled by turning channels
on or off. For example, the service channels could be checkouts in a supermarket
or production machines in a factory. Requests for service are sent to the service
facility according to a Poisson process with rate λ. Each arriving request for service
is allowed to enter the system and waits in line until an operating channel is
provided. The service time of each request is exponentially distributed with mean
1/µ. It is assumed that the average arrival rate λ is less than the maximum service
rate sµ. A channel that is turned on can handle only one request at a time. At any
time, channels can be turned on or off depending on the number of service requests
in the system. A non-negative switching cost K(a, b) is incurred when adjusting
the number of channels turned on from a to b. For each channel turned on there
is an operating cost at a rate of r > 0 per unit of time. Also, for each request
a holding cost of h > 0 is incurred for each unit of time the message is in the
system until its service is completed. The objective is to find a rule for controlling
the number of channels turned on such that the long-run average cost per unit of
time is minimal.
Since the Poisson process and the exponential distribution are memoryless, the
state of the system at any time is described by the pair (i, t), where

i = the number of service requests present,

t = the number of channels being turned on.
The decision epochs are the epochs at which a new request for service arrives
or the service of a request is completed. In this example the number of possible
states is unbounded since the state variable i has the possible values 0, 1, . . . .
A brute-force approach would result in a semi-Markov decision formulation in
which the state variable i is bounded by a sufficiently large chosen integer U such
that the probability of having more than U requests in the system is negligible
under any reasonable control rule. This approach would lead to a very large state
space when the arrival rate λ is close to the maximum service rate sµ. A more
efficient Markov decision formulation is obtained by restricting the class of control
rules rather than truncating the state space. It is intuitively obvious that under each
reasonable control rule all of the s channels will be turned on when the number of
requests in the system is sufficiently large. In other words, choosing a sufficiently
large integer M with M ≥ s, it is from a practical point of view no restriction
to assume that in the states (i, t) with i ≥ M the only feasible action is to turn
on all of the s channels. However, this implies that we can restrict the control of
the system only to those arrival epochs and service completion epochs at which