Lecture 02: A SingleServer Queue
Swakkhar Shatabda
CSI 423, Simulation and Modeling, Spring 2014
Department of Computer Science and Engineering
United International University
United International University CSI 423: Simulation and Modeling 1
A SingleServer Queue
A single-sever service node consists of a server plus its queue
Example: ATM booth.
United International University CSI 423: Simulation and Modeling 2
Queue Discipline
Queue Discipline: the algorithm used when a job is selected from the
queue to enter service
FIFO - first in first out
LIFO - last in first out
SIRO - serve in random order
Priority - shortest job first / other schemes
United International University CSI 423: Simulation and Modeling 3
Queue Assumptions
FIFO is also known as first come, first serve (FCFS)
The order of arrival and departure are the same
Unless otherwise specified, assume FIFO with infinite queue capacity.
Service is non-preemptive
Once initiated, service of a job will continue until completion
Service is conservative
Server will never remain idle if there is one or more jobs in the service
node
United International University CSI 423: Simulation and Modeling 4
The problem model
Initial Conditions
Queue empty
Server idle
Events
Arrival
Departure
United International University CSI 423: Simulation and Modeling 5
Variables
Two input variables
Arrival times, Ai
Service times, Si
IID (Independent and identically distributed) random variables
Performance measures
Delay
Customers in Queue
Utilization of the server
United International University CSI 423: Simulation and Modeling 6
Delay
Expected average delay in queue
Pi=n
i=1 Di
d̂(n) =
n
Di is the delay for the customer i
Gives the system performance from customer’s point of view.
United International University CSI 423: Simulation and Modeling 7
Customers in Queue
Expected number of customers in Queue
P∞
iTi
q̂(n) = i=1
T (n)
Ti is the total time of simulation that number of customers in the queue is
i
Who wants this information? customer/service provider?
United International University CSI 423: Simulation and Modeling 8
Customers in Queue
United International University CSI 423: Simulation and Modeling 9
Utilization of the server
Expected utilization of the server
R T (n)
0 B(t)dt
û(n) =
T (n)
B(t) = 1, if the server is busy at time t
B(t) = 0, if the server is idle at time t
United International University CSI 423: Simulation and Modeling 10
Utilization of the server
United International University CSI 423: Simulation and Modeling 11
An Example Simulation
Suppose inter-arrival times are A1 = 0.4, A2 = 1.2, A3 = 0.5, A4 =
1.7, A5 = 0.2, A6 = 1.6, A7 = 0.2, A8 = 1.4, A9 = 1.9, · · ·
Service times are
S1 = 2.0, S2 = 0.7, S3 = 0.2, S4 = 1.1, S5 = 3.7, S6 = 0.6, · · ·
Next event time advance mechanism.
United International University CSI 423: Simulation and Modeling 12
An Arrival Event
United International University CSI 423: Simulation and Modeling 13
A Departure Event
United International University CSI 423: Simulation and Modeling 14
An Example Simulation
United International University CSI 423: Simulation and Modeling 15
An Example Simulation
United International University CSI 423: Simulation and Modeling 16
An Example Simulation
United International University CSI 423: Simulation and Modeling 17
An Example Simulation
United International University CSI 423: Simulation and Modeling 18
An Example Simulation
United International University CSI 423: Simulation and Modeling 19
An Example Simulation
United International University CSI 423: Simulation and Modeling 20
An Example Simulation
United International University CSI 423: Simulation and Modeling 21
An Example Simulation
United International University CSI 423: Simulation and Modeling 22
An Example Simulation
United International University CSI 423: Simulation and Modeling 23
An Example Simulation
United International University CSI 423: Simulation and Modeling 24
An Example Simulation
United International University CSI 423: Simulation and Modeling 25
An Example Simulation
United International University CSI 423: Simulation and Modeling 26
An Example Simulation
United International University CSI 423: Simulation and Modeling 27
An Example Simulation
United International University CSI 423: Simulation and Modeling 28
Thats it!
Thank you
United International University CSI 423: Simulation and Modeling 29
