What is OR

Queuing Systems & Formula


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.

Back to What is OR?



Website by:
QuIC Solutions, Inc