Little's Law: J. D. C. Little, A proof of the queueing formula: L = λW,

IEOR 4615, Lecture 3, January 27, 2015
Little’s Law*
L=λW
• L time average number in Line or system
• λ arrival rate
• W average Waiting time per customer
*J. D. C. Little, A proof of the queueing formula: L = λW,
Operations Research 9 (1961) 383-387.
(See written class lecture notes for more references.)

Outline
• Two Examples
– Unassigned problems from Homework 2
• Careful Statement
• Sketch of Proof (Explanation)
• Two More Examples
– More unassigned problems from Homework 2
• More on Proof Details (written notes)
Little’s Law EX 1 (HW2 Q3)
• A mad scientist has been studying the passage of
insects through a certain cubic meter of air in central
Minnesota, using automated instruments to
continuously monitor insect positions.
• Her measurements show that, during the calendar year
1990, insects crossed the boundary of the “invisible
cube" at an overall rate of 0.061 per hour, either going
in or going out, and that the average number of insects
in the cube was 0.0082.
• Q: What was the average duration of an insect visit to

the cube during 1990?
3
• Since the scientist counts both “going in” and
“going out”, the average arrival rate is
λ = (0.061/2) insects/hour = 0.0305 insects/hour.
The average number of insects in the cube is L = 0.0082.

Therefore, the average duration of an insect visit is
W =L/λ
= (0.0082 insects) / (0.0306 insects/hour) = 0.269 hours.
4
• It is known that 100 candidates on average pass
the annual qualification exam for accountants in
Israel. An accountant works for 20 years on
average (until retirement or professional change).
• Q1: Approximately how many accountants will be

employed in Israel in 2050?
• Q2: Briefly explain the assumptions that are used
in your solution.
5
• In 2050, approximately
L = λ W = 100 x 20 = 2000
accountants will be employed.
• Assumptions:
–λ and L will be constant till 2050.
–The edge effects cancel.
6
Careful Statement
Basic Definitions
• Ak arrival time of customer k (if there after time 0)
• Dk departure time of customer k
• Wk waiting time of customer k
– Wk = Dk - Ak
• R (0) number of remaining customers at time 0
– arrived before time 0
• A(t) number of new arrivals in [0,t]
– A(t) = max{k: Ak ≤ t} – R(0)
• L(t) number in system at time t;
– So L(0) = R(0) + A(0), common case is A(0) = 0
Averages over [0,t]
Time Averages:
Customer Average:
(among new arrivals in [0,t])

Averages Among First n Arrivals
Tn = An + R(0) arrival epoch of nth new arrival
Time Averages (over [0,Tn]):
Customer Average:
Theorem (Little’s law for limits of averages)
If
where
then
where L=λW
(full proof in the written lecture notes.)
Theorem (Little’s law for Steady State)
If, for a stochastic model, the arrival rate λ is well
defined, and limiting distributions exist, i.e.,
L(t) → L(∞) as t →∞
and
Wn → W∞ as n →∞,
(where → means convergence in distribution)
then E[L(∞)] = λ E[W∞]

Sketch of Proof
for the Relation

among limits for averages
Proof Idea
Proof Idea Continued
The main part is region D.
(The only part if System Starts and Ends Empty)
Compute Area of Region D in Two Ways
Area of D = =
So:
= x
(Equality if System Starts and Ends Empty)
How to Apply with Measurements?
(These are approximations; equality if begin and end

empty. More generally, we may want to evaluate with
statistical analysis, e.g., by estimating confidence
intervals; see Kim and WW (2012a,b); next class.)
TWO MORE EXAMPLES
Unassigned ones in Homework 2

Others in Recitation 2 and Homework 2
• Assume that K judges work at a court. The following data
was collected for every judge:
– Li,j: Number of pending cases that await decision of judge j,
1 ≤ j ≤ K, at the end of the month i, 1 ≤ i ≤ 12.
– λi,j: Number of cases that judge j, 1 ≤ j ≤ K, resolved during
month i, 1 ≤ i ≤ 12.
• The head-judge would like to estimate the average sojourn

time of a case in the court, per judge and overall.
• Q: How can he use the above data without additional

measurements? Explain your method and outline
restrictions.
19
• The average sojourn time for judge j
– We can estimate the average number of pending cases by
Lj = ∑i=1,…,12 Li,j / 12,

– And the average number of cases that the judge resolves per month by
λj = ∑i=1,…,12 λi,j / 12,

– Then the average sojourn time of a case at judge j is (in months)
Wj = Lj / λ j = ∑i=1,…,12 Li,j / ∑i=1,…,12 λi,j .
20
• The overall average sojourn time:
W = ∑j∑i=1,…,12 Li,j / ∑j ∑i=1,…,12 λ i,j .
Alternatively,
W = L / λ = ∑ j Lj / ∑j λ j
= ∑j λ j W j / λ
21
• A hospital emergency room (ER) is organized so that all patients register
through an initial check-in process. At his/her turn, each patient is seen by
a doctor and then exits the process, either with a prescription or with
admission to the hospital.
• Currently, 50 people per hour arrive at the ER, 10% of whom are admitted
to the hospital. On average, 30 people are waiting to be registered and 40
are registered and waiting to see a doctor. The registration process takes,
on average, 2 minutes per patient. Among patients who receive
prescriptions, average time spent with a doctor is 5 minutes. Among those
admitted to the hospital, average time is 30 minutes.
• Q1: On average, how long does a patient stay in the ER?

• Q2: On average, how many patients are being examined by doctors?
• Q3: On average, how many patients are in the ER?
• The ER can be divided into 4 subsystems:
1. Queue for registration.
2. Registration.
3. Queue for doctors.
4. Doctors.
• The arrival rate λ to all subsystems is 50 per hour = 5/6 per

min.
• Denote by Wi and Li the waiting time and average number of

customers in subsystem i. Then,
L1 =30; W2 = 2 min; L3 =40;
W4 =(5 x 0.9) + (30 x 0.1) = 7.5 min.

4 stages
1 2 3 4
1. Waiting
3. Waiting to 4. Seeing
to register 2. Being
see doctor doctor
registered
λ1= λ2= λ3= λ4= 50/hour = 5/6 per minute
L1 = 30
W2 = 2 minutes
L3 = 40
W4 =(5 x 0.9) + (30 x 0.1) = 7.5 minutes
So
W1= L1/λ1= 30/(5/6) = 36 minutes
L2= λ2W2= (5/6) x 2 = 5/3 patients
W3= L3/λ3= 40/(5/6) = 48 minutes
L4= λ4W4= (5/6) x (15/2) = 75/12 = 6.25 patients (answers Q2)
• From above, we can answer the three questions:
• If we denote by L and W the average number of customers and the

average waiting time in ER respectively, then
L = L1 + L2 + L3 + L4 = 77.9 (answers Q3)
W = W1 + W2 + W3 + W4 =93.5 minutes (answers Q1)
In summary,
 A patient stays 93.5 minutes in the ER on average.

 On average, 6.25 patients are being examined by doctors.
 There are 77.9 patients in the ER on average.

Little's Law*: *J. D. C. Little, A proof of the queueing formula: L = λW,

Uploaded by

Copyright:

Available Formats

Little's Law*: *J. D. C. Little, A proof of the queueing formula: L = λW,

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Little's Law*: *J. D. C. Little, A proof of the queueing formula: L = λW,

Uploaded by

Copyright:

Available Formats

IEOR 4615, Lecture 3, January 27, 2015

(See written class lecture notes for more references.)

• Q: What was the average duration of an insect visit to

λ = (0.061/2) insects/hour = 0.0305 insects/hour.

The average number of insects in the cube is L = 0.0082.

• Q1: Approximately how many accountants will be

(among new arrivals in [0,t])

Time Averages (over [0,Tn]):

then E[L(∞)] = λ E[W∞]

for the Relation

(The only part if System Starts and Ends Empty)

Compute Area of Region D in Two Ways

(These are approximations; equality if begin and end

Unassigned ones in Homework 2

• The head-judge would like to estimate the average sojourn

• Q: How can he use the above data without additional

– We can estimate the average number of pending cases by

Lj = ∑i=1,…,12 Li,j / 12,

λj = ∑i=1,…,12 λi,j / 12,

Wj = Lj / λ j = ∑i=1,…,12 Li,j / ∑i=1,…,12 λi,j .

W = ∑j∑i=1,…,12 Li,j / ∑j ∑i=1,…,12 λ i,j .

• Q1: On average, how long does a patient stay in the ER?

• The arrival rate λ to all subsystems is 50 per hour = 5/6 per

• Denote by Wi and Li the waiting time and average number of

L1 =30; W2 = 2 min; L3 =40;

W4 =(5 x 0.9) + (30 x 0.1) = 7.5 min.

• If we denote by L and W the average number of customers and the

 A patient stays 93.5 minutes in the ER on average.

You might also like

Little's Law: J. D. C. Little, A proof of the queueing formula: L = λW,

Little's Law: J. D. C. Little, A proof of the queueing formula: L = λW,

Little's Law: J. D. C. Little, A proof of the queueing formula: L = λW,