In general, a queueing system involves customers who enter the system, wait in line (a
queue), are served, and leave the system. While many familiar queueing situations
involve only people as customers and servers, there are also many applications in which
one or both of these entities is inanimate (e.g., an ATM could be the �server,� parts on an
assembly line could be the �customers�). Nevertheless, the terms customer and server
are still used. The key features of queueing systems can be classified as characteristics of
arrivals, service discipline, and characteristics of service.
Characteristics of the stream of arrivals
Two important issues relevant to a queue
involve the timing and types of arrivals. Usually, the timing of arrivals is described by
specifying the average rate of arrivals per unit of time (a), or the average interarrival time
(1/a). For example, if the average rate of arrivals, a = 10 per hour, then the interarrival
time, on average, is 1/a = 1/10 hr = 6 min. In many simple applications, the pattern of
times between successive arrivals and the service times both have exponential probability
distributions of the form f(t) = ke-kt, where k = a for arrivals and k = h for service. This
leads to the formulas x = a/h and L = x / (1 � x). In many cases, the arrival patterns
and/or service patterns may not be exponential, such as in the case of a doctor�s
scheduled appointments, and the formulas given here do not apply. For these cases, other
methods of analysis must be used.
There are at least two issues related to the types of arrivals. First, the arrivals may occur
one at a time or in batches (such as a carload, for example). Second, the arrivals might
well be treated as essentially all the same, or they may be separated into groups according
to some characteristic. For example, at a hospital emergency room, a triage nurse
examines in-coming patients and prioritizes their order of treatment.
Service discipline
The service discipline is the rule, or set of rules, specifying which of
the waiting customers is next to receive service. The most common service discipline is
first-come-first-served. Other service disciplines include last-come-first-served, servicein-
random-order, and shortest-processing-time. An example of the last case occurs when
computer operators prioritize jobs waiting to be processed according to their expected
processing time and run the shortest jobs first.
Other service discipline issues concern whether and how long customers will wait in line
and, if there are lines, whether there is one line or multiple lines. There may be a single
line even when there is more than one server (e.g., banks, post offices, and airport checkins).
Service characteristics. In most simple queueing systems, each customer is served by
one and only one server, no matter how many servers are present. The service time is
usually assumed to be random and exponentially distributed, and when there are multiple
servers, it is usually assumed that all servers are identical. That is, we assume that each is
able to service customers at the same average rate, h. It might seem more natural to use s
or perhaps c to represent this variable, but s and c are used for other variables in queueing
theory. Therefore, throughout the Arm-and-a-Leg student activity, we have used the term
�help� in place of �serve.� The reciprocal, 1/h, of the average rate of service is the
average time required to serve one customer. For example, if a server can serve h = 3
customers per hour, on average, then 1/h = 1/3 hr = 20 min is the average service time for
one customer.
In addition to queueing systems which employ a single server or multiple servers in
parallel, some queueing systems employ multiple servers in sequence. This set-up is
appropriate when customers must be served by more than one server and is often
encountered in manufacturing settings. For example, parts on an assembly line can be
thought of as �customers� waiting for �service� at various workstations (�servers�) on the
line. A similar situation occurs in a cafeteria line where customers must wait for service
at several points in the line.
Queueing formulas
Analysis of queues requires defining certain performance measures. Two key measures
are:
|
L = the average number of customers in the system and
W = the average time a customer spends in the system.
|
If we let:
|
a = the average rate of customer arrivals and
h = the average rate at which customers can be served (or helped, to use the language we have used in the student activity), then
1/a = the average time between successive arrivals and
1/h = the average service time per customer.
|
The ratio of customer arrival rate to customer service rate, x = a/h, also reflects the
average number of arrivals during an average service time.2 This formula can also be
shown to represent the fraction of time the server is busy.
In steady state (where x must be less than 1), that is, after the system has been operating
for a long time,
L = x/(1 � x) = a/(h � a)
A steady state relationship between L and W is given by a formula known as Little�s Law:
L = aW
or equivalently:
W = L/a
Likewise, if Wq = the average time spent waiting in the queue before service begins, then
Lq, the average length of the queue, is given by:
Lq = aWq
Foot Note 2 Note that x = a(1/h), so that, for example, if the average arrival rate a = 10/hr and the average service time 1/h = � hr, then x=5 represents the average number of arrivals during an average service time. In this case, since x > 1, the line would grow indefinitely.