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.
Limited 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.

➢ Balking: leaving when they see that the line is too long.

➢ Reneging: leaving after being in line, assuming that it is

moving too slowly.

➢ Jockeying: 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):

➢ First-in-first-out (FIFO)
➢ Last-in-first-out (LIFO)
➢ Service in random order (SIRO)
➢ Shortest processing time first (SPT)
➢ Service according to priority (PR)
Service Time and Queueing
Notation
Service time and Service mechanism:
Service times are normally the sequence of independent and
identically distributed random variables
There may be one number of server, more number of server
or infinite number of servers
Simulation Examples
Three steps of the simulations

➢ Determine the characteristics of each of the inputs to the simulation.

Quite often, these may be modeled as probability distributions, either
continuous or discrete.

➢ Construct a simulation table. Each simulation table is different, for each is

developed for the problem at hand.

➢ For 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

Server
Waiting Line
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.
Note that the server has only two possible states : it is either
busy or idle.
Departure
Event

Begin server No Another unit Yes Remove the waiting unit

idle time waiting? from the queue

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.

The 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 queue

service busy? 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
Assume 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

Assuming 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.
The 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

The 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

The 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.)
The essence of a manual simulation is the simulation table.
The 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.
Statistical measures of performance can be obtained form
the simulation table such as Table 2.10.
Statistical measures of performance in this example.
Each customer's time in the system
The server's idle time
In 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.
 Time Time
Time Since Service Time Customer Time Customer Idle Time of
Arrival
Customer Last Arrival Time Service Waits in Service Spends in Server
Time
(Minutes) (Minutes) Begins Queue Ends System (Minutes)
(Minutes) (Minutes)

1 – 0 4 0 0 4 4 0
2 8 8 1 8 0 9 1 4
3 6 14 4 14 0 18 4 5
4 1 15 3 18 3 21 6 0
5 8 23 2 23 0 25 2 2
E2=max (G1, C2) and continues
I2=max (0, C2-G1)
F2=max (0, G1-C2) and continues
G-C
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 average will
be to E (S )
Simulation of Queueing Systems

Example (Cont.)
The 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 be to E ( A)

◼ 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.)
The 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 queue in service

 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.)
➢ A simplifying rule is that
Able gets the customer if
both carhops are idle.
➢ If both are busy, the
customer begins service
with the first server to
become free.
➢ To estimate the system
measures of
performance, a
simulation of 1 hour of
operation is made.
➢ The problem is to find
how well the current
arrangement is working.
Simulation of Queueing Systems
Simulation of Queueing Systems
 Able Baker
Random
Random Time Clock Time
Customer Digits
Digits for between Time of in
No. for Time Time Time Time
Arrival Arrivals Arrival Service Service Queue
Service Service Service Service Service
Time Time
Begins Ends Begins Ends

1 – – 0 95 0 5 5 0

2 26 2 2 21 2 3 5 0

3 98 4 6 51 6 3 9 0

4 90 4 10 92 10 5 15 0

5 26 2 12 89 12 6 18 0
 Simulation of Queueing Systems

➢The analysis of Table 2.14 results in the following:

➢ Over the 62-minute period Able was busy 90% of the time.
➢ Baker was busy only 69% of the time. The seniority rule keeps
Baker less busy (and gives Able more tips).
➢ Nine 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.
➢ Those nine who did have to wait only waited an average of
1.22 minutes, which is quite [Link] Idle Time / No of customers waiting = 11/9 = 1.22 min

➢ In 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.