Simulation of Queueing System
Introduction
How queue is formed (role of customer,
server ......)
Simulation is often used in the analysis of
queueing models.
Queueing models provide the analyst with a
powerful tool for designing and evaluating the
performance of queueing systems.
A trade-off involved (while designing a queueing
system)
System Performance &
Input Parameters
Typical measures of system performance include server
utilization, length of waiting lines, delays of customers,
etc.
System performance is predicted as a function of input
parameters.
Input parameters: arrival rate of customers, service
demand of customers, rate at which server works,
arrangement of servers etc.
For relatively simple systems, compute mathematically.
For realistic models of complex systems, simulation is
usually required.
Characteristics of a
queueing system
Key elements of queuing systems:
Customer: anything that arrives at a facility and
requires service, viz. people, machines, trucks,
emails etc.
Server: any resource that provides the service,
for example: repairpersons, retrieval machines,
runways at airport.
Calling population: population of potential
customers, may be assumed to be finite or
infinite.
Population Models &
System Capacity
Infinite population model: Arrival rate is not
affected by the number of customers who have
left the calling population and joined the queue.
Finite population model: Arrival rate depends
on the number of customers being served and
waiting.
System Capacity: a limit on the number of
customers that may be in the waiting line or
system.
imited capacity/Unlimited capacity
Arrival Process
Arrivals Process: For infinite population, arrival
process is usually characterized in terms of inter-
arrival times of successive customers.
Arrival may occur at scheduled times or there may
be random arrivals (inter-arrival times usually
characterized by a probability distribution).
One at a time/in batches
Batch may be of constant size or random number
Queue Behavior
Queue behavior: Means actions of customers while in a
queue, waiting for service to begin.
alking: leaving when they see that the line is too long.
eneging: leaving after being in line, assuming that it is
moving too slowly.
ockeying: move from one line to another (shorter) line.
Queue Discipline
Queue discipline: the logical ordering of customers in a queue for
deciding which of the customer to be chosen for service (when a
server becomes free):
irst-in-first-out (FIFO)
ast-in-first-out (LIFO)
ervice in random order (SIRO)
hortest processing time first (SPT)
ervice according to priority (PR)
Service Time and
Queueing Notation
Service time and Service mechanism:
ervice times are normally the sequence of
independent and identically distributed random
variables
here may be one number of server, more
number of server or infinite number of servers
Simulation Examples
Three steps of the simulations
etermine the characteristics of each of the inputs to the
simulation. Quite often, these may be modeled as probability
distributions, either continuous or discrete.
onstruct a simulation table. Each simulation table is different, for
each is developed for the problem at hand.
or each repetition i, generate a value for each of the p inputs, and
evaluate the function, calculating a value of the response yi. The
input values may be computed by sampling values from the
distributions determined in step 1. A response typically depends
on the inputs and one or more previous responses.
Simulation of Queueing Systems
Serve
Waiting Line r
Calling
population
Fig. 2.1 Queueing
System
A queueing system is described by its calling population,
the nature of the arrivals, the service mechanism, the
system capacity, and the queueing discipline.
Simulation of Queueing
Systems
System state: the number of units in the system and
the status of the server(busy or idle).
Event: a set of circumstances that cause an
instantaneous change in the state of the system.
In a single-channel queueing system, there are only two
possible events that can affect the state of the system.
The arrival event: the entry of a unit into the system.
The departure event: the completion of service on a
unit.
Simulation clock: used to track simulated time.
Simulation of Queueing
Systems
If a unit has just completed service, the
simulation proceeds in the manner shown
in the flow diagram of Figure 2.2.
ote that the server has only two possible states :
it is either busy or idle.
Departure
Event
Begin No Another Yes Remove the waiting
server idle unit unit from the queue
time waiting?
Begin servicing the
unit
Fig. 2.2 Service-just-completed flow
diagram
Simulation of Queueing Systems
The arrival event occurs when a unit enters
the system.
he unit may find the server either idle or busy.
Idle: The unit begins service immediately
Busy: the unit enters the queue for the server.
Arrival
Event
Unit enters No Server Yes Unit enters
service busy? queue for
service
Fig. 2.3 Unit-entering-system flow
diagram
Simulation of Queueing Systems
Fig. 2.4 Potential unit actions upon
arrival
Fig. 2.5 Server outcomes after service
completion
Simulation of Queueing Systems
Pseudo-random numbers : The numbers are
generated using a procedure.
Table 2.2. Interarrival and Clock Times
ssume that the times between arrivals were generated by
rolling a die five times and recording the up face.
Simulation of Queueing Systems
Table 2.3. Service Times
ssuming that all four
values are equally likely to
occur, these values could
have been generated by
placing the numbers one
through four on chips and
drawing the chips from a
hat with replacement,
being sure to record the
numbers selected.
he only possible service
times are one, two, three,
and four time units.
Simulation of Queueing Systems
The interarrival times and service times must be meshed to
simulate the single-channel queueing system.
Table 2.4 was designed specifically for a single-channel queue
which serves customers on a first-in, first-out (FIFO) basis.
Simulation of Queueing Systems
Table 2.4 keeps track of the clock
time at which each event occurs.
The occurrence of the two types of
events(arrival and departure event)
in chronological order is shown in
Table 2.5 and Figure 2.6.
Figure 2.6 is a visual image of the
event listing of Table 2.5.
The chronological ordering of
events is the basis of the approach
to discrete-event simulation.
Simulation of Queueing Systems
Figure 2.6 depicts the number of customers in the system at
the various clock times.
Simulation of Queueing Systems
Example: Single-Channel Queue
Arrival Departure
Checkout Counter
Assumptions
• Only one checkout counter.
• Customers arrive at this checkout counter at random from 1 to
8 minutes apart. Each possible value of interarrival time has
the same probability of occurrence, as shown in Table 2.6.
• The service times vary from 1 to 6 minutes with the
probabilities shown in Table 2.7.
• The problem is to analyze the system by simulating the arrival
and service of 20 customers.
Simulation of Queueing Systems
Simulation of Queueing Systems
Simulation of Queueing Systems
Example (Cont.) Table 2.8
he first random digits are 913. To obtain the corresponding time
between arrivals, enter the fourth column of Table 2.6 and read 8
minutes from the first column of the table.
Simulation of Queueing Systems
Example (Cont.) Table 2.9
he first customer's service time is 4 minutes because the random digits 84
fall in the bracket 61-85
Simulation of Queueing Systems
Example (Cont.)
he essence of a manual simulation is the simulation table.
he simulation table for the single-channel queue, shown in Table 2.10, is an
extension of the type of table already seen in Table 2.4.
tatistical measures of performance can be obtained form the simulation
table such as Table 2.10.
tatistical measures of performance in this example.
Each customer's time in the system
The server's idle time
n order to compute summary statistics, totals are formed as shown for
service times, time customers spend in the system, idle time of the server,
and time the customers wait in the queue.
Simulation of Queueing Systems
Example (Cont.)
The average waiting time for a customer : 2.8 minutes
total time customers wait in queue 56
average waitng time 2.8 (min)
total numbers of customers 20
The probability that a customer has to wait in the queue :
0.65 number of customers who wait 13
probability ( wait ) 0.65
total numbers of customers 20
The fraction of idle time of the server : 0.21
total idle time of server 18
probability of idle server 0.21
total run time of simulation 86
The probability of the server being busy: 0.79 (=1-0.21)
Simulation of Queueing Systems
Example (Cont.)
The average service time : 3.4 minutes
total service time 68
average service time 3.4 (min)
total numbers of customers 20
This result can be compared with the expected service time by
finding the mean of the service-time distribution using the equation
in table 2.7.
E ( S ) sp ( s )
s 0
E ( S ) 1(0.10) 2(0.20) 3(0.30) 4(0.25) 5(1.10) 6(0.05) 3.2 (min)
The expected service time is slightly lower than the average service
time in the simulation. The longer the simulation, the closer the
E (S )will be to
average
Simulation of Queueing Systems
Example (Cont.)
he average time between arrivals : 4.3 minutes
sum of all times between arrivals 82
average time between arrivals 4.3 (min)
numbers of arrivals 1 19
This result can be compared to the expected time between
arrivals by finding the mean of the discrete uniform
distribution whose endpoints are a=1 and b=8.
a b 1 8
E ( A) 4.5 (min)
2 2
The longer the simulation, the closer the average will beE ( A)
to
The average waiting time of those who wait : 4.3
minutes total time customers wait in queue 56
average waiting time of those who wait 4.3 (min)
total numbers of customers who wiat 13
Simulation of Queueing Systems
Example (Cont.)
he average time a customer spends in the system : 6.2 minutes
total time customers spend in system 124
average time customer spends in the system 6.2 (min)
total numbers of customers 20
average time average time average time
customer spends = customer spends + customer spends
in the system waiting in the in service
queue
average time customer spends in the system = 2.8 + 3.4 = 6.2
(min)
Simulation of Queueing Systems
Example: The Able Baker Carhop Problem
Able
Baker
A drive-in restaurant where carhops take orders and bring food to the
car.
Assumptions
• Cars arrive in the manner shown in Table 2.11.
• Two carhops Able and Baker - Able is better able to do the job and
works a bit faster than Baker.
• The distribution of their service times is shown in Tables 2.12 and
2.13.
Simulation of Queueing Systems
Example: (Cont.)
simplifying rule is that Able
gets the customer if both
carhops are idle.
f both are busy, the customer
begins service with the first
server to become free.
o estimate the system
measures of performance, a
simulation of 1 hour of
operation is made.
he problem is to find how well
the current arrangement is
working.
Simulation of Queueing Systems
Example 2.2 (cont.)
he row for the first customer is filled in manually, with the random-number function
RAND() in case of Excel or another random function replacing the random digits.
fter the first customer, the cells for the other customers must be based on logic and
formulas. For example, the “Clock Time of Arrival” (column D) in the row for the
second customer is computed as follows:
D
2 = D1 + C2
he logic to computer who gets a given customer can use the Excel macro function
IF(), which returns one of two values depending on whether a condition is true or
false.
I
F( condition, value if true, value if false)
clock = 0
Is there the service
Is it time of arrival? Increment clock
N completed? N
o o
Y
e
s
Y
e
Store clock time (column H or K)
s
Generate random digit for
Is Able idle?
Y service (column E)
e
s
Convert random digit to random
number for service time
(column G)
N
o
Able service begin (column F)
Generate random digit for
Is Baker idle?
Y service (column E)
e
s
N Convert random digit to random
o
number for service time
(column J)
Nothing Baker service begin (column I)
Simulation of Queueing Systems
The analysis of Table 2.14 results in the following:
ver the 62-minute period Able was busy 90% of the time.
aker was busy only 69% of the time. The seniority rule keeps Baker less busy
(and gives Able more tips).
ine of the 26 arrivals (about 35%) had to wait. The average waiting time for all
customers was only about 0.42 minute (25 seconds), which is very small.
hose nine who did have to wait only waited an average of 1.22 minutes, which
is quite low.
n summary, this system seems well balanced. One server cannot handle all the
diners, and three servers would probably be too many. Adding an additional
server would surely reduce the waiting time to nearly zero. However, the cost
of waiting would have to be quite high to justify an additional server.