Queueing optimization is an important science that has made many significant contributions to operations
and marketing management. Queueing models have broad, practical application in numerous diverse fields.
The list of potential applications is almost endless, but here are just a few examples:
- Customer service (e.g., tech support help desks or telemarketing call centers)
- Inventory control
- Retailing (e.g., movie theaters, banks, gas stations, supermarkets, post offices, etc.)
- Machine servicing
- Salesforce management
- Traffic flow engineering and management (e.g., traffic lights, toll booths, etc.)
- Computer networks/data communication
- Medical emergency rooms
- Production systems
Here we present a basic introduction that will focus on operations optimization. We begin with a simple
diagram that shows three typical queueing system configurations:
The first system above is a single-queue, single-server system typical of ATMs; the second is a single-queue,
multi-server system found at most banks, post offices and airport check-in counters; and the third is a
collection of single-queue, single-server systems found at some fast-food restaurants, supermarkets, etc.
Each of these systems is a first-in, first-out (FIFO) system, where the first customer or object to enter the
system waits until a server is available, at which time the customer or object is the first to be served, after
which they leave the system.
In most of these queueing systems, customers or objects arrive at the system in a random pattern or
frequency distribution. (The exception would be production systems in which objects tend to arrive at
and move through the system in a nonrandom or deterministic fashion.) There are three key variables of
interest to us when analyzing queueing systems: arrival rate, service rate, and length or capacity of the queue in
which customers or objects can wait for service or processing. Total time spent in the system is the sum
of waiting time plus service time.
Random arrival rates (e.g., number of arrivals per hour) typically follow a Poisson distribution, where the
horizontal axis represents number of arrivals per time period and the vertical axis represents the probability with
which a particular arrival rate occurs:
A given arrival rate will necessarily imply a particular probability distribution for interarrival
times (the time periods elapsing between arrivals). If an arrival rate follows a Poisson probability
distribution, then the resulting interarrival times will follow an exponential distribution. Service
times may also follow an exponential distribution:
As the graphs above indicate, many queueing models assume that most customers or objects that pass through the
system arrive at relatively modest time intervals, and fewer have relatively long interarrival times; and that
most customers or objects are served with relatively modest service times, but a few require relatively
long service times. In addition, queue length can be assumed to be either finite or infinite. When
dealing with customers, a longer queue space will allow more customers to wait in the queue; but if the queue gets
too full, then customers will begin to "balk" or fail to enter the system at all. Such an outcome is
undesirable, and queueing models can be used to attempt to find suitable parameter values (i.e., queue
lengths, service times and numbers of servers) that minimize balking.
Because there are many possible queueing models, a notational system, Kendall Notation, has been developed
to describe a given model. Using this notation system, queueing models can be described with three parameters
using the general format of
1/2/3. (There is actually a more complicated version of the Kendall Notation system that allows for six
parameters instead of three, but that is beyond the scope of this discussion.)
The first parameter represents interarrival times, and is abbreviated as M for
Markovian interarrival times (following an exponential random distribution); or as G
for Generally distributed interarrival times (non-exponential random); or as D for
Deterministic (non-random) interarrival times. The second parameter represents service
times, and can be similarly abbreviated as either M for Markovian; or as
G for General; or as D for Deterministic. The third parameter,
S, represents the number of servers available in the system.
For example, a notation of M/M/1 represents a queueing model in which interarrival times and service times
both follow an exponential distribution, and there is one server in the system. A notation of M/G/2
represents a queueing model in which interarrival times are distributed exponentially, service times follow a
general (nonexponential) distribution, and there are two servers. And so forth.
This link takes you to an example of a simple
M/M/S queueing model in which we can try to adjust the queue length and number of servers (S) to
handle shorter interarrival times that tend to occur at heavier customer traffic times.
This link leads to an example of a G/G/S queueing model that helps a
supermarket reduce the amount of time customers have to spend waiting in check-out lines.
This link goes to an example of a M/G/S queueing model showing how a
fast-food restaurant can improve service and its bottom line by installing a self-service soft-drink dispenser.
Here is a M/D/S queueing model example showing how a partially
automated car wash can benefit from replacing post-washing cloth drying with automated blow drying.
Return to Optimization Programming main page