Transcript t - itworkss

QUEUING THEORY
Queuing Theory
• Each of us has spent a great deal of time waiting in lines.
• In this chapter, we develop mathematical models for
waiting lines, or queues.
• To describe a queuing system, an input process and an
output process must be specified.
• Examples of input and output processes are:
Situation
Input Process
Output Process
Bank
Customers arrive at
bank
Tellers serve the
customers
Pizza hut
Request for pizza
delivery are received
Pizza parlor send out
scooters to deliver
pizzas
QUEUING THEORY
2
Queuing Costs vs. Level of Service
Cost of operation
Total expected
cost
Cost of
operating the
service facility
per unit time
Cost of waiting
customers per
unit time
Optimum
service level
Level of Service
QUEUING THEORY
3
QUEUING SYSTEM
Service System
Waiting
Customers
Input
source
Arrival
Process
Balk
Queuing
Process
Renege
Queuing
discipline
Departure
Service
Process
Jockey
QUEUING THEORY
4
Input Source Characteristics
• Input source is characterized by size of calling
population, behavior of the arrivals and pattern of
arrival of customers.
• Size of calling population – Homogeneous, subclasses, finite or infinite.
• Behavior of arrivals – Patient customer, balking,
reneging or jockeying.
• Pattern of arrivals – Static or dynamic, pattern is
further subdivided based on nature of arrival rate
and control on the arrival.
QUEUING THEORY
5
Pattern of Arrival Process
• In static systems the arrivals can be random or at
constant rate.
• Random arrivals can be varying with time.
• To analyze the queuing system we should know
the probability distribution of the arrivals.
• We obtain distribution for the arrivals and also for
the inter-arrival time.
• In dynamic system, both service facility and
customers are controlled.
• The arrival pattern can be approximated by
Poisson, Erlang or Exponential distribution.
QUEUING THEORY
6
QUEUING PROCESS
• Queuing process refers to length of queues and
number of queues.
• There can be single server (facility) or multiple
facility.
• Queues can be finite (cinema hall) or infinite
(sales orders).
• When customers experience long queues then they
may not enter the queue.
• Queue discipline controls the service for the
customers
QUEUING THEORY
7
QUEUE DISCIPLINE
• The queue discipline describes the method used to
determine the order in which customers are served.
• The most common queue discipline is the FCFS discipline
(first come, first served), in which customers are served in
the order of their arrival.
• Under the LCFS discipline (last come, first served), the
most recent arrivals are the first to enter service.
• If the next customer to enter service is randomly chosen
from those customers waiting for service it is referred to as
the SIRO discipline (service in random order).
QUEUING THEORY
8
QUEUEING DISCIPLINE
• Finally we consider priority queuing disciplines.
• A priority discipline classifies each arrival into
one of several categories.
• Each category is then given a priority level, and
within each priority level, customers enter service
on an FCFS basis.
• Another factor that has an important effect on the
behavior of a queuing system is the method that
customers use to determine which line to join.
QUEUING THEORY
9
SERVICE PROCESS
• Service process is characterized by following




arrangement of service facility.
distribution of service times.
server’s behavior
management policies.
• Arrangement of facilities can be
 single queue and single server
 single queue and multiple server
 mixed arrangement
QUEUING THEORY
10
Service Process Distribution
• Time taken be server from the commencement to
completion of service for a customer is called service time.
• To describe the output process of a queuing system, we
usually specify a probability distribution – the service time
distribution – which governs a customer’s service time
• The most commonly distribution used for service time
distribution is negative exponential.
• Servers are in parallel if all servers provide the same type
of service and a customer needs only pass through one
server to complete service.
• Servers are in series if a customer must pass through
several servers before completing service.
QUEUING THEORY
11
Performance measures of Queuing theory
• Time related questions
 What is the average time an arriving customer has to
wait in the queue (Wq) before being served.
 What is the average time an arriving customer spends
in the system (Ws) including waiting and service.
• Quantitative questions related to no of customers
 Expected no of customers in the queue for service (Lq)
 Expected no of customers who are in the system
waiting in queue or being serviced (Ls)
QUEUING THEORY
12
Performance measures of Queuing theory
• Questions involving time both for customers and
servers
 Probability that an arriving customer has to wait before
being served Pw.
 Probability that a server is busy at any particular point
(). It is the proportion of the time that a server spends
actually with a customer.
 Probability of having ‘n’ customers in the system when
it is in steady state. Pn, n= 0,1,…n.
 Probability of customer denied service because of
queue being full. Pd.
QUEUING THEORY
13
Poisson Distribution
• Customers arrive at a bank or grocery in a completely
random fashion.
• The probability density function for describing such
arrivals during a specified period follows Poisson
distribution.
• Let x be the arrivals that take place during a specified time
units.
• Poisson pdf is given by
P[ x  k ] 
k e  
k!
, k  1,2,..
• Mean and variance is given by
E{x}  
var{x}  
QUEUING THEORY
14
Exponential Distribution
• If the no of arrivals at a service facility during a specified
period occurs according to Poisson distribution then the
distribution of the intervals between successive arrivals
must follow the negative exponential distribution.
• If  is the rate at which Poisson events occur then the
distribution of the time ,x, between successive arrivals is
given as
f ( x )  e  x
Mean E{x}  1
Var {x}  1

2
A

CDF P{x  A}  e x dx  1  e A
0
QUEUING THEORY
15
Analysis of a Simple Queue
service rate  at
the server
Arrivals with an
average arrival
rate of 
Single server
Infinite no of
waiting
customers.
QUEUING THEORY
16
Steady State & Transient State
• At the start of the system the queue is influenced
by no of customers, and the elapsed time.
• This is referred as transient state.
• After sufficient time the system returns to steady
state.
• We analyse the steady state behavior as transient
state is complex and beyond our scope.
• Arrival rate has to be less than service rate else the
system cannot reach steady state.
QUEUING THEORY
17
Modeling Arrival Process
• We assume that the arrival process can be
approximated by Poisson distribution.
• Let us consider a Poisson process involving the
number of arrivals n over a time period t.
• If  is the arrival rate (traffic intensity) then the no
of customers expected in time t will be t.
• The probability mass function Pn is given by
( t ) n e   t
P( x  n | Pn  t ) 
, n  0,1,2..
n!
QUEUING THEORY
18
Modeling Arrival Process
• The probability mass function of no arrival (n=0) in time t
is given by
0  t
( t ) e
P( x  0 | Pn  t ) 
0!
 e  t
• Let us define the random variable T as the time between
successive arrivals.
• T will be a continuous random variable.
• The assumption that each inter-arrival time is governed by
the same random variable implies that the distribution of
arrivals is independent of the time of day or the day of the
week.
• This is the assumption of stationary inter-arrival times.
QUEUING THEORY
19
Modeling Arrival Process
• Stationary inter-arrival times is often unrealistic, but we
may often approximate reality by breaking the time of day
into segments.
• A negative inter-arrival time is impossible. This allows us
to write
P(T  t ) 
t

0 a(t )dt and P(T  t )  t a(t )dt
• We define1/λ to be the mean or average inter-arrival time.
1


  ta(t )dt
0
QUEUING THEORY
20
Modeling Arrival Process
• The distribution of the random variable T is called
the exponential distribution.
• Its probability density function is given by
f(t) = λe-λt. for t 0 and is o for t<0.
• We can show that the average or mean inter-arrival
time is given by
.
E (T) 
1

QUEUING THEORY
21
Derivation of Exp Distribution
• The exponential distribution is based on three
axioms:
 Given N(t), the number of events during the interval
(0,t), the probability process describing N(t) has
stationary independent increments, in the sense that the
probability of an event occurring in interval (T, T+S)
depends only on the length of S.
 The probability of an event occurring in a sufficiently
small time interval h> 0 is positive but less than 1
 In a sufficiently small time interval h>0, at most one
event can occur-that is P{N(h)>1}=0
QUEUING THEORY
22
Derivation of Exponential Distribution
• Define Pn(t) as the probability of n events occurring during t.
• We have seen earlier that probability of no arrival in time t is given by
P0(t) = e -t
• Define f(t) as the pdf of the interval t between successive events, t>0 .
We then have
 P(inter-event time >T) = P(no event during T)

 f (t )  P0(T ), T  0 which after rearranging
T
T

f (t )  1  e t , T  0
0
Taking derivativeof both sides will yield
f (t )  e t , t  0. This is exponential distribution
QUEUING THEORY
23
No Memory Property of Exp Distribution
• If T has an exponential distribution, then for all
nonnegative values of t and h,
P(T  t  h | T  t )  P(T  h)
• A density function that satisfies the equation is said to have
the no-memory property.
• The no-memory property of the exponential distribution is
important because it implies that if we want to know the
probability distribution of the time until the next arrival,
then it does not matter how long it has been since the last
arrival.
QUEUING THEORY
24
Markov Process
• Markov Processes
 X(t) satisfies the Markov Property (memoryless) which
states that -for any choice of time instants ti, i=1,……,
n where tj>tk for j>k
 P{X(tn+1)=xn+1| X(tn)=xn ……. X(t1)=x1}
=P{X(tn+1)=xn+1| X(tn)=xn}
• Memoryless property as the state of the system at
future time tn+1 is decided by the system state at
the current time tn and does not depend on the
state at earlier time instants t1,…….., tn-1
QUEUING THEORY
25
Modeling the Service Process
• We assume that the service times of different customers are
independent random variables and that each customer’s
service time is governed by a random variable S having a
density function s(t).
• We let 1/µ be the mean service time for a customer.
• The variable 1/µ will have units of hours per customer, so
µ has units of customers per hour. For this reason, we call
µ the service rate.
• Unfortunately, actual service times may not be consistent
with the no-memory property.
• In certain situations, inter-arrival or service times may be
modeled as having zero variance; in this case, inter-arrival
or service times are considered to be deterministic.
QUEUING THEORY
26
Modeling the Service Process
• For example, if inter-arrival times are deterministic, then
each inter-arrival time will be exactly 1/λ, and if service
times are deterministic, each customer’s service time is
exactly 1/µ.
• Negative exponential distribution is used to describe the
service times distribution.
• The pdf of the service times is
f (t )   e  t , t  0
• The probability of n service completion in time t is given
by
( t ) n e  t
P(n service completion in time t) 
, n  0,1,2..
n!
QUEUING THEORY
27
Basic Notations
n  no of customers in the system(waiting & in service)
Pn  probability of n customers in the system
  average (expected) customer arrival rate or average arrival rate per unit time
  average (expected) service rate or average no of customers served per unit of time.

    average service completion time (1/ )/average inter - arrival time (1/ )
 traffic intensityor server utilisation factor (fraction of time server is busy)
s  no of service channels
N  maximum no o fcustomers allowedin the system
Ls  average (expected) no of customers in the system(in queue & served)
Lq  average (expected) no of customers in the queue
Lb  average (expected) length of non - empty queue
W s  average (expected) waiting time in the system(waiting & in service)
W q  average (expected) waiting time in the queue.
Pw  probability that an arriving customer has to wait.
QUEUING THEORY
28
Relationship among Performance
measures
• We have the following relationships
Ls 

 nPn
n 0
Lq 

 (n  s)Pn
n s
• Average no of customers in the system is equal to the
expected no of customers in queue plus in service
Ls  L  E  Lq  

• Average waiting time of the customer in the system is
equal to waiting time in queue plus in service
Ws Wq  1

QUEUING THEORY
29
Relationship among Performance
measures
• Average no of customers served per busy period is given
by
Ls

Lb 

P( n  s )   
where P(n  s)  probability that systembeing busy
• Average length of queue during busy period is given by
Wq
1
W b

P(n  s)   
QUEUING THEORY
30
Relationship among Performance
measures
• Little's law gives a very important relation between Ls, the mean
number of customers in the system, Ws, the mean sojourn time
and , the average number of customers entering the system per
unit time. Little's law states that
1
Ls  1
Ls  W s or W s  Ls or

Lq  W q or W q 
1


Lq or
Ls

• The probability , Pn of n customers in the queuing system at any
time can be used to determine all the basic measures of
performance in the following order
Ls 

 nPn  W s 
n 0
Ls

W q W s
QUEUING THEORY
1

 Lq  W q
31
Basic Axioms
• Let Pn(t) denote the probability that there are n customers
in the system at time t.
• The rate of change of Pn(t) with respect to time t is
denoted by derivative of Pn(t) with respect to t.
• In case of steady state we have
Lim Pn(t )  Pn independent of t
t 
d
d
Lim {Pn(t )}  ( Pn)
dt
dt
t 
Lim P' n(t )  0
t 
QUEUING THEORY
32
Basic Axioms
• The no of arrivals in non-overlapping intervals are
statistically independent.
• The probability that two or more customers arrive
in time interval (t, t+t) is negligible and is
denoted by 0 t. 
• The probability that a customer arrives in the time
interval (t, t+t) is P1(t) =  t + 0 t.
•  is inter-arrival time and is independent of total
no of arrivals up to time t. As t  0, the qty 0 t
is negligible.
QUEUING THEORY
33
Probability Analysis
Assume that, as t 0
P{one arrival in time  t} =   t
P{no arrival in time  t} =1-   t
P{more than one arrival in time  t} = O(( t)2) = 0
P{one departure in time  t} =   t
P{no departure in time  t} =1-   t
P{more than one departure in time  t} = O(( t)2) = 0
P{one or more arrival and one or more departure in time 
t} = O(( t)2) = 0
• Arrival Process, Mean Inter-arrival time = 1/ 
• Service Process, Mean Service time = 1/ 
•
•
•
•
•
•
•
•
QUEUING THEORY
34
Waiting Time Paradox
• Suppose the time between the arrival of buses at
the student center is exponentially distributed with
a mean of 60 minutes.
• If we arrive at the student center at a randomly
chosen instant, what is the average amount of time
that we will have to wait for a bus?
• The no-memory property of the exponential
distribution implies that no matter how long it has
been since the last bus arrived, we would still
expect to wait an average of 60 minutes until the
next bus arrived.
QUEUING THEORY
35
Birth Death Process
• We subsequently use birth-death processes to answer
questions about several different types of queuing systems.
• We define the number of people present in any queuing
system at time t to be the state of the queuing systems at
time t.
• We call Pn the steady state, or equilibrium probability, of
state n.
• The behavior of Pij(t) before the steady state is reached is
called the transient behavior of the queuing system.
• A birth-death process is a continuous-time stochastic
process for which the system’s state at any time is a
nonnegative integer.
QUEUING THEORY
36
Birth Death Process
• Law 1
 With probability λnΔt+o(Δt), a birth occurs between time t and
time t+Δt. A birth increases the system state by 1, to n+1. The
variable λn is called the birth rate in state n. In most queuing
systems, a birth is simply an arrival.
• Law 2
 With probability µnΔt+o(Δt), a death occurs between time t and
time t + Δt. A death decreases the system state by 1, to n-1. The
variable µn is the death rate in state n. In most queuing systems, a
death is a service completion. Note that µ0 = 0 must hold, or a
negative state could occur.
• Law 3
 Births and deaths are independent of each other.
QUEUING THEORY
37
Steady State Birth Death Process
• We now show how the Pn’s may be determined
for an arbitrary birth-death process.
• The key role is to relate (for small Δt) Pij(t+Δt) to
Pij(t).
Pn1n1  Pn1n1  Pn (n  n ) (n  1,2,...)
P11  P00
• The above equations are often called the flow
balance equations, or conservation of flow
equations, for a birth-death process.
QUEUING THEORY
38
Flow Balancing Approach
• In the “rate diagram” given below, think of the following:

0

1


2


3

4

• Each circle representing a state (i.e., number of customer
in the system) has an unknown probability Pn, n= 0, 1, 2,
… associated with it
QUEUING THEORY
39
Flow Balancing Approach
• We obtain the flow balance equations for a birth-death
process:
(n  0)
P0 0  P11
(n  1)
(1  1 ) P1  0 P0   2 P2
(n  2)
(2   2 ) P2  1P1   3 P3
...
(nth equation) (n   n ) Pn  n1Pn1   n1Pn1
(n  1n  2.....  0)
Pn 
P 0, n  1,2,...
( nn  1...... 1)
• Value of P0 is determined from the equation 
• In general we can write
 Pn  1
n 0
QUEUING THEORY
40
The Kendall-Lee Notation for Queuing
Systems
• Standard notation used to describe many queuing
systems.
• The notation is used to describe a queuing system
in which all arrivals wait in a single line until one
of s identical parallel servers is free. Then the first
customer in line enters service, and so on.
• To describe such a queuing system, Kendall
devised the following notation.
• Each queuing system is described by six
characters: 1/2/3/4/5/6
QUEUING THEORY
41
The Kendall-Lee Notation for Queuing
Systems
• The first characteristic specifies the nature of the
arrival process. The following standard
abbreviations are used:
 M = Inter-arrival times are independent, identically
distributed (iid) and exponentially distributed
 D = Inter-arrival times are iid and deterministic
 Ek = Inter-arrival times are iid Erlangs with shape
parameter
k.
 GI = Inter-arrival times are iid and governed by some
general distribution
QUEUING THEORY
42
The Kendall-Lee Notation for Queuing
Systems
• The second characteristic specifies the nature of
the service times:
 M = Service times are iid and exponentially distributed
 D = Service times are iid and deterministic
 Ek = Service times are iid Erlangs with shape parameter
k
 G = Service times are iid and governed by some general
distribution
• The third characteristic is the number of parallel
servers.
QUEUING THEORY
43
The Kendall-Lee Notation for Queuing
Systems
• The fourth characteristic describes the queue discipline:




FCFS = First come, first served
LCFS = Last come, first served
SIRO = Service in random order
GD = General queue discipline
• The fifth characteristic specifies the maximum allowable
number of customers in the system.
• The sixth characteristic gives the size of the population
from which customers are drawn.
• M/E2/8/FCFS/10/∞ might represent a health clinic with 8
doctors, exponential interarrival times, two-phase Erlang
service times, a FCFS queue discipline, and a total capacity
of 10 patients.
QUEUING THEORY
44
(M/M/1):(FCFS// )
• The models has following assumptions
 Poisson arrival rate and exponential distribution of inter-arrival
times.
 Single waiting line with no restriction on queue length
 Queuing discipline is First come first served
 Single server with exponential service time.
• The solution is obtained by using flow balancing approach.
The three states possible in small time Δt before t are
 The system is in state n and no arrivals or service completions
occurred.
 The system is in state (n+1) and a service completion occurs,
reducing the customers to n.
 The system is in state (n-1) and an arrival occurs, bringing the no
of customers to n.
QUEUING THEORY
45
Single Server (M/M/1)
• Obtaining system of equations
P 0(t  t )  P 0(t )[1  t ]  P1(t ) t
for n  0
Pn(t  t )  Pn(t )[1  t  t ]  Pn  1t  Pn  1t
for n  0

 Pn  1  P0  P1  P2...  Pn  1
subjected to normalisation condition
n 0
• Taking the limits as t 0, and subject to the same
normalisation, we get
dP0(t )
 P 0(t )  P1(t ) for n  0
dt
dPn(t )
 (   ) Pn(t )  Pn  1(t )  Pn  1(t ) for n  0
dt
QUEUING THEORY
46
Single Server Model
• For equilibrium conditions we require
d
Lim Pn(t )  Pn and Lim
{Pn(t )}  0 for n  0,1,2,..
t 
t  dt
• Let =/. Then we get following results
P1  P0
Pn   N P0
• Applying normalisation condition of Pn=1 we get
P0 
1

 N
N 0
The denominator is an infinite geometric series whose sum is


N 0
N 
1
and hence P 0  1   and Pn   N (1   )
1 
QUEUING THEORY
47
Performance Measures – Single Server
• Average no of customers in the system
Ls   nPn   n(1   )  n , 0    1

 Ls  (1   ) n n  (1   ){
}
2
(1   )
 Ls 

1 


 
• Average no of customers in queue
Lq 
 (n  1)Pn   nPn   Pn (n  1 to )
 Lq  Ls  [
2
Pn  Po]  Ls  [1  Po] 
0
 (   )


2
Lq 
 (   )
QUEUING THEORY
48
Performance Measures – Single Server
• Average time a customer spends waiting in the
queue
Lq

W q


 (   )
• Average time a customer spends in system
W s  Waitingtime in queue  service time
W s W q 1  1

W s  Ls
(   )
 Ls


• Probability of customers in system greater than or
equal to k
k
k 1




P(n  k )    ; P(n  k )   


QUEUING THEORY
49
Performance Measures – Single Server
• Variance (fluctuations of queue length)
Var(n) 



(1   ) 2 (    ) 2
• Probability that a queue is non-empty

P ( n  1)  1  Po  P1   

2
• Expected length of non-empty queue
Expected length of waiting line
Lq

Lb 


Pr ob(n  1)
P(n  1)   
QUEUING THEORY
50
Parameters
Average no of
customers in
System
Average waiting time
per unit in
Ws  Ls
Probability of having k
or more units in the
system

P (n  k )  

Expected length of non
empty queue
Lb 
Ls 
Queue

1 

 


 
2
Lq 
 (   )
Wq 





Probability that a queue
is non empty
Probability that waiting
time is more than t

Lq



 (   )
k


Lb 

 

P(n  1)   

e  (    )t
P1  P 0
2
  (    )t
e

Pn   N P 0
QUEUING THEORY
51
Example (M/M/1)
• At a cycle repair shop on an average a customer
arrives every five minutes and on an average, the
service time is 4 minutes per customer. Suppose
that the inter-arrival time follows Poisson
distribution and service time is exponentially
distributed. Find the various performance
characteristics
QUEUING THEORY
52
M/M/1:N/FCFS/
• Limited no of customers are allowed in the system.
• Service rate need not be greater than arrival rate.
n   for n  0,1,2..., N - 1
n  0 for n  N, N  1,..
μn  μ for n  1,2,...
Using    /  , we get
Pn  nP0 for n  N and Pn  0 for n  N
• Steady state equations are
P0  P1
for n  0
(   ) Pn  Pn  1  Pn  1
λPN-1  μPN
for n  1,2,...N - 1.
for n  N
QUEUING THEORY
53
Performance characteristics
• Service rate meed not be more than arrival rate as
arrivals are controlled.
• eff, rather than ,, is the rate that matters.
• eff is calculated as arrival rate minus the
probability of losing customers.
• eff =  - lost =  - Pn= (1-Pn)
• Other parameters are calculated from the eff.
QUEUING THEORY
54
Performance Characteristics
Po 
1 
, for   1 and   1
1   N 1
1
Po 
for   1
N 1
Parameters
Average no of
customers in
, for   1
1   N 1
1
Po 
for   1
N 1
Pn 
System
Ls 
(1   )  n
Queue
N
 nPn
Lq 
n 0
Average waiting time
per unit in
Ws 
Ls
 (1  PN )
 (1  PN )

Wq 
QUEUING THEORY
Lq
 (1  PN )
55
Example
• Consider a single server queuing system with
Poisson arrival, exponential input, exponential
service times. Suppose the mean arrival rate is 3
calling units per hour, the expected service time is
0.25 hour and the maximum permissible calling
units in the system is 2. Derive the steady state
probability distribution of the number of calling
units in the system, and then calculate the
expected no in the system.
QUEUING THEORY
56
M/G/1: GD/ /
• Queuing models in which the arrival and departure rate do
not follow Poisson are complex.
• The above is a model with Poisson arrival rate and service
time t, is represented by any general distribution.
• The mean of the distribution is E(t) and variance is Var(t).
• Let  be the arrival rate. If E(t) < 1, then we can calculate
the Length of the system queue.
 2( E 2(t )  var[t ])
Ls  E (t ) 
, E (t )  1
2(1  E[t ])
QUEUING THEORY
57
Example
QUEUING THEORY
58