System modelling & simulation 17CS834
MODULE - 2
CHAPTER 2: QUEUEING MODELS
Contents:
• Characteristics of Queueing Systems
• Queueing Notation – Kendall Notation
• Long-run Measures of Performance of Queueing Systems
• Steady-state Behavior of Infinite-Population MarkovianModels
• Steady-state Behavior of Finite-Population Models
• Networks of Queues
Purpose:
• Simulation is often used in the analysis of queueing models.
• A simple but typical queueing model Waiting line Server Calling population
Calling population
Waiting line Server
• Queueing models provide the analyst with a powerful tool for designing and evaluating the
performance of queueing systems.
• Typical measures of system performance
• Server utilization, length of waiting lines, and delays of customers
• For relatively simple systems: compute mathematically
• For realistic models of complex systems: simulation is usually required
4.1 Characteristics of Queueing System
The key elements of queuing system are the “customer and servers”.
Customer: refers to anything that arrives at a facility and requires service, e.g.,
people, trucks, mechanics, airplanes, emails, packets, frames, etc.
Server: Refer to any resource that provides the requested services. Eg.,
receptionists, repairperson, medical personal, machines,host, switch, etc.
4.1.1 Calling Population
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 1
System modelling & simulation 17CS834
The population of potential customers referred to as the “calling population”.
The calling population may be assumed to be finite or infinite.
The calling population is finite and consists of some specified number of potential
customers.
In system with a large population of potential customers, the calling population is
usually assumed to be infinite.
The main difference between finite and infinite population models is how the arrival
rate is defined.
Finite population model: if arrival rate depends on the number of customers being
served and waiting, e.g., model of one corporate jet, if it is being repaired, the repair
arrival rate becomes zero.
In an infinite population model, arrival rate is not affected by the number of
customer who have left the calling population and joined the queueing.
4.1.2 System Capacity
System Capacity: a limit to the number of customers that may be in the waiting
line or system.
Limited capacity, e.g., an automatic car wash only has room for 10 cars to wait in
line to enter the mechanism
An arriving customer who finds the system full does not enter but returns
immediately to the calling population.
If system is full no customers are accepted anymore.
Unlimited capacity, e.g., concert ticket sales with no limit on the number of people
allowed to wait to purchase tickets
4.1.3 Arrival Process
The arrival process for “Infinite population” models is usually characterized in
terms of interarrival time of successive customers.
Arrivals may occur at scheduled times or at random times.
When random times, the interarrival times are usually characterized by a
probability distribution.
Customer may arrive one at a time or in batches, the batches may be of constant
size or random size.
The second important class of arrivals is scheduled arrivals such as scheduled
airline flight arrivals to an input.
Third situation occurs when one at customer is assumed to always be present in the
queue. So that the server is never idle because of a lack of customer.
For finite population model, the arrivals process is characterized in a completely
different fashion.
Define customer as pending when that customer is outside the queueing system and
a member of the calling population
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 2
System modelling & simulation 17CS834
4.1.4 Queue Behavior and Queue Discipline
Queue Behavior:
It refers to the actions of customers while in a queue waiting for the service to begin.
In some situations, there is a possibility that incoming customers will
a) balk(leave when they see that the line is too long) ,
b) renege(leave after being in the line when they see that the line is moving
slowly) , or
c) jockey( move from one line to another if they think they have chosen a slow
line).
Queue discipline: refers to the logical ordering of the customers in a queue and
determines which customer will be chosen for service when a server becomes free.
Common queue disciplines include FIFO, LIFO, service in random order(SIRO),
shortest processing time first( SPT) and service according to priority (PR).
4.1.5 Service Times and Service Mechanism
The service times of successive arrivals are denoted by s1, s2, sn.. They may be
constant or of random duration.
When {s1,s2,sn} is usually characterized as a sequence of independent and
identically distributed random variables.
The exponential, weibull, gamma, lognormal and truncated normal distribution
have all been used successively as models of service times in different situations.
A queueing system consists of a number of service centers and interconnected
queues. Each service center consists of some number of servers c, working in
parallel.
That is upon getting to the head of the line of customer takes the first available
server.
Parallel Service mechanisms are either single server or multiple server(1<c<∞) are
unlimited servers(c=∞).
A self service facility is usually characterized as having an unlimited number of
servers.
• Example: consider a discount warehouse where customers may
• serve themselves before paying at the cashier (service center 1) or
• served by a clerk (service center 2)
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 3
System modelling & simulation 17CS834
• Wait for one of the three clerks:
• Batch service (a server serving several customers simultaneously), or customer
requires several serverssimultaneously.
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 4
System modelling & simulation 17CS834
• Candy production line
• Three machines separated by buffers
• Buffers have capacity of 1000 candies
Assumption:Always
sufficient supply of raw
material.
4.2 Queueing Notation(Kendal’s Notation)
Kendal’s proposal a notational s/m for parallel server s/m which has been widely adopted.
An a bridge version of this convention is based on format A|B|C|N|K
These letters represent the following s/m characteristics:
A-Represents the InterArrival Time distribution
B-Represents the service time distribution
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 5
System modelling & simulation 17CS834
C-Represents the number of parallel servers
N-Represents the s/m capacity
K-Represents the size of the calling populations
N, K are usually dropped, if they are infinity
Common symbols for A & B include M(exponential or Markov), D(constant or
deterministic), Ek (Erlang of order k), PH (phase-type), H(hyperexponential), G(arbitrary or
general), & GI(general independent).
For eg, M|M|1|∞|∞ indicates a single server s/m that has unlimited queue capacity & an
infinite population of potential arrivals
Eg:M|M|5|20|1500|FIFO:
The interarrival times & service times are exponentially distributed when N & K
areinfinite, they may be dropped from the notation.
For eg, , M|M|1|∞|∞ is often short ended to M|M|1. The tire-curing s/m can be initially
represented by G|G|1|5|5.
Additional notation used for parallel server queueing s/m are as follows:
4.3 Long-run Measures of performance of queueing systems
The primary long run measures of performance of queueing system are the long run time
average number of customer in s/m(L) & queue(LQ)
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 6
System modelling & simulation 17CS834
The long run average time spent in s/m(w) & in the queue(wQ) per customer
Server utilization or population of time that a server is busy ( ).
4.3.1 Time average Number in s/m (L):
Consider a queueing s/m over a period of time T & let L(t) denote the number of
customer I the s/m at time t.
Let Ti denote the total time during[0,T] in which the s/m contained exactly I customers.
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 7
System modelling & simulation 17CS834
4.3.2 Average time spent in s/m per customer (w)
Average s/m time is given as:
For stable s/m N-> ∞
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 8
System modelling & simulation 17CS834
With probability 1, where w is called the long-run average s/m time.
Considering the equation 1 & 2 are written as,
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 9
System modelling & simulation 17CS834
4.3.3 Server utilization:
Server utilization is defined as the population of time server is busy
Server utilization is denoted by ƥ is defined over a specified time interval[01]
Long run server utilization is denoted by p
Ƥ -> P as T -> ∞
Server utilization in G|G|C|∞|∞ queues
Consider a queuing s/m with c identical servers in parallel
If arriving customer finds more than one server idle the customer choose a server
without favoring any particular server.
The average number of busy servers say Ls is given by,
Ls = λ / μ 0<= Ls <= C
The long run average server utilization is defined by
The utilization P can be interpreted as the proportion of time an arbitrary server is busy in
the long run
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 10
System modelling & simulation 17CS834
VTUPulse.com
4.4 STEADY-STATE BEHAVIOUR OF INFINITE-
POPULATION MARKOVIAN MODLES
For the infinite population models, the arrivals are assumed to follow a poisson process
with rate λ arrivals per time unit
The interarrival times are assumed to be exponentially distributed with mean 1/λ
Service times may be exponentially distributed(M) or arbitrary(G)
The queue discipline will be FIFO because of the exponential distributed assumptions on
the arrival process, these model are called “MARKOVIAN MODEL”.
The steady-state parameter L, the time average number of customers in the s/m can be
computed as
∞
𝐿 = ∑ 𝑛𝑃𝑛
𝑛=0
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 11
System modelling & simulation 17CS834
Where Pn are the steady state probability of finding n customers in the s/m
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 12
System modelling & simulation 17CS834
Other steady state parameters can be computed readily from little equation to whole
system & to queue alone
w = L/λ
wQ = w – (1/μ)
LQ = λwQ
Where λ is the arrival rate & μ is the service rate per server
4.4.1 SINGLE-SERVER QUEUE WITH POISSON ARRIVALS & UNLIMITED
CAPACITY: M|G|1 t s
Suppose that service times have mean 1/μ & variance σ² & that there is one server
If P = λ / μ <1, then the M|G|1 queue has a steady state probability distribution with
steady state characteristics
The quantity P = λ / μ is the server utilization or long run proportion of time the
server is busy
Steady state parameters of the M|G|1 are:
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 13
System modelling & simulation 17CS834
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 14
System modelling & simulation 17CS834
4.4 2 MULTISERVER QUEUE: M|M|C|∞|∞
Suppose that there are c servers operating in parallel
Each of these servers has an independent & identical exponential service time
distribution with mean 1/μ.
The arrival process is poisson with rate λ. Arrival will join a single queue & enter the first
available service channel
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 15
System modelling & simulation 17CS834
For the M|M|C queue to have statistical equilibrium the offered load must satisfy λ/μ <
c in which case λ/ (cμ) =P the server utilization.
WHEN THE NUMBER OF SERVERS IS INFINITE (M|c|∞|∞ )
There are at least three situations in which it is appropriate to treat the number of server
as infinite
1. When each customer is its own server in other words in a self service s/m
2. When service capacity far exceeds service demand as in a so called ample server
s/m
3. When we want to know how many servers are required so that customer will
rarely be delayed.
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 16
System modelling & simulation 17CS834
4.5 STEADY STATE BEHAVIOR OF FINITE POPULATION
MODELS (M|M|c|K|K)
In many practical problems, the assumption of an infinite calling population leads
to invalid results because the calling population is, in fact small.
When the calling population is small, the presence of one or more customers in
the system has a strong effect on the distribution of future arrivals and the use of
an infinite population model can be misleading.
Consider a finite calling population model with k customers. The time between
the end of one service visit and the next call for service for each member of the
population is assumed to be exponentially distributed with mean 1/ λ time units.
Service times are also exponentially distributed, with mean 1/ µ time units. There
are c parallel servers and system capacity is K. Such a system is shown in figure.
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 17
System modelling & simulation 17CS834
The effective arrival rate λe has several valid interpretations:
Λe = long-run effective arrival rate of customers to queue
= long-run effective arrival rate of customers entering service
= long-run rate at which customers exit from service
= long-run rate at which customers enter the calling population
=long-run rate at which customers exit from the calling population.
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 18
System modelling & simulation 17CS834
Where λe is the long run effective arrival rate of customers to queue (or
entering/exiting service)
4.6 NETWORKS OF QUEUE
Many systems are naturally modeled as networks of single queues in which
customer departing from one queue may be routed to another
The following results assume a stable system with infinite calling population and
no limit on system capacity.
1) Provided that no customers are created or destroyed in the queue, then the
departure rate out of a queue is the same as the arrival rate into the queue over the
long run.
2) If customers arrive to queue i at rate λi and a fraction 0≤pij≤ 1 of them are routed
to queue j upon departure, then the arrival rate from queue i to queue j is λiPij is
over long run
3) The overall arrival rate into queue j, λi is the sum of the arrival rate from all
source. If customers arrive from outside the network at rate ai then
4) If queue j has ci < ∞ parallel servers, each working at rate µ ,then the long run
utilization of each server is
& Pj<1 is required for queue to be stable
5) If, for each queue j, arrivals from outside the network form a poisson process
with rate a and if there are ci identical services delivering exponentially
distributed service times with mean 1/µ then in steady state queue j behaves like
a M|M|C; queue with arrival rate
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 19
System modelling & simulation 17CS834
Discount store example:
• Suppose customers arrive at the rate 80 per hour and 40% choose
self-service.
Hence
Arrival rate to service center 1 is λ1 = 80(0.4) = 32 per hour
Arrival rate to service center 2 is λ2 = 80(0.6) = 48 per hour.
c2 = 3 clerks and µ2 = 20 customers per hour.
The long-run utilization of the clerks is:
ρ 2 = 48/(3×20) = 0.8
All customers must see the cashier at service center 3, the overall rate to service center 3
is λ3 = λ1 + λ2 = 80 per hour.
If µ3 = 90 per hour, then the utilization of the cashier is:
ρ3 = 80/90 = 0.89
Summary
Introduced basic concepts of queueing models.
Showed how simulation, and sometimes mathematical analysis, can be used to estimate
the performance measures of a system.
Commonly used performance measures: L, LQ, w, wQ, ρ1, and λe.
When simulating any system that evolves over time, analyst must decide whether to
study transient or steady-state behavior.
o Simple formulas exist for the steady-state behavior of some queues.
Simple models can be solved mathematically, and can be useful in providing a rough
estimate of a performance measure.
********************** End of Module – 2 ************************
Saraswathi D, Dept. of ISE, MITM Module – 2: Queueing Models Page 20
