15th Nov
POISSON PROCESS: it is equivalent to a process that has independent identically distributed inter arrival times with distribution which are exponential with ratel. No of customers generated until any specific time has a poisson distribution.
The probability of having n
arrivals in a time t is given by:
(1)
Here, l is the mean arrival rate (expected no of arrivals/unit time)
So, if X is the inter arrival time, where (a,b) is the time interval, then
(2)
If N(t) denotes the no of arrivals in time t, then expected no of arrivals in time t,
E (N (t)) =lt
MEMORY LESS PROPERTY of the EXPONENTIAL DISTRIBUTION
Probability distribution of remaining time until the arrival or service completion occurs always is the same as, regardless of how much time (s) already has passed. In effect the process “forgets” its history. For inter arrival time this property describes the common situation where the time until the next arrival is completely uninfluenced by when the last arrival occurred.
Examples
(1) In last 5 min no person came at bus stand. This fact won’t effect in any way the probability of a person coming in the near future.
(2) Given that a bulb that has not failed its future life is as good as that of a new bulb.
Mathematically, if X is exponentially
distributed, i.e its pdf is for x ≥0, l>0,
then
P (X >t+s| X >s) =P (X>t)
(3)
NOTE: Exponential distribution is the only distribution that has memory less property
THE BIRTH AND DEATH PROCESS
Most queuing models assume that inputs (arrivals of customers) and outputs (departure of a served customer) of the queuing system occur according to birth and death process. Here birth refers to arrival of new customers and death refers to the departure of served customers. Broadly speaking, individual births and deaths occur randomly, where their mean occurrence rates depend upon the current state of the system. This is with the assumption that only one birth or death can occur at a time. This assumption is valid, because in a Poisson process, probability of 2 simultaneous arrivals is zero.
Pure Birth Process
Probability of n births in time t with rate l is a Poisson process.
Pure Death Process
No of items dying is also a Poisson process. Suppose 1) we have N items to begin with and demand is 2)Poisson with rate µ and 3) n items left after time t
Then Probability of N-n demand
(4)
for zero items at time t, one may be tempted to write:
however this expression is incorrect, this is only the probability of demand being equal to N in time t. but even if the demand is greater than N, we are finally left with zero items.
Therefore summation from 0 to infinity is 1 and not 0 to n is 1.If demand is greater than N then we left with zero inventory.
Therefore , P0(t) = P(demand ≥ N) = P(demand = N) + P(demand = N+1) + ….P(demand = ∞)
=> (6)
to verify we can check that
NOTATION FOR SPECIFYING QUEUE
A queue is denoted by (a/b/c) (d/e/f) where,
a: arrival time distribution
b: service time distribution (M/M/ if inter arrival time and service time are exponential where M for memory less, GI/GI/ if general independent arrival distribution and D if deterministic)
c: no of parallel servers (GI/GI/5 for 5 queues, e.g. check-in at airport, photocopy shop, the disadvantage with multi-queue is that a person entered late may get priority or server and people both are waiting)
d: service disciplines (M/M/1/FCFS, GI/D/1/SIRO, GI/D/1/LCFS,GI/D/1/PS, GI/D/1/TCP (transfer control processing)
e: max no allowed in a system (e.g. in phone calls when all available lines are busy then further any call would be simply rejected)
f: size of the calling source (e.g., no of births from a finite population) -> f = size of the population ( e.g. in a bank queue, f = no. of account holders)
THE BASIC MODEL (Constant Arrival and Service Rate)
It is quite common for a queuing system’ mean arrival and service rate per busy server to be essentially constant (l and µ respectively) regardless of the state of the system (see fig 1.1). Therefore basic model makes this assumption. When the system has just a single server (c=1), this implies that the parameters for the birth-and-death rate are ln=l (n=0,1,2,..) and µn=µ (n=1,2,..). However when the system has multiple servers (c >1), then the µn can’t be expressed this simply. Keep in mind that the mean service rate for the overall queuing system (i.e., the mean rate at which service completions occur, so that customers can leave the system) when n servers are busy in the system. Thus when the mean service rate is µ, the overall mean service rate must be nµ. therefore when there are N customers in the system,
If N ≤ c, then no. of busy servers = N
If N > c then no. of busy servers = c, mean service rate = cµ
All one needs to know is the no. of people in the queue at that instant. (see fig. 1.2)
Fig 1.1 At
Each State 2 Clocks Are Working One At And Other At
ln=l for n=0,1,2,..
µn=nµ for n=1,2,3
cµ for n=4,5,6.
.
Fig 1.2
Transition Rate Diagram for Multiple Server Case (c=3 with service rate µ and
arrival ratel)
Suppose we have three events whose
‘occurring times’ t1, t2, t3 are exponentially
distributed with parameters µ1, µ2, µ3. Then
the time when first event occurs, i.e. min {t1,t2, t3}
is again exponentially distributed with parameter (µ1+ µ2+
µ3). This statement can be generalized for n events.
e.g., m/c shop with N m/cs and each m/c breakdown with rate λ and one repairman repairs with rate µ(see fig 1.3).When two breakdowns have already occurred, next machine will fail in min of time of breakdowns that are N-2 and exponentially distributed.
Fig 1.3 Transition Rate Diagram for N m/cs
GENERALIZED
POISSON MODEL
To study all of these models we define a general framework. This applies to Poisson queue with state dependent arrival and departure rates (see fig 1.4). Birth one jump up and death one down (multi-jumps are not allowed).
Fig 1.4 Transition Rate Diagram For
Generalized Model
Let us observe the system after time T has passed since the stint.
It is steady state, when T is large enough so that probability of finding the system in any state does not depend on T
ie., (independent
of time)
(e,g. in initial period data may be biased but as time becomes large probability becomes constant with time.)
(Constant) (7)
Where Tn = time spent by system in state n
Expected no of people in the system