Simulation of Queuing Systems and discrete–event 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; why?Queuing 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 multi-access 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):