Chapter 4: Queuing Systems

Introduction
 Queuing system is the organized collection and the
interrelationship between different components of a
queue with predefined intension for particular service.
 It is the system in which customer arrive for a particular
service, wait in a queue if service couldn’t start
immediately and leave after being served.
 So, it is the system consisting of organized grouping
between various elements like population of customers,
arrival, queuing discipline, server and output, with
predetermined objective to achieve service fast

1
• A queueing system consists of one or more servers that
provide service of some kind to arriving customers
• If the servers are busy, the customers join one or more
queues in front of the servers, hence queueing system

System Servers Customers

Bank Tellers Customers
Hospital Doctors, Nurses, beds Patients
Computer System CPU, I/O devices Jobs
Manufacturing systems Machines, Workers Parts
Airport Runways, Gates Airplanes, travelers
Communications network Nodes, links Messages, Packets

2
Examples:
 Waiting line queues are one of the most important
areas, where the technique of simulation has been
extensively employed.
 People at railway ticket window, vehicles at a petrol
pump or at a traffic signal, customers in the bank,
products at a machining center, television sets at a
repair shop are a few examples of waiting lines.
 Air traffic at an airport

• Events: aircraft arrival, landing and departure

3
 Queue status
Not empty Empty

Server Busy Enter queue Enter queue

status Idle Impossible Enter service
 The waiting line situations arise, either because,
-There is too much demand on the service facility so
that the customers or entities have to wait for
getting service, or
-There is too less demand, in which case the service
facility have to wait for the entities
 The objective in the analysis of queuing situations is
to balance the waiting time and idle time, so as to
keep the total cost at minimum.

5
Queuing System

 Elements of Queuing Systems

6
 Population of Customers or calling source can
be considered either limited (closed systems) or
unlimited (open systems).
 Unlimited population represents a theoretical
model of systems with a large number of possible
customers (a bank on a busy street, a motorway
petrol station).
 Example of a limited population may be a number
of processes to be run (served) by a computer or
a certain number of machines to be repaired by a
service man.
 It is necessary to take the term "customer" very
generally.
 Customers may be people, machines of various
nature, computer processes, telephone calls, etc.
7
 Arrival defines the way customers enter the
system.
 Mostly the arrivals are random with random
intervals between two adjacent arrivals.
 Typically the arrival is described by a random
distribution of intervals also called Arrival
Pattern.

8
 Queue or waiting line represents a certain number
of customers waiting for service (of course the
queue may be empty).
 Typically the customer being served is considered
not to be in the queue. Sometimes the customers
form a queue literally (people waiting in a line for a
bank teller).
 Sometimes the queue is an abstraction (planes
waiting for a runway to land).
 There are two important properties of a queue:
Maximum Size and Queuing Discipline.

9
 Maximum Queue Size (also called System
capacity) is the maximum number of customers that
may wait in the queue (plus the one(s) being
served).
 Queue is always limited, but some theoretical
models assume an unlimited queue length.
 If the queue length is limited, some customers are
forced to renounce without being served
 Queuing Discipline represents the way queue is
organized ( rules of inserting and removing
customers to/from queue)

10
 Service represents activity which takes time and the
customers are waiting for. Again take it very generally.
 It may be a real service carried on persons or
machines, but it may be a CPU time slice, connection
created for a telephone call, being shot down for an
enemy plane, etc.
 Typically a service takes random time. Theoretical
models are based on random distribution of service
duration also called Service Pattern.
 Another important parameter is number of server.
 System with one server only are Single Channel
System whereas system with more servers are
Multichannel Systems.

11
 Output represents the way customer leaves
the system
 Output is mostly ignored by theoretical models,
but sometimes the customers leaving the
server enter the queue again ("round robin"
time-sharing systems).

12
Characteristics of queuing systems
 Arrival Process
 The distribution that determines how the tasks
arrives in the system. The arrival pattern is
generally Poisson’s distribution with arrival
rate λ with probability that certain no. of
customer (x) arrive in a given time window

 It is discrete distribution, denoted by

M(Markovian). Other distribution might be
deterministic (D) or General (G).

13
 • The simulation time start when first customer arrives
to the system
• The arrival time is random and hence inter-arrival
time is also random
• If arrivals vary stochastically, it is necessary to define
the probability function of the inter-arrival times
• Two or more arrivals may be simultaneous. If n
variables are simultaneous, then n-1 of them have zero
inter-arrival times
• The arrival time is very much uncertain and hence its
distribution is important
Example;
Arrival Arrival Inter-arrival Arrival Arrival Inter-
Number Time Time Number Time arrival time
1 12.5 12.5 11 136.4 21.4
2 15.1 2.6 12 142.7 6.3
3 44.1 29.0 13 151.2 8.5
4 62.6 18.5 14 162.5 11.3
5 65.3 2.7 15 167.2 4.7
6 67.6 2.3 16 172.9 5.7
7 71.0 3.4 17 179.8 6.9
8 92.5 21.5 18 181.6 1.8
9 106.5 14.0 19 185.0 3.4
10 115.0 8.5 20 194.9 9.9
14
 Service Process
 The distribution that determines the task
processing time. The service distribution is
generally exponential which is continuous
distribution taking any feasible range of
time.
 For average service time (μ), the probability
that service will exceed at time t in
exponential distribution is:
 Service might have deterministic or general
distribution
•Normally, service time of a process is constant But if it
varies stochastically, it is described by a probability
function.
Ts = Mean service time µ
= mean service rate
P(t) = Probability that service time > t

• Normally, exponential distribution is used to represent the

service time but if the service time is fluctuating by large
variance, it is represented by normal distribution.
 Number of Servers
 Total number of servers available to process the
tasks depending on whether the model is single
server or multiple server.
 For e.g. M/M/1 queue has only one exponential
server.
 Queuing Discipline represents the way the queue
is organized (rules of inserting and removing
customers to/from the queue). There are these ways:
1) FIFO (First In First Out) also called FCFS (First
Come First Serve) - orderly queue.
2) LIFO (Last In First Out) also called LCFS (Last Come
First Serve) - stack.
3) SIRO (Serve In Random Order).
4) Priority Queue, that may be viewed as a number of
queues for various priorities. Etc

19
 Most quantitative parameters (like average queue
length, average time spent in the system) do not
depend on the queuing discipline.
 That’ s why most models either do not take the
queuing discipline into account at all or assume the
normal FIFO queue.
 In fact the only parameter that depends on the
queuing discipline is the variance (or standard
deviation) of the waiting time.

20
Queuing System

 Queuing Theory is a collection of mathematical

models of various queuing systems that take as
inputs parameters of the above elements and that
provide quantitative parameters describing the
system performance

21
Applications of Queuing Theory
 Telecommunications
 Traffic control
 Determining the sequence of computer
operations
 Predicting computer performance
 Health services (eg. control of hospital bed
assignments)
 Airport traffic, airline ticket sales
 Layout of manufacturing systems i.e.
planning
22
Example application of queuing theory
 Queuing theory is applied in many banks, retail stores,
oil stations, etc.
 There might be single queue/line and multiple
queue/lines configuration for the service.
 In multiple line/multiple checkout system, a queuing
system where customer wait for next available cashier,
the throughput is high since multiple lines are being used
for service as in banks.
 The customers takes service through multiple teller,
making the separate lines for each server(teller).

23
Figure: Single Queue Configuration(Single waiting line/multiple server)

Figure: Multiple Queue Configuration(Multiple waiting line/multiple server)

Kendall Notation

 Kendall’s Notation is the standard system used

to describe and classify a queuing model.
 David George Kendall proposed describing
queuing models using 3 factors A/S/c in 1953,
where A denotes the time between arrivals to
queue i.e. arrival distribution, S is size of jobs, c
is number of servers at node.

25
Kendall Notation 1/2/3(/4/5/6)

 Six parameters in shorthand

 First three typically used, unless specified
1. Arrival Distribution
2. Service Distribution
3. Number of servers
4. Total Capacity (infinite if not specified)
5. Population Size (infinite)
6. Service Discipline (FCFS/FIFO)

26
Kendall Classification of Queuing Systems
 The Kendall classification of queuing systems (1953) exists
in several modifications.
 The most comprehensive classification uses 6 symbols:
A/B/s/q/c/p

where:
 A is the arrival pattern (distribution of intervals between
arrivals).
 B is the service pattern (distribution of service duration).
 s is the number of servers.
 q is the queuing discipline (FIFO, LIFO, ...). Omitted for
FIFO or if not specified.
 c is the system capacity. Omitted for unlimited queues.
 p is the population size (number of possible customers).
Omitted for open systems.

27
Kendall Classification of Queuing Systems

These symbols are used for arrival and service patterns:

 M is the Poisson (Markovian) process with
exponential distribution of intervals or service
duration respectively.
 Em is the Erlang distribution of intervals or
service duration.
 D is the symbol for deterministic (known)
arrivals and constant service duration.
 G is a general (any) distribution.
 GI is a general (any) distribution with independent
random values.

28
Kendall Classification of Queuing Systems
Examples: What is the meaning of following
notations in Queuing System?
 D/M/1 = Deterministic (known) input, one
exponential server, one unlimited FIFO or
unspecified queue, unlimited customer population.
 M/G/3/20 = Poisson input, three servers with any
distribution, system capacity 20, unlimited
customer population.
 D/M/1/LIFO/10/50 = Deterministic arrivals, one
exponential server, queue is a stack of the
maximum size 9, total number of customers 50.
 M/D/6/10/FIFO = Markovian(Poissons) arrival,
six deterministic server, queue is orderly queue
with maximum size 10, unlimited customer
population
29
Kendall Classification of Queuing Systems

Examples:
 M/D/8/15/LIFO = Single waiting line with Poisson’s
or Markovian arrival, deterministic service
distribution with 8 servers, queue is stack with
maximum size 15(0 to 14), unlimited customer
population.
 D/M/1/FIFO/20/510 = According to Kendall
classification (notation), the above queuing
system represents the system with
Deterministic input (arrival), single server with
exponential distribution, queue is orderly queue
(FIFO) with system capacity 20, the population
of customers is 510.

30
Model of Queuing System

Queuing System

Queue
Server
Server System

 Use Queuing models to

 Describe the behavior of queuing systems
 Evaluate system performance: Queuing
models are build with certain arrival rate
and service rate
31
Analysis of M/M/1 queue
(Single Server Queue)
 Given:
• : Arrival rate
• : Service rate
 Solve:
 L: average number in queuing system
 Lq average number in the queue
 W: average waiting time in whole system
 Wq average waiting time in the queue

32
M/M/1 queue model

L
Lq



1
Wq 

33
 Here
• =Customer Arrival rate
• = Customer Service rate
• System Utilization, P= /, is the percentage
capacity utilized which reflects the extent to which
facility is busy rather than idle.
 Solve:
 Average number in queuing system,L= /(- )
 Average number in the queue,Lq = P.L
 Average waiting time in whole system,W=1/(- )
 Average waiting time in the queue, Wq= P.W
Measures of system performance
 Let us consider the following waiting line example:

 Demand=customer arrival rate(λ)=30customer/hr

 Capacity=average service rate(μ)=40 customer/hr
 System utilization(P)=λ/μ=30/40=0.75 i.e. 75%
- It means 45 min/hr is busy and 15 min/hr is idle time

 A waiting line will form with following characteristics:

30
 Customers in service system(L)= /(- )=30/(40-30)=3
i.e. 3 customers
 Customers in queue(Lq)=P.L=0.75*3=2.25
i.e. average no. of customers waiting=2.25
 Time spent in the system(W)=1/(- )= 1/(40-30)=1/10 hr
i.e. 6 minutes
 Time spent in waiting line(Wq)=P.W=0.75*6=4.5 minutes
i.e. average waiting time= 4.5 minutes
 Average service time (1/μ) = 1/40 hr=1.5 minutes

36
Measures of system performance

 The knowledge of average number of customers in

the queue or in the system helps to determine the
space requirements of the waiting entities.
 Also too long a waiting line may discourage the
prospectus customers, while no queue may suggest
that service offered is not of good quality to attract
customers.
 The knowledge of average waiting time in the queue
is necessary for determining the cost of waiting in
the queue.

37
System Utilization
 System Utilization is the percentage capacity utilized
which reflects the extent to which the facility is busy
rather than idle.
 System utilization factor (s) is the ratio of average arrival
rate (λ) to the average service rate (µ).
S= λ/µ in the case of a single server model
S= λ/µn in the case of a “n” server model
 The system utilization can be increased by increasing
the arrival rate which amounts to increasing the average
queue length as well as the average waiting time.
 Under the normal circumstances 100% system
utilization is not a realistic goal.

38
Simulation of Queuing System- Example
 In a single channel queuing simulation, inter arrival
times and service times are generated from the
distribution of random variable.
 Table below gives the inter arrival times and service
times generated at random :
Customer Inter arrival Service
Time(Minutes) Time(Minutes)
1 - 2
2 2 1
3 4 3
4 1 2
5 2 1
6 6 4

39
  The simulation table for the single-channel queue is:

Time Time Time

Inter Arrival Waiting
Service service service customer Idle time
Customer arrival time time in
time begins ends spends in of server
Time (Clock) queue
(Clock) (Clock) system
1 - 0 2 0 0 2 2 0
2 2 2 1 2 0 3 1 0
3 4 6 3 6 0 9 3 3
4 1 7 2 9 2 11 4 0
5 2 9 1 11 2 12 3 0
6 6 15 4 15 0 19 4 3
Total 15 13 4 17 6

40
• Some of the findings from the above Simulation
table are as follows:

 Average waiting time = (total time customers wait in

queue)/(total number of customers) = 4/6 =0.67minutes
 The probability that a customer has to wait =
(no. of customers who wait)/(total number of customers)
= 2/6=0.33
 The probability of server being idle = (total idle time of
server)/(total run time of simulation)= 6/19 = 0.31
i.e. The proportion of idle time of the server is 0.31. The
probability of the server’s being busy is 0.69
 Average service time = (total service time)/(total no. of
customers) = 13/6 = 2.16 minutes
 Average time between arrivals = (sum of all times
between arrival)/(number of arrivals-1)= 15/5 = 3minutes

41
 Average waiting time of those who wait =
(total time customers wait in queue)/(total no. of
customers that wait) = 4/2 = 2 minutes
 The average time a customer spends in the system =
(total time customers spends in the system)/(total
number of customers) = 17/6 = 2.83 minutes
Alternatively, Average time customer spends in the
system = (average time customer spends waiting in the
queue) + (average time customer spends in service) =
(0.67+2.16) = 2.83 minutes

42
 (IMPORTANT) See Example 2.1 (page 25) From
Discrete-Event System Simulation By Jerry Banks et al.

43