CSC 406/SEN 306

QUEUING SYSTEMS AND PERFORMANCE EVALUATION

COURSE CONTENT
 Introduction
 Birth-death queuing systems
 Markovian queues
 The queue M/GI bounds, inequalities and approximations.

LECTURE 1- INTRODUCTION

What is queuing theory?

Queuing theory refers to the mathematical study of the formation, function, and
congestion of waiting lines, or queues. It’s also referred to as queueing theory, queue
theory, and waiting line theory.

At its core, a queuing situation involves two parts:

1. Someone or something that requests a service—usually referred to as the

customer, job, or request.
2. Someone or something that completes or delivers the services—usually
referred to as the server.

To illustrate, let’s take two examples. First, when looking at the queuing situation at a
bank, the customers are people seeking to deposit or withdraw money, and the servers
are the bank tellers.

Second, when looking at the queuing situation of a printer, the customers are the
requests that have been sent to the printer, and the server is the printer.

Queuing theory scrutinizes the entire system of waiting in line, including elements
like the customer arrival rate, number of servers, number of customers, capacity of the
waiting area, average service completion time, and queuing discipline.

Queuing discipline refers to the rules of the queue, for example whether it behaves
based on a principle of first-in-first-out, last-in-first-out, prioritized, or serve-in-
random-order.

2. How did queuing theory start?

Queuing theory was first introduced in the early 20 th century by Danish

mathematician and engineer Agner Krarup Erlang.

Erlang worked for the Copenhagen Telephone Exchange and wanted to analyze and
optimize its operations.

He sought to determine how many circuits were needed to provide an acceptable level
of telephone service, for people not to be “on hold” (or in a telephone queue) for too

1
long. He was also curious to find out how many telephone operators were needed to
process a given volume of calls.

His mathematical analysis culminated in his 1920 paper “Telephone Waiting Times”,
which contained some of the first queuing models and served as the foundation of
applied queuing theory. The international unit of telephone traffic is called the Erlang
in his honor.

Characterizing a Queuing System

Queuing models analyze how customers (including people, objects, and information)
receive a service. A queuing system contains:

 Arrival process. The arrival process is simply how customers arrive. They
may come into a queue alone or in groups, and they may arrive at certain
intervals or randomly.
 Behavior. How do customers behave when they are in line? Some might be
willing to wait for their place in the queue; others may become impatient and
leave. Yet others might decide to rejoin the queue later, such as when they are
put on hold with customer service and decide to call back in hopes of
receiving faster service.
 How customers are serviced. This includes the length of time a customer is
serviced, the number of servers available to help the customers, whether
customers are served one by one or in batches, and the order in which
customers are serviced, also called service discipline.
 Service discipline refers to the rule by which the next customer is selected.
Although many retail scenarios employ the “first come, first served” rule,
other situations may call for other types of service. For example, customers
may be served in order of priority, or based on the number of items they need
serviced (such as in an express lane in a grocery store). Sometimes, the last
customer to arrive will be served first (such s in the case in a stack of dirty
dishes, where the one on top will be the first to be washed).
 Waiting room. The number of customers allowed to wait in the queue may be
limited based on the space available.

Mathematics of Queuing Theory

Kendall’s notation is a shorthand notation that specifies the parameters of a basic

queuing model. Kendall’s notation is written in the form A/S/c/B/N/D, where each of
the letters stand for different parameters.

 The A term describes when customers arrive at the queue – in particular, the
time between arrivals, or interarrival times. Mathematically, this parameter
specifies the probability distribution that the interarrival times follow. One
common probability distribution used for the A term is the Poisson
distribution.
 The S term describes how long it takes for a customer to be serviced after it
leaves the queue. Mathematically, this parameter specifies the probability
distribution that these service times follow. The Poisson distribution is also
commonly used for the S term.

2
  The c term specifies the number of servers in the queuing system. The model
assumes that all servers in the system are identical, so they can all be
described by the S term above.
 The B term specifies the total number of items that can be in the system, and
includes items that are still in the queue and those that are being serviced.
Though many systems in the real world have a limited capacity, the model is
easier to analyze if this capacity is considered infinite. Consequently, if the
capacity of a system is large enough, the system is commonly assumed to be
infinite.
 The N term specifies the total number of potential customers – i.e., the number
of customers that could ever enter the queueing system – which may be
considered finite or infinite.
 The D term specifies the service discipline of the queuing system, such as
first-come-first-served or last-in-first-out.

Little’s law, which was first proven by mathematician John Little, states that the
average number of items in a queue can be calculated by multiplying the average rate
at which the items arrive in the system by the average amount of time they spend in it.

 In mathematical notation, the Little's law is: L = λW

 L is the average number of items, λ is the average arrival rate of the items in
the queuing system, and W is the average amount of time the items spend in
the queuing system.
 Little’s law assumes that the system is in a “steady state” – the mathematical
variables characterizing the system do not change over time.

Although Little’s law only needs three inputs, it is quite general and can be applied to
many queuing systems, regardless of the types of items in the queue or the way items
are processed in the queue.

APPLICATION OF LITTLE’S LAW: Little’s law can be useful in analyzing how

a queue has performed over some time, or to quickly gauge how a queue is currently
performing.

For example: a shoebox company wants to figure out the average number of
shoeboxes that are stored in a warehouse. The company knows that the average arrival
rate of the boxes into the warehouse is 1,000 shoeboxes/year, and that the average
time they spend in the warehouse is about 3 months, or ¼ of a year. Thus, the average
number of shoeboxes in the warehouse is given by (1000 shoeboxes/year) x (¼ year),
or 250 shoeboxes.

How Do You Use Queuing Theory?

Queuing theory is used to identify and correct points of congestion in a process. The
queue may consist of people, things, or information. In any case, they are being forced
to wait for service. That is inefficient, bad for business, and annoying (when the
queue consists of people). Queuing theory is used to analyze the existing process and
map out alternatives with a better result.

Queue management

3
Queue management as a set of principles aimed at controlling customer flow and
streamlining the queuing experience.

To add to that, queue management is not something that is needed once or twice. For
it to bring results, queue management needs to be a continuous process.

On paper, a huge number of visitors is a good thing for your business. That’s a lot of
potential sales just waiting to happen!

The problem arises when the influx of customer exceeds the capabilities of employees.
The fewer service clerks there are, the smaller the crowd of customers they can
manage.

The results? 51% of US consumers switched service providers in 2012 due to poor
customer service experiences.

Left on their own, service clerks can’t help but feel overwhelmed when faced with
Hun-like hordes of visitors storming in. It’s only when equipped with queue
management tools that they can prevail.

Queue management primarily concerns queue areas — i.e., places where queues
happen.

Introduction to queuing systems

Queue systems have come a long way. They went from simple physical barriers to
state-of-the-art virtual queuing software

There are many types of queuing solutions to choose from, but their most simple
cases are also among the least effective.

Take, for example, crowd barriers.

Crowd barriers, or stanchions, are typically used in hotels, banks, movie theaters,
public events, and other venues. Their main goal is crowd control through limiting the
access to certain areas.

On the one hand, it seems logical to use physical tools to manage the flow of
customers who are physically present at your location.

On the other hand, our digital age calls for something more sophisticated. Putting
your visitors inside a labyrinth of rope barriers also has adverse effect on their
psychological state.

Obviously, the situation calls for more elegant solutions.

A modern, digital-based queuing solution operates on a different level than simple

crowd management tools.

4
A digital queue system provide customers with a sense of agency, as they sign
themselves up for services using self-service kiosks — interactive terminals placed at
points of high foot traffic.

After signing up, a customer needs to look at the screen which provides relevant stats:
your place in a queue, the number of people before you, the service point you need to
go to, etc.

With clear instructions and text message notifications, the queuing process is faster
than ever. The checkouts are efficient, waiting time is reduced, and shopping
experience is greatly improved.

Meanwhile, staff receives valuable metrics like queue lengths, waiting times, and
other information provided by queue management systems that work towards further
improving the service.

What exactly goes into making the process of queuing smooth? Let’s take a look at
the principles of queuing systems.

The elements of a queuing system

Queue management — and, by extension, queue systems — rests on three main

principles of queuing. These are fairness, engaging queuing, and explained waiting.

Let’s explore each of these principles, one by one.

Fair queuing

Nobody likes queue-jumpers and line-cutters. But usually when confronted with
clear-cut cases of queue jumping, people don’t voice their dissatisfaction and prefer to
keep things civil.

Only 10% of people in a queue prevent line-cutting.

However, this means they will lash out at your queuing system that lets people jump
the queue without consequences.

As a result, your business loses a lot of respect by failing to effectively deal with this
situation.

Fair treatment means that everybody accepts the rules of the queue and their place in
it. If there’s a priority list, it needs to be communicated in advance.

Should there be queue-jumpers, they need to face consequences — or better yet,

prevented altogether.

A lack of order in your queues breeds anxiety and concern. People are afraid of
leaving their spot and generally mistrust their fellow queue-standers.

This makes for an unrewarding customer service atmosphere.

5
Fairness in queuing is not to be underestimated. Making sure your queues are fair is
one of the most important aspect of good queue management.

Engaging queuing

Believe it or not, the passage of time is not an objective thing. It largely depends on a
person’s unique perception of time.

Twiddling your thumbs while standing in a queue does nothing to shorten your wait
time. In fact, this can make your wait time seem even longer.

When customers are not engaged, their focus is on how much time they’ve waited.

Perceived wait time often feels longer than the actual time spent in a queue.

This is precisely the reason why you see magazines and brochures lying around in
waiting areas. Even a simple activity can take your mind off the fact that you’re
waiting and, effectively, help you kill time.

But you can go about it in another way.

When there’s no fear of losing their spot in a queue, customers are free to do what
they want — browse their phones, walk around the shop, engage with service staff,
etc.

A queuing solution that gets rid of the “time perception” problem kills two birds with
one stone.

Firstly, this makes for a better shopping experience. Both the perceived and actual
wait times are reduced, greatly improving your business’ image in your visitors’ eyes.

Secondly, this may also result in additional revenue. While browsing your store,
your visitors may find something that they would like to purchase either right away or
at some point in the future.

Effectively, this is advertising and merchandising, rolled into one.

Explaining customer wait times

Firstly, explained waiting means customers need to know how long they have to wait.
In amusement parks, this comes in the form of signs outside a queue, stating how
much wait time is expected.

Secondly, explained waiting means any hiccup in the queuing process needs to have a
clearly stated reason. When clerks do not tend to a customer, they need to have a
clear, verifiable reason.

Of course, it is easy to mistake a busy clerk for an idle one. And even when a
customer suspects a clerk is slacking off, most of the time there would be no outbreak.

6
Human brain works in mysterious ways. Our emotions often cloud our perception of
reality, which is how uncertain waits can feel longer than known, finite waits.

But you also have to consider this: people standing in a queue without a clue why
they’ve been waiting for so long feel powerless.

Your company, on the other hand, is supposed to improve their life and make them
feel better.

When there’s a clear cause for the delay, at least customers have concrete information
and don’t descend into full-on paranoia.

Naturally, the length of the period your customers are willing to wait also
depends on the value of your product or service. Or, rather, it depends on the
perceived value thereof.

That is not to say you can neglect waiting line management when you believe you’re
offering something exceptional, but there are many nuances you have to take into
account.

Types of queuing systems in different industries

At first, you may think that queue systems are something that would only work in
retail, where the number of clients you can serve in limited time is what matters the
most. However, crowd management is an issue worth tackling in many other
industries — from healthcare to government, to education, to banking.

Let’s see how queuing solutions can help in each case.

Queue management in retail

The most obvious application of queue management is brick-and-mortar stores. If

they cannot manage their lines efficiently, they are risking losing customers to their
competitors.

Long wait times and mismanaged queues are a bane of businesses worldwide.
Implementing a queue system for retail is what allows to turn these wait times into a
smooth customer experience.

Visitors who are met with proper queue management also can turn into loyal
customers — but more on that later.

Waiting line management in healthcare

How bad are wait times in healthcare? 21% patients go elsewhere to fill their
prescription due to long wait time.

The thing is, patients — as opposed to customers — don’t have the luxury of waiting.
Even when it’s not a life-or-death situation, patients don’t want to spend more time
in a hospital than necessary.

7
A healthcare queue management system would help control the patient flow, building
a better atmosphere for both the hospital staff and patients.

For the former, it’s all about taking the burden off their shoulder, helping them
manage their time better. For the latter, it’s all about reducing their anxiety and
frustration.

Queue management in education

Although there are peak times in retail and healthcare, nowhere are they more
apparent than in education.

Schools have to take into account the influx of students and would-be students during
the enrollment and at the beginning and end of semesters.

Then, there are also breaks when students visit the admission office to get the answers
to their questions.

What happens once you implement a queuing system at school? It helps with
organizing orderly waiting lines, preventing students from crowding up the place at
peak times.

Visitor management in government facilities

Government facilities are a black sheep in this list. They are not too worries about the
level of their customer management, since people come to them for services no one
else can provide.

In retail as well as pretty much every other industry, an additional customer is a

potential sale or revenue. For government offices, it’s an additional cost.

They need a waiting line management system precisely because they don’t want to
spend time on managing and servicing their visitors. The faster the output, the better.

As you can see, queuing solutions bring many benefits to all industries that need to
face more than one customer at a time.

Some industries — like government offices — are interested in the queuing aspect of
their problem. Others — like retail and healthcare — want to improve their customer
service situation.

A queuing solution is an irreplaceable tool that manages to help with both aspects of
visitor management.

EXAMPLES OF HOW QUEUING THEORY CAN BE APPLIED

The following situations are examples of how queueing theory can be applied:

 Waiting in line at a bank or a store

8
  Waiting for a customer service representative to answer a call after the call has
been placed on hold
 Waiting for a train to come
 Waiting for a computer to perform a task or respond
 Waiting for an automated car wash to clean a line of cars

The application of queuing theory

Queuing theory is powerful because the ubiquity of queue situations means it has
countless and diverse applications.

Queuing theory has been applied, just to name a few, to:

 Telecommunications
 Transportation
 Logistics
 Finance
 Emergency services
 Computing
 Industrial engineering
 Project management
 Operation research

The benefits of a queuing system

“The queuing aspect” and “improve the customer service situation” both sound good,
but also vague enough. Something a snake oil salesman would say.

So let’s get down to specifics. Namely, what kind of benefits a queuing solution can
bring your business.

Increase customer loyalty

In our modern age, where retaining a customer is more cost-efficient than getting a
new one, customer loyalty is an important talking point.

Considering that nowadays, customers tend to be more selective and are not afraid of
switching to a new brand, your have to make sure your customers like the experience
they’re getting.

Even the smallest details matter. Long waiting time may not have been a deal-breaker
a few decades ago, but now reducing wait time plays a major role in building positive
customer experience.

Things like expected wait, queue length, and wait time to service time ratio are what
makes or break a business.

Basic math suggests that less time spent waiting equals more time spent shopping.
Even when it doesn’t affect shopping habits of your customers, it makes them leave in
good mood.

9
The last moments we spend at a counter are the most crucial.

A customer decides whether he enjoyed the overall shopping experience or not. No

amount of additional customer service afterwards trumps the first impression.

By creating a better shopping experience, queuing solutions help your business turn
visitors into loyal customers. A loyal customer does not only visit your business more
often but also tends to purchase more.

In short, loyal customers are the backbone of success, and a queuing solutions helps
you get them more easily.

Gather customer data

Queuing solutions do not only help you improve your business right now, they also
help you improve it in the future. And they do so with the help of customer data.

You don’t have to hire and train additional staff or install special sensors to get
accurate footfall metrics. A queuing solution doubles as a people counting solution.

Since a queue system automatically keeps track of all signed-up customers, you get
easy access to the number of visitors, queue demand, and wait times.

In other words, a queue system helps you generate detailed, real-time retail
analytics:

1. The number of visitors.

2. The number of no-shows.
3. Identify areas with low/high footfall.
4. Discover wait, idle, and service times.

The hard numbers gathered and processed by a queuing solutions helps your business
to take advantage of sales opportunities and further improve your service.

The ability to compare the current data to its past counterpart helps you understand
whether you’re moving in the right direction.

Efficient use of staff

We’ve already mentioned “taking the load off employees”, but what does it mean,
exactly?

You have to understand that managing visitors is a lot of work. Greeting them,
signing them up, showing them directions — that’s a lot of time spent for every
visitor.

When you multiply this amount by the number of daily visitors, it becomes apparent
just how much time is wasted on something that could be automated.

10
A queuing solution is aimed at making the life better not only for your customers
but also employees. Once their time is freed up to pursue more important tasks,
customer service improves by leaps and bounds.

Coming back to the data aspect of QMS, analytics help with determining whether the
use of staff is efficient or not.

It can show the kinks in the workforce management, by pinpointing clerks who have
hard time managing their visitors.

Perhaps it’s time to provide additional training? How about redeploying employees to
this problem area? Or maybe you need to add another service point?

The choice is up to you. But it’s a queuing solution that helps you make this choice
informed.

11