Lecture Notes for 21 November 2002                      (Author: Gautam Tambay)

 

Queuing Theory (Continued)

 

Let us consider an optimization problem.

 

If we have a bank with a (M/M/c) (GD/∞/∞) type of queue. This is to say that the inter-arrival times and service times are exponentially distributed, and the system capacity and the calling source are assumed to be infinite.

 

It is intuitively evident that as we have fewer servers, the average waiting time will go up, while increasing the number of servers would raise our operational costs. There is an obvious trade-off here, and thus an optimization problem can be formulated. We are required to find the optimal value for c, i.e. the number of servers that should be set up at the bank, so as to minimize our costs.

 

Mathematically, a cost may be assigned to the waiting time. That is, we can incorporate a cost of waiting, f(W), which is a non decreasing function of the expected waiting time W.

The function f will depend on how much penalty we want to introduce for high waiting times.

 

Eg.       It may be linear.            f(W) =  R*W               (where R is a constant)

 

Alternatively, if we want a higher penalty for higher waiting times,

            It may be quadratic       f(W) =  R*W²

 

 

Similarly, we there will be a cost for operating the servers, g(c), which will typically be a linear function of c, the number of servers.

 

Thus our total cost will look like this:

 

TC =  f(W) + g(c)

           

The expected waiting time (W) can be expressed in terms of the number of servers c. It is evident that by increasing c, W will decrease.

Thus, f(W) can be expressed as h(c), a non increasing function of c,

 

Thus our total cost will be:

 

            TC =  h(c) + g(c)

                                        where h(c) is the cost of waiting when we have c servers

                                                   g(c) is the cost of operating c servers

 

Thus we have the total cost in terms of c.

One way to optimize the total cost, is to differentiate the expression for TC with respect to c, and equate it to zero. Since the total cost will be a convex function of c, there will be only one minimum point.

 

The optimal value (c*) obtained by this method is not an integer. However, we need an integer value, since c is the number of servers we require.

 

Then we look at the values of the TC at the two integers between which c* lies. This is to say, that if the optimal value of c* is 3.7, then we check the total cost at  c = 3 and c = 4.

We compare TC(c=3) and TC(c=4). Whichever of these is found to be lower on comparison will give the optimal value of c.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

BLOCKING

 

Suppose we have a queue where each person who comes in has to go through two service points S1 and S2.

 

Assumptions:

 

o       Arrival rate of customers is Poisson with parameter λ

_o         Service rate at first service station is Poisson with parameter μ₁

_o         Service rate at first service station is Poisson with parameter μ₂

 

o       The maximum capacity of each server is 1

Ø      If a customer arrives and sees that S1 is occupied, then s/he  returns without entering the system.

Ø      If a customer at S1 has been serviced, but s/he sees that S2 is occupied, then s/he waits at S1 until the ongoing service at S2 is completed. (S/he is thus blocking the system, since till the time he is waiting at S1, there can be no service at S1, though the server is not busy.)

 

We have to define states such that we only need to know what state the system is in order to predict what is going to happen.

 

The possible states are:

 

1. When S2 is vacant:

(0,0) i.e. no person at either server

(1,0) i.e. one person at S1, nobody at S2

 

2. When S2 is occupied

(0,1) i.e. nobody at S1, one person at S2

            (1,1) i.e. one person is being serviced at S1, one person at S2

            (1b,1) i.e. one person has been serviced, and is blocking S1, one person at S2

 

Thus there are a total of 5 possible states.

It is important that we distinguish between (1,1) and (1b,1) because when S2 is occupied, simply knowing that there is one person at S1 is not sufficient to predict the future states. We need to know whether or not the person at S1 is blocking the system. With this information we can draw the state diagram.

 

 

State Diagram for System described above

 

 

Here, we can find the probability P_n of finding the system in any state n, by using ‘Rate in  =  Rate out’ equations.

 

Through Put

 

A good measure of service quality in this kind of a system would be the number of people that get processed per unit time. We call this the Through Put of the system.

 

The through put will simply be equal to the rate at which people are exiting S2.

This, in our case, will be :

 

Through put  =  μ_{2 *} ( P_(0,1) + P_(1,1) + P_(1b,1) )

 

We can also define alternate measures of service quality, for instance, the rate at which people get turned down at the onset (when S1 is busy).