CS 3341 Lecture Notes - Lecture 17: Queueing Systems, Snow Cone, Markov Chain
16 May 2018
School
Department
Course
Professor
Section 7.3 Bernoulli Single-Server Queuing Process
Page 1 of 10
“Occupied time feels shorter than unoccupied time. Research on queuing has shown
that, on average, people overestimate how long they’ve waited in a line by about 36
percent.”
—Alex Stone, Why Waiting is Torture (N.Y. Times, 8/19/2012)
Queueing Systems
These are systems where people or items “get in line,” wait to receive service, and leave
once service is complete. Examples include customers getting in line, jobs sent to a
computer for processing, and phone calls put on hold until they can be answered.
A queuing system has potentially many, many variables to consider:
ARRIVALS
How many arrivals up to now?
How many items in queue now?
Average frequency of arrivals?
ROUTING
How many servers?
How are items routed to the
servers?
SERVICE
How many served up to now?
How many items in service now?
Average frequency of services?
SYSTEM
How many items in the system now?
Arrival-to-service ratio (utilization)?
Capacity of the system?
Section 7.3 Bernoulli Single-Server Queuing Process
Page 2 of 10
Bernoulli Single-Server Queuing Process (BSSQP)
A queuing system with the following properties:
Discrete Time
One server
Unlimited capacity
Arrivals occur according to a Binomial process, where the probability of an arrival
in any given frame is 𝒑𝑨
If at least one job is in the system, the probability of a completed service (that is,
a departure) in any given frame is 𝒑𝑺
Service completion takes at least one frame
Waiting times and service times are independent
In any given frame, there are four possible transitions. Find a formula for the probability
of each, and note what happens to the value of the state 𝑋(𝑡).
No arrival and one service
No arrival and no service
One arrival and one service
One arrival and no service
