Done, your profile is created.Finish your profile by filling in the following fields
Forgot Password Earn Money,Free Notes
Password sent to your Email Id, Please Check your Mail
Updating Cart........ Please Wait........
Simulation of Queuing Systems
Simulation of Queuing Systems
Queuing Queuing System System
Prof. S. Shaky ya
1Simulation of Queuing Systems
Waiting line queues are one of the most important areas, where
the technique of simulation has been extensively employed.
The The w waiting aiting lines lines or or queues queues are are a a common common s site ite iin n r real eal life life.
People at railway ticket window, vehicles at a petrol pump or at a
traffic signal, workers at a tool crib, products at a machining
center center, television television sets sets at at a a r repair epair s shop hop are are a a ffew ew examples examples of of
2Simulation of Queuing Systems
The The waiting waiting line line situations situations arise, arise, either either because, because,
There is too much demand on the service facility so
that the customers or entities have no wait for
getting service, or
There is too less demand, in which case the service
f facilit ility h have tto wait it ffor t th he ent titi ities
The objective in the analysis of queuing situations is
to to balance balance tthe he waiting waiting ttime ime and and idle idle time time, so so as as to to
keep the total cost at minimum.
3Simulation of Queuing Systems
The The queuing queuing ttheory heory iits ts development development to to an an
engineer A.K.Earlang, who in 1920, studied
waiting line queues of telephone calls in
CCh openhagen, D Denmark k.
The problem was that during the busy period,
t telleph hone operattors were unabl ble tto h handl dle
the calls, there was too much waiting time,
which which r resulted esulted in in customer customer dissatisfaction dissatisfaction.
InTheAir: number of aircraft either landing or
waiting to land
OnTheGround: number of landed aircraft
RunwayFree: Boolean, true if runway availableDiscrete Event Simulation Computation
example: example: air air ttraf rafffic ic at at an an airport airport
events: aircraft arrival, landing, departure
Events that have been scheduled, but have not been
simulated simulated (processed) (processed) yet yet a are re stored stored in in a a pending pending
Events are processed in time stamp order; whyQueuing System
Elements Elements of of Queuing Queuing Systems Systems
Population of Customers or calling source can be
considered considered either either limited limited (closed (closed systems) systems) or or unlimited unlimited
Unlimited population represents a theoretical model of
systems systems w with ith a a large large number number of of possible possible c customers ustomers (a (a
bank on a busy street, a motorway petrol station).
Example of a limited population may be a number of
processes processes tto o b be e r run un (served) (served) by by a a c computer omputer or or a a c certain ertain
number of machines to be repaired by a service man.
It is necessary to take the term "customer" very generally.
Customers Customers m may ay be be people people, m machines achines of of various various nature nature,
computer processes, telephone calls, etc.
Arrival Arrival defines defines the the way way customers customers enter enter the the
Mostly Mostly the the a arrivals rrivals are are r random andom with with r random andom
intervals between two adjacent arrivals.
Typically Typically the the a arrival rrival iis s described described b by y a a random random
distribution of intervals also called Arrival
Queue or waiting line represents a certain number
of customers waiting for service (of course the
queue may be empty).
Typ ypically y the customer being g 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 There are are two two important important properties properties of of a a queue: queue:
Maximum Size and Queuing Discipline.
Maximum Maximum Q Queue ueue Size Size (also (also c called alled System System
capacity) is the maximum number of customers that
may wait in the queue (plus the one(s) being
Queue is always limited, but some theoretical
models models a assume ssume an an unlimited unlimited queue queue length length.
If the queue length is limited, some customers are
forced forced to to renounce renounce w without ithout being being served served
11Applications of Queuing Theory
Determining the sequence of computer
Predicting computer performance
Health services (eg. control of hospital bed
Ai Airport t ttraffi ffic, aiirlliine ttiick kett salles
Layout of manufacturing systems.
12Example application of queuing theory
In In many many retail retail stores stores and and banks banks
multiple line/multiple checkout system a
qqg ueuing sy ystem where customers wait for the next
We can prove using queuing theory that :
throughput improves increases when queues are
used instead of separate lines
13Example application of queuing theory
14Queuing theory for studying networks
View View network network a as s c collections ollections o of f q queues ueues
Queuinggy theory p provides p probabilistic
analysis of these queues
Average waiting time
Probability queue is at a certain length
Probability a packet will be lost
15Model Queuing System
Use Queuing models to
Describe the behavior of queuing systems
Evaluate system performance
Single Queue Configuration
17Characteristics of queuing systems
Arrival Arrival P Process rocess
The distribution that determines how the tasks
arrives in the sy ystem.
The The distribution distribution that that determines determines the the task task
Number of Servers
Total number of servers available to process the
Queuing Discipline represents the way the queue is organized
(r (rules les o of f iinserting nserting and and r remo emoviing ng c cus stomers tomers to/from to/from the the q que eue e) ).
There are these ways:
1) FIFO (First In First Out) also called FCFS (First Come First
Serve) ) orderlyyq queue.
2) LIFO (Last In First Out) also called LCFS (Last Come First Serve)
3) SIRO (Serve In Random Order).
4) Priority Queue, that may be viewed as a number of queues for
5) Many other more complex queuing methods that typically change
the the customer customer’s s position position iin n tthe he queue queue according according to to the the time time spent spent
already in the queue, expected service duration, and/or priority.
These methods are typical for computer multiaccess systems
Most qqp uantitative parameters ( (like averag ge q queue
length, average time spent in the system) do not
depend on the queuing discipline.
That That’s s w why hy most most models models e either ither do do not not take take the 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) deviation) of of the the w waiting aiting time time. There There is is t this his important important
rule (that may be used for example to verify results
of a simulation experiment):
The two extreme values of the waiting time variance are for the
FIFO FIFO q que eue e (minim (minimum) m) and and the the LIFO LIFO q que eue e (ma (maxim imum) m).
Theoretical models (without priorities) assume only one queue.
This is not considered as a limiting factor because practical
systems systems with with m more ore queues queues (bank (bank with with s several everal tellers tellers with with
separate queues) may be viewed as a system with one queue,
because the customers always select the shortest queue.
Of course, it is assumed that the customers leave after being
Systems with more queues (and more servers) where the
customers may be served more times are called Queuing
Service represents some activity that takes time and
that the customers are waiting for. Again take it very
It may be a real service carried on persons or
machines, but it may be a CPU time slice, connection
created df for a telleph hone call ll, b beiing sh hot d down ffor an
enemy plane, etc. Typically a service takes random
Theoretical models are based on random distribution
of service duration also called Service Pattern.
Another Another i important mportant parameter parameter is is the the number number of of
servers. Systems with one server only are called
Single Channel Systems, systems with more servers
are call lled d M Multi lti Ch Channel l S Syst tems
Outp put repy presents the way customers leave the
Output is mostly ignored by theoretical models, but
sometimes sometimes the the customers customers lleaving eaving tthe he server server enter enter
the queue again ("round robin" timesharing
Queuing Theory is a collection of mathematical
models of various queuing systems that take as
inputs inputs parameters parameters of of the the above above e elements lements and and that that
provide quantitative parameters describing the
23Analysis of M/M/1 queue
•: Arrival rate of jobs (packets on input link)
•:: Service Service rate rate of of the the server server (output (output link) link)
L: L: average average number number in in queuing queuing system system
L average number in the queue
W: W: average average waiting waiting ttime ime iin n w whole hole system system
W average waiting time in the queue
24M/M/1 queue model
25Kendall Notation 1/2/3(/4/5/6)
Six Six parameters parameters iin n s shorthand horthand
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)
26Kendall Classification of Queuing Systems
The The Kendall Kendall classifi classification cation o of f queuing queuing system systems s (1953) (1953) exi exists sts in in several several
The most comprehensive classification uses 6 symbols: A/B/s/q/c/p
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 iis th the queuiing di disciipli line (FIFO (FIFO, LIFO LIFO, ...) ). O Omitt itted d f for FIFO FIFO or if if not t
c is the system capacity. Omitted for unlimited queues.
p is the population size (number of possible customers). Omitted for open
system systems s.
27Kendall 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
D is the symbol for deterministic (known) arrivals and
constant service duration.
G is a general (any) distribution.
GI is a g( general (any)y) distribution with indep pendent random
28Kendall Classification of Queuing Systems
D/M/1 = Deterministic (known) input, one
exponential server, one unlimited FIFO or
unspq pecified queue,, unlimited customer p pop pulation.
M/G/3/20 = Poisson input, three servers with any
distribution, maximum number of customers 20,
unlimited unlimited customer customer population. population.
D/M/1/LIFO/10/50 = Deterministic arrivals, one
exponential server, queue is a stack of the
maximum maximum s size ize 9 9, total total number number of of customers customers 5 50 0.
29Simulation Simulation of of Queuing Queuing Systems Systems
Measures of system performance
The performance of a queuing system can be evaluated
in terms of a number of response parameters, however
the the following following ffour our are are generally generally employed. employed.
1. Average number of customers in the queue or in the
2. Average waiting time of the customers in the queue or
in the system
3 3. System System utilization utilization
4. The cost of the waiting time idle time
30Simulation of Queuing Systems
Measures of system performance
The knowledge of average number of customers in
the queue or in the system helps to determine the
space requiirementts of f th the waiti iting entiti tities. Al Also ttoo
long a waiting line may discourage the prospectus
customers, customers, while while no no queue queue may may s suggest uggest tthat hat service 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
31Simulation of Queuing Systems
Sy ystem Utilization
System Utilization that is the percentage capacity utilized
reflects that extent to which the facility is busy rather
System utilization factor (s) is the ratio of average arrival
rate (λ) to the average service rate (µ).
S= λ/µg µ 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 the arrival arrival r rate ate w which hich amounts amounts t to o iincreasing ncreasing tthe he average average
queue length as well as the average waiting time, as
shown in fig 1. Under the normal circumstances 100
system utilization is not a realistic goal.
Fig 1Time Oriented Simulation
A factoryg y has large number of semiautomatic machines.On 50
of the working days none of the machines fail. On 30of the
days one machines fails and on 20of the days two machines
fail. The maintenance staff on the average puts 65 of the
machines in order in one day, 30 in two days and remaining
5 in three days.
Simulate the syyy stem for 30 days duration and estimate the
average length of queue, average waiting time and server
loading that is the fraction of time for which server is busy.
34Time Oriented Simulation
Th The giiven systtem iis a siinglle server queuiing mod dell. Th The ffaiillure off th the
machines in the factory generates arrivals, while the maintenance
staff is the service facility. There is no limit on the capacity of the
system in other words on the length of waiting line. The population
of machines is very large and can be taken as infinite.
On 50of the days arrival=0
OO n 30off the days arrival=1
On 20of the days arrival=2
Expected arrival rate=0.5+1.3+2.2=0.7 per day.
SSi ervice pattttern:
65 machines in 1 day
30 machines in 2 days
5 5 machines machines in in 3 3 d da ays s
35Time Oriented Simulation
Average service time: 1.65+2.3+3.05=1.4 days
E Expectted d serviice ratte=1/1 1/1.4 4=0 0.714 714 machi hines per d day
The expected arrival rate is slightly less than the expected service rate
and hence the system can reach a steady state. For the purpose
of gg generating the arrivals p per day y and the services comp pleted p per
day the given discrete distributions will be used.
Random numbers between 0 and 1 will be used to generate the
arrivals as under.
Si Simil ilarlly, rand dom numb bers b bettween 0 0 and d 1 1 will ill b be used d ffor
generating the service times ( ST)
0 0.65r=0 65r=0.95ST=2days 95ST=2days
0.95r=1.0 ST=3 days
36Time Oriented Simulation
In the timeoriented simulation, the timer is advanced in fixed steps
of time and at each step the system is scanned and updated.
The time is kept very small, so that not many events occur during
this this time time.
All the events occurring during this small time interval are assumed
to occur at the end of the interval.
At start of the simulation, the syyy stem that is the maintenance facility
can assumed to be empty, with no machine waiting for repair.
On day 1, there is no machine in the repair facility.
On day 2 there are 2 arrivals, the queue is made 2.
Since service facility is idle, one arrival is put on service and queue
Server idle time becomes 1 day and the waiting time of customers
is is also also 1 1 day day. Timer Timer is is advanced advanced by by one one day day.
The service time, ST is decreased by one and when ST becomes
zero facility becomes idle.
Arrivals are g, generated which come out to be 1, it is added to the
37Time Oriented Simulation
Facility is checked, which is idle at this time.
One customer is drawn from the queue, its service time is
Idle time and waiting time are updated. The process is continued till
th the end d off siimullati tion.
The following statistics can be determined.
Machine failures( arrivals) during 30 days=21
Arrivals per day=21/30=0.7
Waiting time of customer=40 days
Waiting time per customer=40/21=1.9 days
Average length of the queue=1.9
Server idle time=4 days=4/30 100=13.33
Server loading( g=( 304) )/30=0.87
3839Simulation on queuing system
In a manufacturing g sy ystem p parts are being g made at a
rate of one every 6 minutes. They are two types A and
B and are mixed randomly with about 10 percent of
type type B B. A A separate separate inspector inspector is is assigned assigned to to examine examine
each type of parts. The inspection of a part takes a
mean time of 4 minutes with a standard deviation of 2
miinutes , b but part B B tak kes a mean tiime 20 20 miinutes and d
a standard deviation of 10 minutes. Both inspectors
rejject about 10 of the p parts they y insp pect. Simulate
the system for total of 50 type A parts accepted and
determine , idle time of inspectors and average time a
part part spends spends in in system system.