Queuing Theory

Queuing theory is the study of queues and the random processes that characterize them. It deals with making mathematical sense of real-life scenarios. For example, a mob of people queuing up at a bank or the tasks queuing up on your computer’s back end.

In queuing theory we often want to find out how long wait times or queue lengths are, and we can use models to do this. These models are typically important in business and software applications, and queueing theory is often considered a part of operations research.

About Queuing

Any queuing activity can be summarized as entities (customers in your supermarket queue, or jobs in a computer queue) trying to get through an activity (waiting to be served). Queues happen when we can’t all access the activity at the same time: when it is not economically efficient to have enough checkout lines for everyone to go right through as soon as they were ready, or there isn’t enough server space to do an unlimited amount of computer tasks at one moment.

In queueing theory a queue does not refer simply to a neat row which is always first come, first served. This is one example of a queue, but not the only kind. A mob trying to rush for the door on Black Friday is considered a queue as well, as is a group of job applicants waiting for interviews who are picked randomly, one by one, to be interviewed.

Types of Queues and Types of Service

First In First Out, or First Come First Served, is fairly common in banking and commerce. It is the type of queue you get when you have people politely lined up, waiting for their turn.

Last In First Out is the opposite scheme; whoever has been waiting for the shortest time is served first. This type of queue management is common in asset management, where assets produced or acquired last are the ones used or disposed of first. For example: the most recent employees are often the ones laid off first.

Priority is where customers are served based on their priority level; these levels could be based on status, task urgency, or some other criteria.

Shortest Job First is when whoever needs the shortest amount of service gets taken care of first

Processor Sharing is when everyone gets served, or half-served, at the same time; service capacity is distributed evenly among everyone waiting.

There may be a single server, where a line of people or items must go through a single bottleneck, or parallel servers, where the same line is served by several servers.  Or there may be a tandem queue, where each of multiple servers has their own queue or line.

Balking when a customer decides not to wait for service because the wait time threatens to be too long. Renegingis similar, but when a customer who has waited already decides to leave because they’ve wasted too much time. Jockeying is when a customer switches between queues in a tandem queue system, trying to orchestrate the shortest wait possible.

Standard Notation for Queueing Theory

To make life easier, there’s standard notation for queueing theory that is used across the board. These standard symbols include

λ: the mean arrival rate.

μ: the mean service rate.

n: the number of people in the system.

A: the arrival process probability distribution.

B: the service process probability distribution.

C: the number of servers.

D: the maximum number of customers allowed in the system at any given time, waiting or being served (without getting bumped).

E: the maximum number of customers total.

Queuing System Components

Input Source: The input source generates customers for the service mechanism. The most important characteristic of the input source is its size. It may be either finite or infinite. Please note that the calculations are far easier for the infinite case, therefore, this assumption is often made even when the actual size is relatively large.

If the population size is finite, then the analysis of queuing model becomes more involved. The statistical pattern by which calling units are generated over time must also be specified. It may be Poisson or Exponential probability distribution.

2. Queue: It is characterized by the maximum permissible number of units that it can contain. Queues may be infinite or finite.
3. Service Discipline:It refers to the order in which members of the queue are selected for service. Frequently, the discipline is first come, first served.

Following are some other disciplines:

• LIFO (Last In First Out)
• SIRO (Service In Random Order)
• Priority System

Service Mechanism:

A specification of the service mechanism includes a description of time to complete a service and the number of customers who are satisfied at each service event. The service mechanism also prescribes the number and configuration of servers. If there is more than one service facility, the calling unit may receive service from a sequence of these. At a given facility, the unit enters one of the parallel service channels and is completely serviced by that server. Most elementary models assume one service facility with either one or a finite number of servers.The following figure shows the physical layout of service facilities.

Unusual Customer/Server Behaviour

Customer’s Behaviour

• A customer may not like to join the queue due to long waiting line.
• A customer may leave the queue after waiting for sometime due to impatience.

Collusion. Several customers may cooperate and only one of them may stand in the queue.

Jockeying. When there are a number of queues, a customer may move from one queue to another in hope of receiving the service quickly.

Server’s Behaviour

Failure. The service may be interrupted due to failure of a server (machinery).

Changing service rates. A server may speed up or slow down, depending on the number of customers in the queue. For example, when the queue is long, a server may speed up in response to the pressure. On the contrary, it may slow down if the queue is very small.

Batch processing. A server may service several customers simultaneously, a phenomenon known as batch processing.

Assumptions of Queuing Theory

• The source population has infinite size.
• The inter-arrival time has an exponential probability distribution with a mean arrival rate of l customer arrivals per unit time.
• There is no unusual customer behaviour.
• The service discipline is FIFO.
• The service time has an exponential probability distribution with a mean service rate of m service completions per unit time.
• The mean arrival rate is less than the mean service rate, i.e., l < m.
• There is no unusual server behaviour.