Little's law

From Wikipedia, the free encyclopedia

Theorem in queueing theory

In mathematical queueing theory, Little's law^[a] is a theorem by John Little which states that the long-term average number of customers (L) in a stationary system is equal to the long-term average effective arrival rate (λ) multiplied by the average time that a customer spends in the system (W). Expressed algebraically the law is

${\displaystyle L=\lambda W.}$

In plain terms, the law says that the average number of items in a system depends on both the rate at which items enter the system and the average time each item remains there. If items arrive faster, or if each item stays longer, the average number present increases proportionally.

The relationship is not influenced by the arrival process distribution, the service distribution, or the service order. Queues often arise when demand approaches service capacity, and their size is affected by service-time variability, arrival variability, and the service discipline.^[3]

The result applies to any system, and particularly to systems within systems.^[4] For example, in a bank branch the customer line might be one subsystem and each of the tellers another subsystem, and Little's result can be applied to each one as well as to the whole. The law holds under broad stability conditions: in common queueing applications, the relevant long-run averages must exist, the system boundary must be consistent, and the effective arrival rate must match the population whose time in system is being measured.^[5]

In some cases it is possible not only to mathematically relate the average number in the system to the average wait but even to relate the entire probability distribution (and moments) of the number in the system to the wait.^[6]

In a 1954 paper, Little's law was assumed true and used without proof.^[7][8] The form L = λW was first published by Philip M. Morse where he challenged readers to find a situation where the relationship did not hold.^[7][9] Little published a general proof of the law in 1961 under broad stationarity assumptions.^[10] Little's proof was followed by a simpler version by Jewell^[11] and another by Eilon.^[12] Shaler Stidham published a different and more intuitive proof in 1972.^[13][14]

The following worked examples illustrate Little's law in computing and retail contexts. In each case, the average rate and the average time in the system are measured over the same stable period and refer to the same population of items.^[15][5]

Imagine an application that had no easy way to measure response time. If the mean number in the system and the throughput are known, the average response time can be found using Little's law:

mean response time = mean number in system / mean throughput

For example, a queue-depth meter shows an average of nine jobs waiting to be serviced. Adding one for the job currently being processed gives an average of ten jobs in the system. Another meter shows a mean throughput of 50 per second. The mean response time is then 0.2 seconds = 10 / 50 per second.^[5][16]

Imagine a small store with a single counter and an area for browsing, where only one person can be at the counter at a time, and no one leaves without buying something. So the system is:

entrance → browsing → counter → exit

If the rate at which people enter the store (called the arrival rate) is the rate at which they exit (called the exit rate), the system is stable. By contrast, an arrival rate exceeding an exit rate would represent an unstable system, where the number of waiting customers in the store would gradually increase towards infinity.

Little's Law tells us that the average number of customers in the store L, is the effective arrival rate λ, times the average time that a customer spends in the store W, or simply:

${\displaystyle L=\lambda W}$

Assume customers arrive at the rate of 10 per hour and stay an average of 0.5 hour. This means we should find the average number of customers in the store at any time to be 5.

${\displaystyle L=10\times 0.5=5}$

Now suppose the store is considering doing more advertising to raise the arrival rate to 20 per hour. The store must either be prepared to host an average of 10 occupants or must reduce the time each customer spends in the store to 0.25 hour. The store might achieve the latter by ringing up the bill faster or by adding more counters.

We can apply Little's Law to systems within the store. For example, consider the counter and its queue. Assume we notice that there are on average 2 customers in the queue and at the counter. We know the arrival rate is 10 per hour, so customers must be spending 0.2 hours on average checking out.

${\displaystyle W={\frac {L}{\lambda }}={\frac {2}{10}}=0.2}$

We can even apply Little's Law to the counter itself. The average number of people at the counter would be in the range (0, 1) since no more than one person can be at the counter at a time. In that case, the average number of people at the counter is also known as the utilisation of the counter.

However, because a store in reality generally has a limited amount of space, it can eventually become unstable. If the arrival rate is much greater than the exit rate, the store will eventually start to overflow, and thus any new arriving customers will simply be rejected (and forced to go somewhere else or try again later) until there is once again free space available in the store. This is also the difference between the arrival rate and the effective arrival rate, where the arrival rate roughly corresponds to the rate at which customers arrive at the store, whereas the effective arrival rate corresponds to the rate at which customers enter the store. In a system with infinite capacity and no loss, the two are equal.^[15]

In manufacturing, Little's law connects work in process (WIP), throughput, and cycle time. If a production line completes 200 units per day and the average WIP is 100 units, then by the law each unit spends, on average,

${\displaystyle W=L/\lambda =100/200=0.5{\text{ days}}}$

in the line. Hopp and Spearman present this relation as one of the basic laws of factory operation, and use it both to estimate cycle time from observed inventory and to estimate WIP from observed throughput and lead time.^[17]

Little's law requires that all three quantities describe the same system boundary and the same class of items.^[15][5] A common error is to combine an arrival rate measured at one boundary with a waiting time measured at another.^[5] A second error is to use the offered arrival rate rather than the effective throughput in systems where arrivals may be blocked, abandoned, rejected, or lost.^[15][7] The law also describes long-run averages; finite-sample estimation requires statistical care because short transient periods and the treatment of customers present at the start or still in the system at the end of an observation interval can bias the estimate.^[18]

To use Little's law on data, formulas must be used to estimate the parameters, as the result does not necessarily directly apply over finite time intervals, due to problems like how to log customers already present at the start of the logging interval and those who have not yet departed when logging stops.^[19]

Little's law is widely used in manufacturing to relate cycle time, throughput, and work in process. Hopp and Spearman's Factory Physics presents the law as one of the fundamental relations of operations management, used to compute lead time from observed production rate and inventory.^[17]

Software-performance testers and capacity planners use Little's law to relate concurrency, throughput, and response time, and to detect when observed performance is constrained by the test harness rather than the system under test.^[20][21]

Other applications include staffing emergency departments in hospitals.^[15][22]

Lastly, an equivalent version of Little's law also applies in the fields of demography and population biology, although not referred to as "Little's Law".^[23][24] For example, Cohen (2008)^[25] explains that in a homogeneous stationary population without migration, ${\displaystyle P=B\times e}$, where ${\displaystyle P}$ is the total population size, ${\displaystyle B}$ is the number of births per year, and ${\displaystyle e}$ is the life expectancy from birth. The formula ${\displaystyle P=B\times e}$ is thus directly equivalent to Little's law (${\displaystyle L=\lambda \times W}$). However, biological populations tend to be dynamic and therefore more complicated to model accurately.^[26]

In some cases, it is possible not only to relate averages but to relate the entire probability distribution of the number in the system to the time in the system under a first come, first served discipline. A distributional relation for many FIFO/Poisson-class systems was derived by Keilson and Servi (1988)^[27] and further developed in related work, including links to the Fuhrmann–Cooper decomposition^[28]; later, Bertsimas and Nakazato (1995) provided a new proof and surveyed applications.^[29]

• List of eponymous laws (laws, adages, and other succinct observations or predictions named after persons)
• Erlang (unit)

• Sigman, K. A Proof of the Queueing Formula L = λ W, Columbia University.