LECTURE NOTES
06/11/02
QUEUEING THEORY
BY: VINEET GOTHI &PRATIBHA MEENA.
Why study queues?
Waiting
for service is part of our daily life. We wait to eat at restaurants. We “queue
up” at the check-out counters in grocery stores, and we “line up” for service
in post offices. And the waiting phenomenon is not an experience limited to
human beings only: Jobs wait to be processed on a machine, planes circle in a
stack before given permission to land at an airport, and cars stop at traffic
lights. Unfortunately, we cannot eliminate waiting without incurring inordinate
expenses. In fact, all we can hope to achieve is to reduce the adverse impact
of waiting to acceptable levels.
The study of queues determines the
measure of performance of a queueing situation, including the average waiting
time and the average queue length, among others. This information is then used
to decide on an appropriate level of service for the facility.
Some
more examples of queues are:
1) internet queues
2) railway reservation counters.
3) Toll barriers
4) Barber’s shop
5) Petrol pumps
6) SBI bank at IIT Delhi
·
E
(W)® Expected waiting time in queue.
·
P
(W>30mins)® probability that the waiting time would
be greater than 30 mins.
·
E
(Q)® Expected queue length
·
P (
Q³15)® probability that the queue length will be greater than or
equal to 15.
·
Average
time for which a particular server is busy.
Example:
Consider a situation
where there are 4 arrivals/hours on an average and the average service time for
a person is 12 mins.
Q.
Can there be a situation where the waiting time is zero?
Ans.
Yes, if the arrivals are exactly after 15 mins and the service time is exactly
12 mins.
Waiting and service times are typically
random
How
do we go about capturing the randomness in waiting and service times??
To
address this problem we make some assumptions:
(A1,
A2, A3.........) i.e the inter-arrival times are
independent of each other and picked up from same distribution.
We
make a similar assumption for all the service times Bi’s.
To
find out what kind of pdf (probability distribution function) does the
inter-arrival and service times follow, we plot the time intervals
(inter-arrival and service time) on X axis and fraction of arrivals/departures
on the Y axis. We then try to make the “best fit curve” and the equation of
curve gives the probability distribution.
For example in the above curve,
(1,2,3...6) are all time intervals say for instance 1 represents 0-20 sec time
interval and 2 represents 20-40 sec time interval and so on. On the y-axis is
the frequency of arrivals and departures in these time intervals. Now we can
find out the equation of the “best fit curve” and this will give the
probability distribution of the inter-arrival and service times.
There
are some tests available to check whether the fit of pdf is indeed a good one
and whether the inter-arrival times are independent or not.
Elements
of a queueing model:
1) No. of servers- single or multiple
2) Queue size- finite or infinite
3) Service discipline (FCFS/LCFS/SPT)- the
order in which customers are selected from a queue.
FCFS-
first come first serve, LCFS- last come first serve, SPT- service priority
timing where priority is given to the customer depending on the expected
service time. For example at grocery stores the customer whose service time is
less is served first no matter what is the order of arrival.
4) Nature of source- infinite or finite, the
source is generally assumed to be an infinite source just to “simplify” things.
A finite source limits the customers arriving for service (e.g machines
requesting the service of a repairperson). Alternatively, an infinite source is
forever “abundant” (e.g calls arriving at a telephone exchange.)
5) Human factors – “Human” customers may “jockey” from one queue to another in
hopes of reducing their waiting. They may also “balk” from joining a queue altogether because they anticipate a
long delay, or they may “renege”
from a queue because they have been waiting too long.
For FCFS, single server queues we can
write.
Wn+1
= [Wn + Bn – An+1]+
where
Wn+1
is the waiting time for n+1th customer
Wn
is the waiting time for nth customer
Bn
is the service time for nth
customer &
An+1
is the inter-arrival time between nth and n+1th customer.
POISSON PROCESS:
The integer valued arrival process {N(t)} is
said to be a Poisson Process with rate l if..
1) N(0) =0
2)
The
process has independent increments i.e.
N (t+s) – N(t) is independent of N(u) , u£ t
3) The
no. of events in any interval of length “t” is Poisson distributed with
mean lt if
P [N(t+s)-N(s)=n] =
{(lt)n
e-lt}/ n! &
E {N(t)}=lt.
This process can be alternatively
characterised in the following more intuitive manner.(in fact the two can be
proved to be equivalent)
A function f( ) is o(h) if limit h®0 f(h)/h =0.
The counting process {N(t)} is said to be
a Poisson process with rate l, l>0 if
1) N(0) = 0
2) The increments are independents of each
other.
3) P [N(h) =1] =lh + o(h)
4) P [N(h)³2] = o(h)
Let (A1, A2,.........An)
is a sequence of inter arrival times of a Poisson process
We now show that these are I.I.D
exponentially distributed with rate l i.e their pdf is f(x)=le-lx when x ³0 and 0
otherwise. To see this we note that,
P (A1 >t) = P{N(t)=0)= e-lt
i.e. P (A1£t) = 1- e-lt
fA1 (t) =l e-lt
Now, P(A2 >t| A1=s)
= P(No event in [s,(s+t)] | A1 =s)
= P (N(t+s)-N(s)=0| N(u)=0, 0<u<s)
= P (N(t+s)-N(s)=0)
= P (N(t)=0)
= P (No event in s,s+t)..........®independent increment
=P (No event in (0,t)).............®stationary increment
= e-lt
This argument shows that the inter-arrival
times have an exponential distribution.