Transcript Materialy/11/L4-Introduction to gueuing theory

Slovak University of Technology
Faculty of Material Science and Technology in Trnava
Modeling and
simulation of systems
Introduction to queuing theory
The system of queuing model
Queue
Service
Arriving customer
Serviced
customer
The system of queuing model is an arbitrary service where the
service of a particular kind is provided. The customers (demands)
who require service arrive into this system.
The element of the system which provides the service is called
serviced channel or line.
The system of queuing model
Important qualities of elements of queuing
model :
 Arrivals of customers
intervals between arrivals are important
 run of service
one or more serviced channel (links)
period of service
 behaviour of customers when they
cannot be serviced immediately
 systems without queue
 with limited length of queue
 with unlimited length
Qualification of queuing models
 Kandal´s qualification which divides queuing
models according to three criteria is used the
most frequently:
 Arrival of customers
is described by random process
 The
division of probabilities of period of service
 The number of servicing channels

Used shape of qualification X/Y/c
Qualification of queuing models
Examples of marking:
 M/M/n
n = 1,2,3 ....
Arrival – Poisson´s process
Service – exponential division
n – number of serviced channels
 D/D/c
Arrival – regular intervals
Service – constant period
 G/G/c
general case it means no assumptions about
arrivals and general division of period of service
Arrivals of customers (stochastic
process)



The customers arrive individually
For each time t we get number N(t) – number of
customers who came at time (0,t
The result is non falling function N(t), t0, which gains
the whole non negative values and N(0) = 0
N(t)
5
4
3
2
1
t0
t1
t2
t3
t4
t5
Arrivals of customers
(stochastic process)



Arrivals into the system are random then for
given t is N(t) random quality  what is division
of probabilities
pk(t) = P{N(t) = k}, k = 0,1,2,...
Arrival of customer is defined as the system of
random variables N(t), t0 and is edited
{N(t)}tT T0,
Such system is called stochastic (random)
process
Poisson´s homogenous process

Is given random process {N(t)}t0 with independent
growths it means random qualities N(b1) - N(a1), N(b2) N(a2), .., N(bn) - N(an) are independent, if intervals
(a1,b1, (a2,b2, .., (an,bn are disjunctive when all
random qualities N(t+) - N(t) have Poisson´s division
of probability.
PN t     N t   e
 
 
k
k!
The middle value of number of customers who come in time 
is 
Qualities of Poisson´s process

Homogeneity

The probability of it that in the time  comes to
customers does not depend on the beginning of
interval (t, t+
It means that arrival of customers is regular
for the whole period.

Independence
the number of customers who came
during each period does not depend on
the number of customers who came into
the system in other disjunctive time
period.
Qualities of Poisson´s process

Ordinary
lim
PN ( )  1
0
 0

It means that more than one customer comes in a very
short time interval with insignificant probability smaller
that the length of this interval.
It is not probable that more customers come at the
same time.
The relation between Poisson´s
division and exponential division
The division of random quantity which is the interval
between arrival of two customers that is
k= tk - tk-1 k = 1,2,...
 Distributive function F() of random variable k
F() = P{k } = 1 - P{k }
P{k } = P{N() = 0} = e-
Then:

1 - e-,
F() =
0,
0
Exponential
distribution
0
If  is the mean value of the number of customers arriving into the
system for time unit, then.... is the mean value of time between
arrivals of customers
The number of customers in the system
Markovov´s homogeneous process
The system is characterized by the
number of customers X(t), who are in
the time t in the system.
 If arrivals of service period is random
then the number of customers X(t) at
the moment t is random.
 The function X(t) can fall as well as rise
in dependence on how customers arrive
and how fast are they served

The run of the number of customers
in the system
X(t)
4
3
2
1
t0
t1
t2
t3
t4
t5
Random value X(t) gains values
k = 0,1,2,... with probabilities
pk(t) = PX(t) = k

where
p
j 0
j
(t )  1
for each t0
t6
t7
Markovov´s random process


Definition:
the random process X(t)t0 is called
Markovov´s, if is in force:
P X(t) = kX(s1) = j1, X(s2) = j2, ..., X(sn) = jn  = P
X(t) = k X(s1) = j1 
for ts1  s2 ... sn 0
It means that the future X(t) does not depend on
the past X(si), i1, but only on the presence
X(s1)
Homogeneous process


If is in force
P X(t+) = j X(t) = i  =
= P X(s+) = j X(s) = i  =
= P X() = j X(0) = i ,
then the process is homogeneous.
It means that there will be j of customers in the
system after the time , if there were i of
customers in the time t it depends only on length
of time , and not on since when it is monitored.
Probability of transition from the
state j into the state i



Probability of transition from j into i is a
probability by which the system transits from
the state i into the state j and is marked as
pij().
Then
pij() = P X(t+) = j X(t) = i  = P N(t+) N(t) = j - i 
Poisson´s process is also Markovov´s and is
in force:
pij ( )  e
 
( )
( j  i )!
j i
Intensity of transition

The intensity of transition of Markovov´s
homogeneous process X(t)t0 is called
number
ij  lim
 0
pij ( )

ij
Intensity of transition
01
0


10
1
SHO is given with one service channel
without waiting. The arrivals with Poisson´s
division with the middle value , period of
service – exponential division with the middle
value 1/. Random process (then the number
of customers in the system gains the values 0
a 1.
It is necessary to determine 01
Intensity of transition
01  lim
 0
p01 ( )

It is necessary to determine for the calculation p01.
The system transits from the state 0 into the state 1:
A:
For the time  just one customer arrives and his
service after the time  does not end.
B:
For the time  more that one customer arrives and the
service of one of them after the time  does not end
It means that
p01( ) = PA + PB
a
01  lim
 0
P{ A}

 lim
 0
P{B}

Intensity of transition
Event B:
PN() 1

lim
 0
P{B}

 lim
 0
Ordinary of
Poisson´s random process
P{N ( )  1}

0
Intensity of transition
Event A:
Probability A is given by product of probability that for
the time  just one customer arrives and probabilities
that his service after  does not end.
PA= PN() =1. Ptobs  
PN() =1=e-.
Distributive function of period of service tobs
F() = Ptobs   = 1- e- ,
 0
then
Ptobs   = 1- Ptobs   = e-

lim
 0
P{ A}

 lim
 0
e   e  


Intensity of transition
Intensity of transition 01= +0= 
 It is possible to determine in similar way
10=
 Then it is necessary to determine for the
system with one service channel without
queue probabilities of the fact that there is in
the system in the time t k of customers:

pk(t)= PX(t) = k 
Kolmogorov´s differential equations

Determination of previous probabilities
leads to the following equations:
p0'  p0 (t )  p1 (t )
p1'   p1 (t )  p0 (t )
These equations are Kolmogorov´s
differential equations. They are not ependent.
It is force:
p0(t) + p1(t) = 1
Kolmogorov´s differential equations

For transcript of Kolmogorov´s equations is in
force:
n


'
pk (t )  pk (t )   kj  
 j 0, j  k 
n
 p (t )
j 0, j  k
k
Derivation p’k of probability that the system in the
time t in the state k equals to summation of
probabilities, that in the state k multiplied by sum
of negatively outstanding intensities of transition
getting out of state k and probabilities of all other
states multiplied by intensities of transition which
getting out into the state k
jk
Kolmogorov´s differential equations
Example of transcript of equations:
01
0
10
23
12
1
21
2
Kolmogorov´s differential equations:
p’0 = - 01p0 + 10p1
p’1 = -(10 + 12) p1 + 01p0 + 21p2
p’2 = -(21 + 23) p2 + 12p1 + 32p3
p’3 = - 32p3 + 23p2
32
3